Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 81
Текст из файла (страница 81)
Заметим, что Л(п, г, й) = /(по г+ 1, й)//(п, г, й) = (й — г) х х 2 '/(г -!- 1) и что Л(п, г, й) > 1 прн й > г > О. Следовотепьнсз /(п, г. й) возрастает по г. Отсюда шах/(п, г, й) = /(п, й, й) = (й)2 ж, пцп/(п, г, й) = 2(„). 5.25. 1) 2"т'/пз если [!обг и) > !обг(п — 1обг и), (2" /п) (1+ 2г ), если 1о г(п — !обг п) ( (1обг п) ~ ()о8,(п — 1обг п — !обг 1обг и), 2" !"кг"!, если (!08 и) < !обг(гг — 1об, и — !08 )обо п). д(п) 6 — ог — Ь вЂ” Ьг 3) чг1 -6 Ь вЂ” 1.
Заметим, что аг — ао = — ао = < О и аг = 2 2 Ь вЂ” Ьг Ь вЂ” ог Ь -!- Ьг аг — Ьг >О,т.е. О<аг<ао Пшгое, аг — аз= '-!- = ' > 2 2 2 2 Ь вЂ” аз~ Ь аз > О, а аг — ао = — — = — — ' < О. Отсюда аг < аг < ао. Вообще 2 2 2 г г а„— о„+г а„тг — о„= . Отсюда по индукции следует, что (аг ) возрастает 2 и а„г < ао при всех п > 1, (аг„ег) убывает и аг зл > аы Следовательно, существуют пределы с = 1пп ог и Н = 1пп аготы Переходя к пределу в рекуррентном соотношении, получаем с = (Ь вЂ” оа) и г! = (Ь вЂ” сг).
Отсюда (с — е!)(2 — с — д) = О, а посхольху с < Ь/2 < 1/2 и д < Ь/2 < 1/2, то 2 — с — е! > О; следовательно, с = д. Отсюда с = з/1+ Ь вЂ” 1. 5.21. 1) С помощью соотношений (3) и (4) получаем, что аз = 9/128, а4 < 11/128. При п > 3 неравенство (4) можно переписать в виде 17 1 323 а„тг < — + а„ ( — + а„) . 1024 1024 400 Отиветы, указания, решения Функция !(п, й) как функция действительного аргумента й выпукла вниз, /1окг иМ пРичем минимУм достигаетсЯ пРи й = й' = 1обг (и — !обг и+ О ( ' )!г!. Положим йо = (!об и]. Очевидно, что либо д(и) = у(п, йо), либо д(п) = = Д(и, йо — Ц, Лля нахождения д(и) нужно выбрать минимум из )(п, йо) )(~, йо — Ц.
ПУсть э) !обг и > йо > 1обг(и — !обг и). Тогда ~(и, йо — Ц = 2" о~' -!- 2 2"~'гги, Пусть 6) !обг(гг — !обг и) ~ )йо > !обе\и — 1обг и — !обг !окг и). Тогда 2" гоо 2" гоо — мог~ — < ог )З 2ото Д(и, йо) — +2 = — (1+2 ), Д(и, йо — Ц и и и Следовательно, д(и) у(п, йо). Пусть в) йо < !обг(гг — !ояг п — !обг !ояг и). Тогда ((п йо) 2 — о ! 2г" 2» — ьо 2мег о — ео ~(п, йо — Ц ~ 32' "+' > Д(п, йо).
Отсюда у(и, йо) д(п) = 2" "'. 2) д(п) 2" (2 ~"1+ 2 Ш1), где о(и) = 1обг п — (!оя п), если а(гг) < < Ц2, д(и) 2" (2' 60 + 2" 00 ~), если п(п) > 1/2. 6.1. Ц Граф с и помеченными вершинами без петель и кратных ребер полностью определяется множеством ребер. Поэтому число таких графов равно числу подмножеств ( ) — — элементного множества, т.е, равно 2 (2) 6.2. Ц 2(г), еиз т 2) ( ).
Число равно числу выборок из иг возможных дуг (включая (,т)' петли) по т. 6.4. Коли р(О) — число различных помеченных графов из 'бэ, изоморф- ных графу О, а оп'„множество всех неизоморфных и-вершинных графов, то !'Й„( < и! !'й*„!, поскольку р(О) < и.'. 6.5. Ц Воспользоваться результатом задачи 6.1, 2) с учетом того, что число т, ребер связного и-вершинного графа без кратных ребер и петель удовлетворяет неравенствам и — 1 < т < ( ).
2) Воспользоваться тем, что (('г) ) < (( г ) ), (( 'г ) ) < т т (!( +ц) 6.8. Ц См. рис. 0.8.1. 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 — — ) <е-';е ''.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
