Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 46
Текст из файла (страница 46)
Индуктивный переход. Пусть корень плоского помеченного дерева Т имеет степень, равную й. Пусть Т„Твч ..., Т» ветви корневого дерева, пронумерованные слева направо. Если кореньдерева Т помечен буквой е, а Г»(а„ Ь»), Гз(аз, Ьг), ...., Ге(а», 6») сети, сопоставленные соответственно ветвями Т», Тз, ..., Т» (пустой ветви сопоставляется однореберная сеть), то дереву Т сопоставляется сеть, являющаяся суперпозицией сети Г' и сетей Г,(а„Ь,) (» = 1, ..., Й). 15 Г. П. Гаврилов, А. А.
Свпожевко 226 Гл. 17. Графы и сети При этом сеть Г,(ап Ь,) подставляется вместо 1-го ребра сети Г"„. Таким образом, сеть Г, изображенная на рис. 6.14, а, соответствует дереву Т (см. рис. 6.14, б), но не дереву Т', изображенному на рис. 6.14, г. (Соответствующая сеть Г' изображена на рис. 6.14, в.) При изображении сетей будем располагать полюс а слева от полюса Ь, а ребра внешней соти Г'„считать упорядоченными слева направо; полюса а,, Ь, внутренних сетей Г,(а„Ь,) также считаются упорядоченными. Если корень помечен буквой р, а Гз(аы Ьз); Гя(аз, Ьз), ..., Гь(аю Ьь) сети, сопоставленные соответственно ветвям Т„ Тз, ..., Ть, то дереву Т сопоставляется сеть, являющаяся супсрпозицией сети Г~ь и сетей Г,(а, Ь,) (1 = 1, ..., Й) . При этом сеть Г1(ао Ь,,) подставляется вместо 1-го ребра сети Г". При изображении мы располагаем первую подсеть слева, затем располагаем вторую подсеть и т.д.
Соглашения об упорядоченности полюсов и ребер сетей позволяют однозначно с точностью до изоморфизма строить я-сети по их диаграммам расщепления. Вершина сети, отличная от полюса, называется внутренней. Вершина о зависн7а озп вершины и, если всякая цепь, соединяющая полюса и проходящая через о, проходит и через и. Вершины и и о эквивалентны, если о зависит от и, и зависит от о. Вершина о слабее вершины и, а вершина и сильнее вершины о, если о зависит от и, но не эквивалентна ей. Вершина о называется минимальной, если она не слабее никакой другой внутренней вершины сети. Вершина о называется разделяющей, если через нее проходят все цепи, соединяющие полюса. Пример.
В сети, изображенной на рис. 6.15, а, вершины 2, 3 зависят от 1 и 4 и слабее их, вершина 2 эквивалентна вершине 3, 1 2 Ь а Ь а б Рис. 6.16 вершина 5 сильнее вершины 4, вершины 6 и 7 являются минимальными и разделяющими и эквивалентны друг другу. 3.16. 1) Построить все попарно неизоморфныс сильно связные двухполюсные сети с 3 ребрами. 2) Найти число попарно неизоморфных сильно связных двухполюсных сетей с 4 ребрами. 3.17. 1) Для каждой из сетей, представленных на рис. 6.16, указать тип разложения.
227 7'у. яеревея а вепш а Ь а Ь Ь а Ь а Ь Рис. 6.16 2) Найти внешнюю сеть и внутренние сети расщеплений для сетей, представленных на рис. 6.16. 3.18. 1) Показать, что в каждой неразложимой сети, .имеющей более двух ребер; а) степень каждого полюса но меньше 2; б) степень каждой внутренней вершины не меньше 3.
2) Найти число попарно неизоморфных неразложимых сетей с пятью ребрами. 3.19. Для сети Г, представленной на рис. 6.15, 6, указать: 1) две пары вершин (и, с) такие, что и слабее с и вершины и, с неэквивалентны; 2) две пары эквивалентных вершин (и, и); 3) пару вершин (и, н), не зависящих друг от друга; 4) все разделяющие вершины; 5) все минимальные вершины. 3.20. 1) Показать., что если неразложимая сеть имеет п > 3 вершин и т ребер, то 3п < 2ти+ 2 < п(п — 1). (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, такие, что В = В(... В,. Петле (Л, Л) припишем слово В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
