Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 82
Текст из файла (страница 82)
461 Гл. 1711. Элементы комбннатаорики 6 2 4 б 7 9 8 3 3 1 Рис. 0.8.1 2) Алгоритм восстановления вектора Х = (1и 12, ..., 1 з) таков: координата П равна наименьшему числу из множества Ж = (1, 2, ..., и), не входящему в наборб = (1~, ул ..., 1„), Проведем ребро (зы 11) и положим № = Х~((з ), Л = (ум, з -з) Далее положим (з равным наименьшему числу из №, не входящему в Оы Проводим ребро ((з, у ) и т. д.
Последними соединяются ребром две вершины, оставшиеся в Ж„ 3) Утверждение вытекает из того, что соответствие между векторами л = (уы уз, ..., у -з) и нумерованными п-вершинными деревьями взаимно однозначно, а число векторов равно п 6.9. Использовать задачи 6.4, 6.8 и формулу Стирлинга. 6.15. Ц Провести доказательство индукцией по числу вершин. 3) Вывести из рекуррентного соотношения для числа 1 дихотомических деревьев следующее соотношение для производящей функции Т(х): Т(х) — 1 = хТ'(х). Отсюда Т(х) = (2х) '(1 — чг1 — 4х). Разлагая Т(х) в ряд, получаем, что ем=2( — 4) (' )= ( и). 6.18. 1) Число графов С из ейо таких, что для фиксированной пары вершин (г, 1) в С отсутствуют цепи длины меньше 3, равно 3" з х л)-зщ-з1-з х 2(з' . Поэтому р(п) = 2 (') ~ ~3" з 2(а) = — (' ) (-) 14,<з< 2) Из того,что 1пп р(п) = О,вытекает,что р(С) = О для почти всех графон.
Отсюда следует, что диаметр почти всех графов меньше 3. 3) Пусть рз(С) . число вершин степени п — 1 в графе С из 'Й„, а р,(п) = 2 заз ~ рз(С). Тогда р,(п) = п. 2 "М'. Отсюда следует, ие з что рз(С) = О для почти всех графов, а значит, радиус их не меньше 2. Теперь с учетом задачи 2) получаем утверждение. 6.19. Число гамильтоновых диклов в полном графе из 'Й„рав- 1 но — (и — 1)!.
Доля графов, у которых присутствует заданный гамильтонов 2 цикл., равна 2 6.26 Ц р( ) = (",) 2) Тур(и) = — (3) 2 з+ ( )(п — 2)(п — 3) 2 3) Вытекает из неравенства Чебышева с учетом того, что Ср(п) < и" = = о((р(п)) ). 26 Г. П. Гаврилов, А. А. Сапоженко 402 Ответы, указания, решения 6 21 1) Р(ггг ) = (З) (т)з/((2)) 6.22. ( ).2 628. ( )((з)и " )((,'„)) Глава 1Х 1.2. 1) Если множество (гг,..., гь) зафиксировано, то число граней В","; " равно числу двоичных наборов (егг... тг), т.е. равно 2 .
2) Если Н б В",'"„' „' " Ез В„",*"„",„* 'г, то аг = гг, ..., гтя = тя, а следовательно, грани совпадагот. Приходим к противоречию. 3) Вытекает из задач 1) и 2) с учетом того, что В",""'„'"' = 2' /и1 4) Число способов выбора направления (гг, ..., гь) равно (й). Теперь утверждение следует из задачи 1). б) Следует из задачи 4). 6) Если Н б В","';,*", то вектор (ггг...ггг) однозначно определяется вектором Н и множеством (гг, ..., гя), Последнее можно выбрать ( ) способами.
7) Код грани О размерности и, содержащей заданную грань Н размерности 1,получается из кода грани Н расстановкой Й вЂ” 1 прочерков среди и — 1 координат, имеющих значение 0 или 1. 8) Лля символов ег и гЗ из множества (О, 1, —.) введем операцию полагая: и 11 = ог если ег = 17; ег В = гг (сг гиз = )г), если о б (О, 1); (соответственно если г8 б (О, 1), о = —.-), значение ег )1 неопределенно, если о ~ )г и щ Д б (О, 1).
Естественным образом операция распространяется на векторы из О". Нетрудно убедиться в том, что если Н и В -- коды граней Е и Н, то вектор Н,9 определен тогда и только тогда, когда Е С Н ф Я. В последнем случае Н 3 является кодом грани, совпадающей с Р С Н. 9) Вытекает из задачи 7). 1.4. Положим 1, = и — и,. Тогда числа 1, удовлетворяют неравенству Макмиллана <з 2 ' < 1. Поэтому существует префиксныи двоичныи 1« . код с длинами кодовых слов 1г, ..., 1,. Пополним каждое кодовое слово ю, длины 1, прочерками в количестве и — 1,.
Тогда каждое из так полученных слон ю, можно рассматривать как код грани размерности и — 1, = и,. То, что грани попарно не пересекаются, следует из префиксности кода. 1.5. 1) Рассмотрим множество всех интервалов Ли, В) таких, что Н б Вги~зр )г б В„" Ог7зр ЛлЯ каждой из () ) )) веРшин ег б В~"„7з~ сУществУет ( ~„7 ) ) веРшин В б В„г„гз~ таких, что о < В. Таким обРазом, / и — )гг/3) 'г число пар (Л, ег) указанного вида, а значит, и число интервалов Ца, г8) рав- Ря.
1Х. Минимизация бувевь х функций п 1 'п — Ги,»31» но () ) )) ( ~ ) ) ). Нетрудно видеть, что все они попарно несравнимы. 2) Аналогично задаче 5.19.1 из гл. П. 1.6. Ц 2. 2) 3. 3) 2. 4) 3. 5) 2. 6) 3. 1.7. Ц 2. 2) 4. 3) 3. 4) 3. 5) 2. 6) 3. 1.8. Ц 2. 2) 1. 3) 1. 4) 2. 5) 5. 6) 4. 1.9. Ц 2. 2) 1. 3) 3. 4) 5. 5) 5. 6) 4. 1.10. 2) Рассмотреть матрицу вила»Р»-»1 — »вЦ, где Р»» . матрица размерности Гп — к+ Ц х Гк — Ц, состоящая сплошь из единиц, а 1„»э» единичная матрица размерности»п — Ге + Ц х»п — й + Ц. 1.11.
Пусть А множество векторов»базисных) линейного»п, 1)-кода. Тогда ~А~ = й и А покрытие. Последнее вытекает из следующих соображений. Пусть утй столбец имеет единицу в»-й координате. Поскольку »-я строка является линейной комбинацией базисных строк, то существует базисный вектор, имеющий единицу в блм разряде. 1.12*. Ц Пусть Л» — семейство всех Ге-элементных подмножеств строк матрицы М.
Лля Р 6 Н» обозначим через н»Р) множество столбцов, не покрытых строками из Р, и пусть й» = (в) ~ иГР) среднее число ген» непокрытых вершин по подмножествам Р из й».. Пусть»' — множество столбцов матрицы М, а рГи) число тех Р из Л», которые не покрывают столбец и, а пГ»») число строк, .покрывающих столбец и.
Тогда й»=( ) ~р»и)=(„) ~(™ )< <и( )ГГ( ) <п(1 — — ) <пе Лля всякого натурального Й имеем 6(М) ( Й+ р». Поэтому, полагая Й = 1»п вп Г т еви = ] — 1п — ~, получаем СГМ) < 1 ~- — 1п —. в в и» 2) Пусть 6» доля тех столбцов матрицы М, которые остались непокрытыми после 1-го шага градиентной процедуры.
Ясно, что 6о = 1. Покажем, что Г»»6». — 6»в») ) в»6»в)Г»». Неравенство равносильно утверждению о том, что на»л -Н Ц-м шаге можно выбрать строку, покрывающую не менее вг»6»)т столбцов. В самом деле, в каждом из п6» непокрытых столбцов содержится не менее в единиц, а число строк не превышает т. Таким образом, 6»» < 6»»1 — в/и»). Отсюда по индукции следует, что 6» (»1 — в,»т) ( е ' д".
Лля всякого натурального й имеем Ь»ЛМ) ( к+ п6». ( к+ пе ' '. Полагая к = ) — 1и ( — в) [, получавЂ.»» 1 т /ив 1 ем требуемое неравенство. 1.13*. Аналогично тому., ках в задаче 1.12, 2) доказывается, что 6» < — *» Г »» <ет»1 — е)(1 — — ) <е-';е ''.
Лалее, полагая Ге=~ — 1п( — )( в 1 т /овец ГП в вп неравенстве ЛгГМ) < к+ п6»м получаем требуемое утверждение. 1.14. На первом шаге градиентной процедуры в покрытие войдет строка, покрывающая не менее п»»р столбцов, и не более п(1 — 1/р) останутся непокрытыми. Если А» множество непокрытых после к-го шага столбцов и ~А» ~ < пГ1 — 1»р)», то на Г)е -~- Ц-м шаге по крайней море одна из строк 404 Ответы, указания, решения покрывает не менее (Ая(/р столбцов.
Отсюда )Агег! < (Аь((1 — 1/р) < < п(1 — 1/р)ььг. Таким образом, )Ая) < гг(1 — 1/р)". Посколыгу Ьг(Р) < < й. + ~Ая ~ при любом натуральном к, то, полагая ] (1п Р)/З1п(1 ') [ получаем утверждение. 1.15. — = — (1обя ( — + 1)). 1.16. Ц Множество 1г' = (Н б В': ОНО, и четное) является (и, Ц-протыкающим и )Х) = 2" . Остается показать, что б(п, Ц > 2" . В силу задачи 1.2 куб В" разбивается на 2" ' 1-мерных граней одного направления. В каждой из них должна присутствовать вершина (и, Ц-протыкающего множества.
2) Нижняя оценка очевидна. С другой стороны, гу = (О, Ц является (и, п — Ц-протыкающим. 3) (В.В. Глаголов.) Указание. Рассмотреть гУ = (Н б В": ОЩ = : — О (шог1 3) ) ипи № = (а б Вп: н(Й) = 3 (шог1 4)). 4) (О.Б. Лупанов.) Нижняя оценка. Заметим, что, для того чтобы веригина Н = (пг, ..., гг„) содержалась в (и — 2)-мерной грани с колом у = = ('Уг, ..., '7 ), в котоРом У,, Тз б (О, Ц, нУжно, чтобы щ = У„о = У . Пусть 1г' С В" —. (и, и — 2)-протыкающее множество и ~гу~ = ти. Рассмотрим матрицу М, строками которой являются векторы из № Из предыдущего следует, что для каждой пары чисел (г, 1), 1 < г < ) < и, и любой пары (а., г), гг, т б (О, Ц, должна найтись строка й = (ог, ..., ег ) такая, что а, = и, о = т. Отсюда вытекает, что любые два столбца матрицы М попарно несравнимы.
Число попарно несравнимых двоичных наборов т г гп длины ги не превосходит...). Отсюда вытекает, что (,, )) > и. , (гп/2/) ' (иг/2 В е р х н я я о ц е н к а. Пусть т наименьшее целое такое, что (= / )) > и. Построим двоичную матрицу М с т строками и п попарно несравнимыми столбцами. Добавим к матрице две строки: 0 и 1. Тогда множество строк полученной матрицы будет (гг, и + 2)-протыкающим. ! гН б) Вытекает из того, что множество 7У = () Вггзгн является (и, й)- =в протыкающим.
6) Если гу является (и, 1)-протыкающим и С вЂ” г-мерная грань куба В", то ггг О С является (г, 1)-протыкакндим. Отсюда и из задачи 1.2, Ц вытекает требуемое неравенство. 7) Неравенство вытекает из задачи 1.12, если положить ги = 2", в = 2, п ()2 — Я 1.17. Ц 1+ 1. 2) Положим ~(Мтюг) = р„,г...г. Утверждение вытекает из того., что 1 и — 1-~-1 Г йд„ьг. г > пд„г г г г г, р„г. г целое и д„гпг ь г г г = ] 3) Ясно, что 4(М„,„цг) > 1, поскольку при любом выборе 1 векторов Нг, ..., Нг из В,", г можно подобрать вектор /3 б В,", не покрываемый ни одним из выбранных 1 векторов. Это можно сделать, выбрав по одной нулевой координате в каждом из векторов йг,..., Н„и положив их равными 1 в векторе /3.
Если жс выбраны 1+ 1 векторов из В'„' г, так, что 405 Гл. 1Х. Минимизация булевых функций множества нулевых координат попарно не пересекаются, то все векторы из Вт" оказываются покрытыми. 4) Нижняя оценка вытекает из мощностных соображений: число покрыт'и1 Гттз ваемых столбцов равно (! ), а каждая строка покрывает (1) столбцов. Верхняя оценка вытекает из задачи 1.12. 5) Верхняя оценка. Пусть и =4!! — 1)+г, 0 < г < ! — 2. Разобьем и, кттординат на ! — 1 блоков так, что два любых блока различаются по мощности не большо, чем на 1. Всего имеется г блоков мощности й+ 1, ! — 1 — г блоков мощности т!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
