Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 47
Текст из файла (страница 47)
(1) 2) Показать, что при четных п первое из неравенств (1) достигается. 3.21. Показать, что всякая разделяющая вершина сети минимальна. 3.22. Показать, что всякая разделяющая вершина сети, смежная с обоими ее полюсами, минимальна. 3.23. Пусть все вершины сильно связной соти Г минимальны. Выяснить, может ли сеть Г быть; 1) в-разложимой; 2) р-разложимой; 3) Н-разложимой. 3.24.
Пусть все внутренние вершины сети Г являются минимальными, сеть Г не является ни р-,ни в-разложимой,число Ь вершин сети больше 3 и в Г нет кратных ребер. Показать,что Г является Н-сетью. Рис. 6.17 3. 25. Показать неразложимость сети, представленной на рис. 6. 17. 3.26.
Пусть С двухсвязный граф без кратных ребер, степень каждой вершины которого не меньше 3. Верно ли, что, выбирая 16* 228 Гж 17. Грифы и сети произвольные две вершины в качестве полюсов, мы получаем неразложимую сеть? 3.27. Сколько попарно неизоморфных неразложимых сетей можно получить, выбирая в п-мерном единичном кубе две вершины в качестве поляков? 3.28. Пусть Г сильно связная сеть без кратных ребер и Я(Г) множество всех вершин сети п, не являя>шихся минимальными. Ц Верно ли, что если в сети Г соединить каждую вершину п множества Я(Г) с каждым из тех ее полюсов, с которыми е не соединена ребром, то получится неразложимая сеть? 2) Верно ли, что если в сети Г соединить каждую вершину п ровно с одним из тех ее полюсов, с которыми и не соединена ребром, то получится неразложимая сеть? 3) Верно ли утверждение и. 1) при условии, что Г является Н-разложимой сетью без кратных ребер? 4) Пусть сеть Г является Н-разложимой сетью без кратных ребер.
Достаточно ли для получения из нее неразложимой сети соединить каждую вершину е из Я(Г) с одним из полюсов, с которыми п не смежна? 5) Доказать, что разложимая сеть Г может быть сделана неразложимой добавлением ребер тогда и только тогда, когда она не имеет кратных ребер, не имеет ребер, соединяющих полюса, и обладает по меньшей мере четырьмя вершинами. 6) Указать разложимую сеть с наименьшим числом ребер и вершин, которую нельзя сделать неразложимой с помощью замены сетей вида Г" и Гз на ребра. 3.29.
1) Пусть в сильно связной сети Г имеется ровно одна минимальная вершина и не менее трех ребер. Доказать, что сеть Г является либо р-, либо е-разложимой. 2) Пусть в сильно связной сети Г, имен~щей не менее трех ребер, все минимальные вершины эквивалентны между собой. Доказать, что сеть Г либо р-, либо е-разложима. 3.30. 1) Доказать, что если в Н-сети удалить вершину вместе с инцидснтными ее ребрами, то получится связный граф. 2) Верно ли утверждение 1) для Н-разложимых сетей? 3.31.
Пусть С = ('й, И~, Х) связный двудольный граф, степень каждой вершины которого не мсныпе 2. Пусть Г(п, Ь) - ость, построенная путем добавления вершин а и д в качество полюсов и соединения ребром каждой вершины множества И с полюсом а и каждой вершины множества И~ с полюсом Ь. Доказать, что Г(а, Ь) является Н-сетью. 3.32. Для каждой из я-сетей, представленных на рис. 6.16, а, б, г, д, построить диаграмму расщепления. 3.33. Для каждой из диаграмм расщепления Т(Г), представленных на рис. 6.18, восстановить сеть Г. Глава Ъ'П ЭЛЕМЕНТЫ ТЕОРИИ КОПИРОВАНИЯ З 1. Алфавитное кодирование. Критерий однозначности кодирования Пусть й = (ам аг, ..., а„) алфавит.
Конечная последовательность символов из й называется словом в алфавите й. Через Я(й) будет обозначаться множество всех слов в алфавите й. Пусть й и З два алфавита. Однозначное отображение Е произвольного подмножества М С 5(й) на подмножества С ч В(З) называется кодированием. При этом слова из М называются сообщениями, а их образы — кодами сообщений. Множество С называется кодом мнохсества сообщений М. Алфавит й называется алфавитом сообщений, а алфавит гэ — кодирующим алфавитом. Кодирование Е (или код С) называется взаимно однозначным или однозначно декодируемым, если каясцый код сообщения является кодом ровно одного сообщения.
Пусть задано отображение Х букв алфавита й в множество В(З) вида аг — э Вг аг — + Вг а„— > В„ Кодирование Ен. Я(й) -э о'(З), удовлетворяющее свойствам: 1) Рх(аг) = В; (г = 1, ..., г); где под произведением слов АВ понимается приписывание слова В справа к слову А, называется алфавитным кодированием, зпдаваемым схемой Х. Множество кодовых слов ~Вы Вг, ..., В„) будет обозначаться через С(Х) и называться кодом алфавита в схеме Х. Если В = В,Вг, то Вг называется префиксом, а Вг суффиксом слова В. Префикс (суффикс) слова В называется собственным, если он отличен от пустого слова (обозначаемого через Л) и от самого слова В. Длиной слова называется число букв в нем. Схема Х (код С(Х), кодирование Ех) обладата свойстлвом префикса, если для любых слов В, и В (г у: у) из С(Х) слово В, не является префиксом й'1.
Алфавитное кодирование 231 слова В . Код Я(Х), обладающий свойством префикса, называется еще ар еф иконы и ко до и. Префиксный код С(Х) называется полным, если для каждого слова Р в кодирующем алфавите справедливо одно из следуюгцих утверждений: 1) Р является префиксом (не обязательно собственным) некоторого слова из С(Х); 2) некоторое слово из С(Х) является собственным префиксом слова Р. Один из алгоритмов распознавания однозначности декодирования заключается в следующем. Пусть С(Х) алфавитный код. Пусть Я( множество слов (1, обладающих следующим свойством: слово,9 является собственным суффиксом некоторого кодового слова В и собственным префиксом некоторого кодового слова В(, отличного от В, и, кроме того, не является кодовым словом кода С(Х).
Положим Я = = Я( 0 (Л). Сопоставим коду С(Х) ориентированный граф Сг, воршинами которого являются элементы множества Я и в котором дуга, ведущая из вершины а в вершину (( ((3 у'. -а)., присутствует тогда и только тогда, когда существует кодовое слово В и последовательность Р = В„, ..., В,, кодовых слов такие, что В = оВл ...В(,((.
Приэтом последовательность Р может быть и пустой, если ни одна из вершин о, (з не совпадает с Л. Луге, ведущей из о в (3. припишем последовательность Р. Дуги вида (о, м), ведущие из сь в об рассматриваться не будут, за исключением случая а = Л. Луга (петля) из Л в Л присутствует в графе Св тогда и только тогда, когда существуют слово В и последовательность кодовых слов Р = В(, ..., В„где в > 2, такие, что В = В(...
В,. Петле (Л, Л) припишем слово В. Справедливы слодующио утверждения. Теорема 1 (Ал.А. Марков). Алфавитный код С(Х) является однозначно декодируемым тогда и только тогдц когда в графе Сг. отсутствуют кон(ауры и петли, проходяи(ие через вершину Л. Теорема 2 (неравенство Макмиллана). л(ля всякого однозначно декодируемого кода в а-буквенном коднрующем алфави<не с набором длин кодовых слов 1(, 1з, ..., 1„выполнено неравенство ь ~1 <1. ,=1 Теорема 3.
Для всякого однозначно декодаруемого кода С(Х) в кодируюи(ем алфавите З с набором длин кодовых слов !(, 1з....., 1„ можно построить префиксный код С(Х') с тем же набором длин кодовых слов и в том же кодирующем алфавите. Следствие. Пусть 1(, 1з, ..., 1, натуральные числа п(акие, лпо ~~(( * < 1. Тогда существует префиксный код в у-буквенном кок — л 1=1 дирующем алфавите с набором длин кодовых слов вида (1(,1з, ..., 1,).
Пример !. Выяснить, является ли кодирование Рп взаимно однозначным, если С(Х) = (а, аЬ, саЬ, Ьаас). Если да, то указать слово, декодируемое двумя способами. 232 Гл. И1. Элементы теории кодирования а Ьс е Ь л'~ Л аЬ Ь еа аЬ в Рне. 7.1 Решение. Граф Сх показан на рис. 7.1, а. Существует контур, проходящий через вершину Л. Выписывая слова, приписанные вершинам и дугам контура, получаем слово, декодируемое неоднозначно: г1 г — 1 г — 1 а баас аЬ = аЬ а а саЬ.
е лел еле Пример 2. Та же задача для кода С(Е) = (а, Ь, аглЬ). Решение. Граф Св показан на рис. 7.1, б. Граф содержит петлю )Л, Л). Код не является однозначно декодируемым. Слово, декодируемое неоднозначно, есть: ааЬ = а а Ь. ел гл ел Пример 3. Та же задача для кода С(Е) = (саЬ, аЬс, Ьсс, аЬса, аЬсЬ). Решение.
Граф Св показан на рис. 7.1, в. Контуров и петель, проходящих через Л, нет. Код является однозначно декодируемым. 1.1. Выяснить, обладает ли код С свойством префикса: 1) С = (а, Ьа, ЬЬ, ЬЬЬа); 2) С = (аЬ, ЬЬ, Ьа, ааЬ); 3) С = (ас, с, ЬЬ, аЬс, Ьас, аЬЬ, аЬсЬ); 4) С = (а, Ьа, саЬ, асЬ); 5) С = (а, Ьа, ЬЬа, ..., (Ь)на, ...); 6) С = (а„Ьае ..., с(а)".....). 1.2. Выяснить, является ли код С с кодирующим алфавитом (О, 1, 2) однозначно декодирусмым: Ц С = (01, 201, 112, 122, 0112); 2) С' = (001,. 021, 102, 201, 001121, 0101210Ц; 3) С = (О, 01, 0010001001); 4) С = (20, 0Р202, 22, 2001, 2012010, 1020ПЛ, П12); 5) С = 01,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
