Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 74
Текст из файла (страница 74)
Через вершину е, смежную с полюсами а, Ь, проходит цепь из ребер (а, э), (е, Ь). Эта цепь не проходит через какую-либо другую внутреннюю вершину СЕти. 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. 2.8. Если для некоторого кодового слова ш максимальной длины 1 не найдется слова, отличающегося от ш последней буквой, то, нс нарушая прсфиксности кода, можно заменить слово его префиксом длины 1 — 1, что противоречит оптимальности кода. 2.9. Указание. См. задачу 2.8.
2.10. 1), 4), 6) Нет, см. задачу 2.9. 2), 7), 8) Нет. Нарушено неравенство Макмиллана. 3), 5) Оптимальный ход сугцествует. 2.11. 1), 3), 5), 7), 9) Не существует. 2), 4), б), 8), 10) Существует. 2.13. 1) Указание. Лостаточно убедиться, что почти равномерный код можно построить в результате алгоритма Хаффмена. 367 Гл. 171.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
