Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 74
Текст из файла (страница 74)
Возможны следующие наборы степеней вершин у графа Сгт (4, 3, 3, 2) и (3, 3, 3, 3). 2.18. Рис. 6.1: те(С) = 3, ~'(С) = 3. Рис. 6.3: ц(С) = 3, те'(С) = 4. Рис. 6.5, а: с(С) = 3, тс'(С) = 3. Рис. 6.5, б: х(С) = 3,;~'(С) = 3. Рис. 6.6, а: зс(С) = 3, у'(С) = 4. Рис. 6.6, б: с(С) = 2, те'(С) = 4. Рис. 6.6, а: у(С) = 4, у'(С) = 5. 2.19.
Ц К(В") = 2, ~~'(В") = и. 2) у(К„) = и; если и нечетно, то у'(К„) = и, если же и четное, то у~(К ) = и — 1. 3) тс(К,„,„) = 2, ~'(К,„) = шах(тп, и) = и. 2.21. Указание. Применить индукцию по числу вершин. 2.22. У к а з а н и е. Можно применить индукцию по числу вершин. 2.23. Указание. Применить индухдию по числу вершин. 3.1. а) 0101001011. 6) 00010010111011. в) 0000101110010111. г) 0000110100101111, д) 0010110100010111. 3.2.
См. рис. 0.6.1. 3.3. Ц, 4), 6) Ла. 2) Нет, нарушено свойство 2. 4) Нет, нарушено свойство 1. 5) Нет, нарушено свойство 2. 3.4. Ц Классы разбиения имеют внд Кт = (от, от)., Кг = зтог, оз, Нз). 3.5. Провести индукцию по числу ребер. 3.6. Ц Число деревьев с и ребрами не превосходит числа кодов, которые являются двоичными векторами длины 2и.
2) Учтено, что число единиц в коде дерева равно числу нулей. 3) Учтено, что первая координата кода есть О, а последняя 1. 362 Ответы, указания, решенця 3.8 — 3.10. Провести индукцию, опираясь на индуктивное определение корневого дерева. 3.11. а) г(Т) = 2, Ю Т) = 2, Гэ(Т) = 3. 6) г(Т) = 1, 11(Т) = 2, тг(Т) = 4. в) г(Т) = 1, КТ) = 3, Г//Т) = 5. 3.13. Следует из задачи 3.12, 5). 3.14. Указание.
Провести индукцию по величине радиуса дерева. 3.15. Ц Например, простой цикл длины 21 + 1. 3.16. Ц См. рис. 0.6.2. 2) 15. 3.17. Ц На рис. 6.16, б, г разложение е-типа; на рис. 6.16, а, д разложение р-типа; на рис. 6.16, е, е — разложение Н-типа. 2) На рис. 0.6.3, а представлена внешняя сеть Г/(а, Ь) е-расщепления гъ/ /, -''— - '/ з — г/ а б е г д Рис. 0.6.2 Рис. 0.6.3 сети Г(а, Ь), изображенной на рис. 6.16, а. На рис. 0.6.3, б, е, г представлены внутренние сети е-расщепления. 3.19.
Ц Например, (2/ 5), (3/ Ц. 2) (1/ 5), (3/ 4). 3) Например, (2/ 6). 4) (1, 5). 5) 11, 5). 3.20. Ц Первое из неравенств вытехает из того, что в неразложимой, сильно связной сети каждая внутренняя вершина имеет степЕнгэ не меньшую 3, а каждый полюс имеет степень, не меныпую 2. Второе неравенство следует из того, что неразложимая и-вершинная сеть не имеет кратных ребер, а следовательно, число ребер меньше, чем у полного графа с и вершинами. 3.21. Через разделяющую вершину проходят все цепи. Поэтому она не может зависеть ни от какой неэквивалентной ей вершины.
3.22. Через вершину е, смежную с полюсами а, Ь, проходит цепь из ребер (а, э), (е, Ь). Эта цепь не проходит через какую-либо другую внутреннюю вершину СЕти. 363 Гл. РВ Графы и сшви 3.23. 1) Да. Рассмотреть суперпозицию, где внешней сетью является сеть Г' (ш > Ц, а внутренние име/от вид Ге (к > 1). 2) Ла. Рассмотреть суперпозицию, где внешняя сеть есть сеть типа Г" (ш > 1), а внутренние имеют вид Го (ь > 1). 3) Па. Рассмотреть суперпозицию, где внешняя сеть есть Н-сетгн а внутренние сети имеют вид Г'„' (к > Ц. 3.26.
Неверно. См., например, сотен граф которой является полным и-вершинным (и > 3) графом. 3.2Т. л — 1. При выборе в В" в качестве полюсов вершин, находящихся на расстоянии 2, 3, ..., п, получаем неразложимые, попарно неизоморфные сети. 3.28. 1) Неверно, см. рис. 0.6.4/ а. 2) Неверно, см. рис, 0.6.4, б. 3) Верно. 4) Па, достаточно. 6) См. рис.
0.6.4, о. 3.3рь 1) Если удалении некоторой вершины из сети последняя становится несвязной, то удаляемая вершина является разделяющей. Таких вершин в Н-сети нет. 2) Верно. 3.31. Указание. Показать, что каждая внутренняя вершина полученной сети минимальная., и использовать ответ к задаче 3.24.
3.32. См, рис, 0.6.5. З.ЗЗ. См. рис, 0.6.6. 3.38. Рангом оеришны о сети Г(а, Ь) назовем расстояние о от а. Ребро сети, соединяющее вершину ранга г — 1 с вершиной ранга г, назовем а Ь а 6 а Рис. 0.6.4 Рис. 0.6.5 Рис. 0.6.6 ребром уровня г. Заметим, что удаление всех ребер одного уровня, не превосходящего 1, делает сеть несвязной. Поэтому число ребер одного уровня не меньше 1.
Число уровней в сети длины 1 не меньше 1. Отсюда вытекает утверждение. 364 Ответы, указания, решения Глава УП 1.1. Ц, 3), 4), 6) Код С не обладает свойстном префикса. 2), 5) Код обладает свойством префикса. 1.2. Ц Код не является однозначно декодируемым. Неоднозначно декодируемое слово: 01122 01. 2)., 4), 5), 8) Кол однозначно декодируемый. 3 0010001001. 6) 01101100112100. 7) 010210112 ) 1.3.
Ц, 2), 4) Р является кодом одного сообщения. 3), 8) Р не является кодом сообшения. 5) — 7) Р является кодом более чем одного сообшения. 1.4. Ц Р е ш е н и е. Пусть С(А) множество двоичных разложений чисел из А; С(А) = (1, 101, 110, 111, 1100, 1101, 1000Ц. Вычеркнув из С(А) слова 1 и 110, получим префиксный код.
Вычеркиванием меньшего числа слов обойтись нельзя. Таким образом, для задачи а) В = А)(1, 6). 2) а) В = А)(1, 3, 6, 8); б) В = А)(Ц. 3) а) В = А1(2, 6, 7, 8, 9); б) В = А)(2, 7). 4) а) В = А)(1, 2, 5); б) В = А)(1, 2). 1.5. Ц 1201012. 2) 0101010101010101010101010 3) (ОЦН 400. 4) Если Ь = 4, то 01010101, если Ь > 4,то 01010101010. 5) 0(10)~1 *"1, где Н(тв Ь) наименьшее общее кратное чисел т и Ь.
6) (1100)", если й = Зв, в = 1, 2...; в противном случае решений нет. 7) (10Ц~О для всех Ь = 1, 2,... 8) (110)Я (Ь = 2в). 1.6. Ц с = (а, Ьа, ЬЬа, ЬЬЬ). 2) с = (а, Ьа, ЬЬЬа, ЬЬаЬ, ЬЬЬЬ, ЬЬаа). 3) с = (аЬ, Ьа, ЬЬа, ЬЬЬ, аааа, аааЬ, ааЬл, ааЬЬ). 4) с = (аа, аЬ, Ьа, ЬЬаа, ЬЬаЬ, ЬЬЬа).
1 1 1 1 9 1.7. Ц Нет, гак как — -~- — 4- — -~- — = — > 1. 2 4 4 8 8 1 1 1 1 2) Па, так как — 4- — 4- — 4- — ( 1. 3) Па. 4) Па. 8 9 9 27 1.8. Ц Воспользуемся неравенством Макмиллана. Пусть 1, — длины ~сз ~с~ ч 1 х 1 (С( кодовых слов кода С. Тогда яз — > кз — = — > 1. Код но может быть 26 2 2" ,=з однозначно декодируемым. 2) Нет, так как если бы код С был префиксным, то он был бы однозначно декодируемым. 1.9. Пусть код С(В) с набором длин кодовых слов 1ы 19, ..., 1„нс является деходируемым.
Тогда в графе Сп существует контур или петля, проходящие через вершину Л. Число вершин (и дуг) в контуре не больше, чем в графе Св, н, следовательно, не больше 14- ~ (1, — Ц = 1з' — т+ 1. =-1 Збб Гл. (т11, Элементы теории кодирования Идя вдоль контура от вершины Л, рассмотрим слова, приписанные паре (дуга вершина, являющаяся концом дуги).
Ясно, что суммарное количество букв для каждой такой пары не превосходит ! и может быть равно 1 только для первой пары. Отсюда и вытекает утверждение. 1.10. Пусть С вЂ” алфавитный код с набором длин кодовых слов !т, !з... пцп 1, = Ь, шах !, = 1, ~ !, = Лт. Из предыдущей задачи вытекает, =т,. т=т, что если код С не является однозначно декодируемым, то существует сло- во в кодирующем алфавите длины не больше 1+ (Лà — г+ Ц(! — Ц < Лт!.
Тогда в алфавите сообщений длина соответствующих слов будет не боль- ше Лт!/Гй. 1.11. Ц Пусть ! максимальная из длин слов в М. Тогда для числа г 4+ 4 слов в М имеем т < ~ ~т/' = . Отсюда 1 > ! он (9 + г(д — Ц ) — 1. 4 †=. т 2) Доля Ь, слон длины, не превосходятцей ! = (1 — е) (обо(1 + г(д — Ц), не больше Ч Ч Если г=2, 9=2,то Ь,« — <( — ) 2 2 2 тз/ Если г>2, тГ)2и г ° д>4,то г(д — Ц)3 и (4) 1.15. Ц Утверждение вытекает из результата задачи 1.9. 2) Указание. Рассмотреть код С(Е) = (а, (аЬ)ьт', (Ьа)~тз) (Ь ) Ц.
Убедиться,что единственный контур в Сш проходящий через Л,проходит последовательно через вершины (Ьа) тЬ, а(Ьа)' (т = 1, ..., Ь + Ц, а ГР соответствующее этому контуру слово имеет вид (аЬ) ~ ~ а. Зтптп 2.1. Ц, 2) Например, С = (О, 10, ПО, 111). 3) Например, С = (ООт 01, 10, 110, 11Ц, 2.2. Ц Например, С = (а, Ь, са, сЬ, сс). 2) Например, С = (а, Ь, са, сЬ, тта, ссЬ, ссс). Г1 1 1 1 1 14 2.3. Ц Например, Р = ( —; —; —; —; —; — т; оптимальным является ! 2' 4' 8' 16' 32' 32 код С = (О, 10, 110, 1110, 11110, 11111).
Р е пт е н и е. Проведем редукцию длин (1, 2, 3, 4, 5. 5) — т (1, 2т 3, 4, 4) 4 — т (1, 2т 3, 3) — т (1, 2, 2) 4 (1, Ц. Двоичный код с набором длин (1, Ц, очевидно, существует и является единственным и оптимальным при лю- /1 1т бом распределении вероятностей, например, при Г = (-; -/!, С = (От 1).
2 2 Проводя с набором Р преобразования, соответствующие переходу от набора длин (1, Ц к исходному, и деля всякий раз соответствующую вероятГ1 1 1 1 1 1 ность появления слова пополам, приходим к Р = ( †; †; †; †: †; — т 2 4 8 16' 32 32 и С = (О, 10, 110, 1110, 11110, 11111). 366 Ответы, указания, решения 2) Например, Р = (0,2; 0,2: 0,2; 0,2; 0,2); оптимальным является код С = (00, 01, 10, 110, 111). Г1 1 1 1 1 1 1л 3) Например, Р = ( —: —; —; —; —; —; — 1, С = (00, 01, 100, 101, 4 ' 4 8 16 16 16 16 1100, 1101, 1110, 111Ц. Г1 1 1 11 5) Например, Р = ( —; —; —; — 1., С = (а, Ь, са, сЬ). 3 3 6 6 Г1 1 1 1 1 1 1 11 10) Например, Р = ( — —; —.
— —; — —; — ~, С = (а Ь, са, сЬ, сс, сГГ 8 8 8 8 8 8 8 8 4а, ГГЬ, ГГс, ГЫ). 2.4. Ц, 3), 4), 8) Код оптимален. 2)., 9), 10) Код не оптимален. 2.5. а) Леревья 2), 4), 8), 10) являются насыщенными, остальные не являются насытденными. б) Леревья 1), 2), 4), 8), 10) могут являться остовами оптимальных деревьев, остальные не могут. 2.6. 1) Утверждение верно. Всякий двоичный оптимальный код является полным. 2) Вообще говоря, утверждение неверно (см. задачу 2.5, б), 1)). 3), 5) Утверждение верно.
4) Вообгце говоря, неверно (см. задачу 2.5, б), 1)). б) Утверждение верно. Показать можно индукцией по числу концевых вершин. 2.7. 1*) Пусть С полный д-значнгяй код с длинами кодовых слов Л. (1 = 1, ..., т). Пусть Л = ГпахЛ,. Из полноты кода С следует, что каждое слово длины Л в алфавите В имеет префиксом (не обязательно собственным) некоторое кодовое слово. Число слов длины Л, имеющих префиксом слово ш, длины Л„равно 9~ л*. Если ш, и ш -- два кодовых слова, то множества Вл(ш,) и В (ш ) слов длины Л в алфавите В, имеющих префиксом л — л, л кодовые слова ш, и иГм не пеРесекаютсЯ.
Отсюда ял д ' = д, что и 1< <ы требовалось доказать. 2) База индукции - - двоичный оптимальный код с двумя сообщениями. Индуктивный переход осуществляется с помощью теоремы редукции. 3) Лля 6 ) 2 утверждение, вообще говоря, неверно. Пример: д = 3, Г1 1 1 11 Р = [ —; —; —; — 1, С = (а, Ь, са, сЬ). Код С оптимальный, но не полный, 3 3 6 6 тах как 3 ' -~- 3 ' + 3 + 3 = 8/9 < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
