Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 46
Текст из файла (страница 46)
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,. 011, 100, 2100, 101210, 001210); 6) С = (01, 011, 100, 2100, 10110, 00112); 7) С = (01г 12, 021, 0102, 10112); 8) С = (01, 12, 012, 111, 0102, 10112, 01112); 9) С = (01, 12, 012, 0102, 020112); 10) С = (01, 1О, 210, 121, 0210, 0112); 11) С = (01, 10, 210, 201, 0210, 011022, 2221); 12) С = (01г 10, 210, 201, 0210, 011022, 221); 13) С = (01, 10, 210, 201, 0210, 011022); у' 1. Аафавипи~ое кодирование 233 14) С = (01, 12, 011, 01210, 20120, 2011220); 15) С = (01, 12, 011, 01210, 201120, 2011220); 16) С = (000, 0100, 10, 1001, 0010010); 17) С = (01, 12, 01121, 21201). 1.3.
Выяснить, является ли слово Р в алфавите (О, 1, 2) кодом сообщения в кодировании, задаваемом схемой 1 — > 10 2 — > 12 Е: 3 -+ 012 4 †> 101 5 о 2100 Если да,то выяснить, является ли Р кодом ровно одного сообщения: Ц Р = 10120121012100; 2) Р = 1012101201210012; 3) Р = 0121001210201; 4) Р = 120120121001210: 5) Р = 1010122100; 6) Р = 12101210012; 7) Р = 101212101012; 8) Р = 1010012100101.
1А. Выбрать максимальное по числу элементов подмножество В множества А с условием, что двоичные разложения наименьшей длины чисел из В представляют собой а) префиксный код; б) однозначно декодируемый код: Ц А = (1, 5, 6, 7, 12, 13, 17): 2) А = (1, 3, 6,8,10,13,19,33,37); 3) А = (2, 6, 7, 9, 12, 15, 18, 35, 36, 37); 4) А = (1, 2, 5, 8, 9, 10, 13, 15); 5) А = (2, 3, 7, 8, 11, 12, 13, 14): 6) А = (3, 5, 6, 9, 10, 13, 17), :7) А = (1, 2, 5, 8, 9, 12, 13, 14); 8) А = (5, 6, 7, 8, 9, 10, 11, 12, 13); 9) А = (4, 6,. 7, 10, 13., 15, 20, 23, 25); 10) А = (5, 7, 9, 10, 12, 14, 17, 23, 24). 1.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
