close

Вход

Забыли?

вход по аккаунту

?

1544.Дискретная математика Ч 2 Башкин М А

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
Кафедра компьютерной безопасности
и математических методов обработки информации
М. А. Башкин, О. П. Якимова
ДИСКРЕТНАЯ МАТЕМАТИКА
Часть 2
Сборник задач
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по направлению
Математика и компьютерные науки,
специальности Компьютерная безопасность
Ярославль
ЯрГУ
2013
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 519.854(076.1)
ББК В174я73-4
Б 33
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2013 года
Рецензент
кафедра компьютерной безопасности
и математических методов обработки информации ЯрГУ
Б 33
Башкин, М. А. Дискретная математика. Ч. 2:
сборник задач / О. П. Якимова, М. А. Башкин; Яросл.
гос. ун-т им. П. Г. Демидова. – Ярославль : ЯрГУ,
2013. – 76 с.
Предназначен для студентов, обучающихся по направлению 010200.62 Математика и компьютерные
науки, специальности 090301.65 Компьютерная
безопасность (дисциплина «Дискретная математика»,
циклы Б3, С2), очной формы обучения.
УДК 519.854(076.1)
ББК В174я73-4
© ЯрГУ, 2013
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Графы
При подготовке этой части были использованы материалы из
книг [6], [9], [11], [15].
1.1. Основные определения
Пусть V – непустое множество, [V]r – множество всех его
r-элементных подмножеств.
Графом называется пара множеств G = (V, E), где E ⊆ [V]2, то
есть E – произвольное подмножество множества [V]2.
Элементы множества V называются вершинами графа G, а
элементы множества E – его ребрами. Рисуя граф, обычно изображают каждую вершину точкой и соединяют линиями такие
пары точек, которым в графе соответствует пара вершин, образующая ребро.
Рис. 1.1. Граф на множестве вершин V= {1,2,3,4,5,6,7}
со множеством ребер E= {{1, 2} ,{1, 6},{2,6},{3,5},{6,7}}
Множество вершин графа G, обозначается через V(G), а множество его ребер – через E(G). Число вершин графа G будем
обозначать через n(G), число ребер – через m(G). Графы могут быть
как конечными, так и бесконечными. Все рассматриваемые нами
графы конечны.
Говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае.
Если e = {u, v} – ребро, то вершины u и v называют его концами.
В этой ситуации говорят также, что ребро e соединяет вершины u
и v и что вершина u (или v) и ребро e инцидентны. Два ребра называются смежными, если они имеют общую вершину.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Подграфом графа G=(V, E) называется граф G1=(V1, E1) :
V1⊆V, E1 ⊆ E , у которого все вершины и ребра принадлежат G.
Остовный подграф – это подграф графа G, содержащий все
его вершины.
Подграф G0 на подмножестве вершин V0 ⊆ V называется
порожденным, если множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат V0.
Рис. 1.2. Граф, его остовный и порожденный подграфы
На рис. 1.2 изображен некоторый граф G на 6 вершинах и 2
его подграфа, причем G1 – остовный подграф, а G2 – нет. Подграф
G2 порожденный, а G1 – нет.
Легко подсчитать число всех графов с фиксированным множеством вершин V. Эти графы различаются своими ребрами,
и поэтому их число равно количеству подмножеств в [V]2, т. е.
2C(n,2). Однако графы, которые получаются один из другого изменением нумераций вершин, разумно не различать. Это приводит
к понятию изоморфных графов.
Пусть G=(V, E) и G’=(V’, E’) – два графа.
Графы G и G’ изоморфны (G ≅ G’), если существует биекция
φ: V → V’, где {u, v} ∈ E ⇔ {φ(u), φ(v)}∈ E’ при всех u, v ∈ V.
Очевидно, что изоморфизм графов обладает свойствами
симметричности, транзитивности и рефлексивности, т. е. является
эквивалентностью. Следовательно, множество всех графов
разбивается на классы так, что графы из одного класса попарно
изоморфны, а графы из разных классов не изоморфны. В различных
разделах математики изоморфные объекты рассматриваются
как копии одного объекта, и они отождествляются с точностью
до изоморфизма.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для произвольного графа G = (V, E) дополнительным графом
называется граф с тем же множеством вершин V(G), но любые две несовпадающие вершины смежны в
тогда и только
тогда, когда они не смежны в G, то есть =V2 \ E.
Граф, изоморфный своему дополнению, называется
самодополнительным.
Рис. 1.3. Граф, изоморфный своему дополнению
При решении некоторых практических задач приведенное
выше определение графа оказывается недостаточным, и приходится рассматривать более общие объекты. Ориентированный
граф состоит из конечного непустого множества V вершин и заданного набора X2 упорядоченных пар различных вершин. Элементы из X называются ориентированными ребрами или дугами.
Мультиграфом называется граф, в котором пары вершин могут соединяться более чем одним ребром; эти ребра называются
кратными. Если в мультиграфе ребра имеют ориентацию, то подобный граф называется ориентированным мультиграфом.
Дальнейшее обобщение состоит в том, что, кроме кратных
ребер, допускаются еще и петли, то есть ребра, соединяющие
вершину саму с собой. Такой граф называется псевдографом.
На рис. 1.4. представлены описанные виды графов: G1 – мультиграф, G2 – псевдограф, G3 – орграф.
Степенью вершины графа G называется число инцидентных
ей ребер. Традиционно принято обозначать через dv степень вершины v, через ∆ (G) – наибольшую из степеней вершин графа.
Очевидно, что для обыкновенного графа ∆(G) ≤ n(G)-1.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1.4. Мультиграф, псевдограф и орграф
Упорядоченный набор степеней вершин графа dv1,dv2, ... , dvn
называется его степенной последовательностью. Вершина степени 0 называется изолированной, вершина степени 1 – концевой
(висячей).
Теорема 1 (Л. Эйлера). Сумма степеней всех вершин графа
равнa удвоенному числу ребер
Пример 1. Можно ли 57 компьютеров соединить так, чтобы
каждый был соединен ровно с 13?
Рассмотрим граф, вершинами которого будут компьютеры,
а если компьютеры соединены, то и соответствующие вершины
соединены ребром. Если предположить, что такой граф существует, сумма степеней будет равна нечетному числу, что противоречит теореме. То есть так соединить компьютеры нельзя.
Приведем примеры некоторых графов специального вида. Граф
G называется полным (кликой), если любые две его вершины смежны. Полный граф на n вершинах обозначается Kn. Для числа ребер
полного графа выполняется равенство m(Kn) = C(n, 2) = n(n-1)/2.
Противоположным к понятию полного графа является понятие пустого графа. Граф называется пустым, если в нем нет
ребер. Пустой граф на n вершинах обозначается On.
Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две
вершины, входящие в разные доли, смежны, то граф называется
полным двудольным. Полный двудольный граф, доли которого
состоят из p и из q вершин, обозначается символом Kp,q.
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Граф называется однородным (или регулярным) графом степени d, если все его вершины имеют степень d.
Рис.1.5. Пример клики, пустого, двудольного и регулярного графов
Путь – это непустой граф P = (V, E) вида V = {v 0 , v1 ,  , v n } ,
.
Если
все
vi
различны,
то P называется простым путем. Путь замкнут, если v 0 = v n .
Циклом называется замкнутый путь. Простым циклом –
замкнутый простой путь.
Две вершины графа назовем эквивалентными, если они
могут быть соединены путем. Для любого графа данное отношение является эквивалентностью, т. е. обладает свойствами
рефлексивности, симметричности и транзитивности. Максимальные по включению подграфы графа G, порожденные классами эквивалентных вершин, называются компонентами связности
графа G. Любые две вершины из одной компоненты связности
соединены хотя бы одним путем, вершины же из разных
компонент не могут быть соединены путем. Граф называется
связным, если он состоит из одной компоненты связности.
Пример 2. В мегаполисе 12 станций метро, соединенных
56 перегонами (две станции соединяются не более чем одним
перегоном). Докажите, что метрополитен связен.
Решение.������������������������������������������������
Докажем, без ограничения общности, что со станции 1 можно попасть на станцию 2. Если нельзя, то на непересекающихся 11-ти маршрутах 1-2, 1-3-2, 1-4-2, 1-5-2,..., 1-12-2
не хватает хотя бы по одному ребру. Но до полного графа не хватает всего 10 рёбер. Противоречие.
Расстоянием d(u,v) между вершинами u и v графа G называется длина кратчайшего пути, соединяющего эти вершины. Ино7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
гда удобно полагать, что если u и v не соединены, то d(u,v)=∞.
В связном графе расстояние является метрикой.
Важными характеристиками графа являются понятия диаметра и радиуса. Диаметром d(G) связного графа G называется длиmax d(u,v) .
на самого длинного пути в графе, то есть d(G)= max
u
v
Радиусом связного графа G называется величина:
max d(u,v).
r(G)= min
u
v
Очевидно выполнение неравенства r(G)≤ d(G) ≤ 2r(G). Так,
если граф полный, то d(G) = r(G) = 1. А для пути P2m + 1 :
d(P2m + 1) = 2m; r(P2m + 1) = m.
Пример 3. Какое максимальное количество ребер может
иметь граф на n вершинах, у которого k компонент связности?
Рассмотрим граф, состоящий из k клик K n , K n , … , K nk ,
= n. Пусть n1 > n2 ≥ 2. Удалим вершину из компоненты K n
и n2 –1 ребро, ей инцидентное, и добавим вершину в K n 1 . Соединим добавленную вершину со всеми в этой компоненте связности. Общее количество вершин не изменится, общее количество
ребер увеличится на n1 – n2 + 1. Продолжая этот процесс, получим
граф, состоящий из k – 1 изолированной вершины и клики Kn-k + 1
на n – k + 1 вершине. Таким образом, максимальное количество
ребер графа на n вершинах, у которого k компонент связности,
равно
.
1
2
2
Задачи
1.1. Изобразить все попарно неизоморфные 4-вершинные
графы без петель и кратных ребер.
1.2.����������������������������������������������������
 ���������������������������������������������������
Построить все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.
1.3. Изобразить все попарно неизоморфные 6-вершинные
графы без петель и кратных ребер, состоящие: a) из 4 компонент;
б) из 3 компонент; в) из одной компоненты и имеющие 7 ребер и
2 висячие вершины.
1.4. Привести пример графа, в котором удаление некоторых
двух ребер увеличивает число связных компонент, но удаление
любого одного ребра числа связных компонент не меняет.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.5. Приведите пример двух графов, ни один из которых не
является подграфом другого.
1.6. Какие из графов G1, G2, G3 являются изоморфными?
G1
G2
G3
1.7. Среди пар графов, изображенных на рис. 1.6–1.8, указать
пары изоморфных и пары неизоморфных графов. Ответ обосновать.
Рис. 1.6
Рис. 1.7.
Рис. 1.8.
1.8. Решите задачу, используя теорему Эйлера и свойства
степенной последовательности графа: показать, что в любом графе, имеющем не менее двух вершин, найдутся две вершины с
одинаковыми степенями.
1.9. Дана позиция на шахматной доске, изображённая на
рис. 1.9. За наименьшее число ходов поменяйте местами трёх
чёрных и трёх белых коней.
Рис. 1.9.
1.10. Даны два графа G1 = (V1, E1) и G2 = (V2, E2).
V1 = {1,2,3,4,5}, E1 = {{1,2},{1,3},{1,5},{2,3},{2,5},{3,4},{3,5}};
V2 = {1,3,5}, E2 = {{2,5}, {2,3}, {1,5}, {3,5}}. Является ли один из
них подграфом другого?
1.11. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из кото9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
рых соединён с тремя другими, 8 телефонов, каждый из которых
соединён с шестью, и 3 телефона, каждый из которых соединён с
пятью другими?
1.12. В некотором государстве 100 городов, и из каждого из
них выходит 4 дороги. Сколько всего дорог в государстве?
1.13. В розыгрыше первенства по футболу участвуют
20 команд. Какое наименьшее число игр должно быть сыграно,
чтобы среди любых трех команд нашлись две, уже сыгравшие
между собой?
1.14. Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между
собой ровно один раз. В соревновании с двенадцатью участниками провели все встречи. Сколько было сыграно встреч?
1.15. Может ли полный граф иметь 7, 8, 9, или 10 ребер?
1.16. Можно ли на клетчатой бумаге закрасить 15 клеток так,
чтобы у каждой из них было а) чётное; б) нечётное число закрашенных соседей? (Клетки называются соседями, если они имеют
общую сторону.)
1.17. В городе X с любой станции метро можно проехать на
любую другую. Доказать, что одну из станций можно закрыть на
ремонт без права проезда через неё так, чтобы с любой из оставшихся станций можно было проехать на любую другую.
1.18. В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что
население города можно разбить не более чем на три группы так,
чтобы жители, входящие в одну группу, не разговаривали в этот
день между собой по телефону.
1.19. В классе 30 человек. Может ли быть так, что 9 из них
имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?
1.20. У царя Гвидона было 5 детей. Из всех его потомков (детей,
внуков, правнуков и т. д.) 57 имели ровно трёх сыновей, а остальные
умерли бездетными. Сколько потомков было у царя Гвидона?
1.21. Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между
собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.22. В футбольном турнире 20 команд сыграли 8 туров: каждая команда сыграла с 8 разными командами. Докажите, что найдутся 3 команды, не сыгравшие между собой пока ни одного матча.
1.23. Про некоторую компанию известно, что каждый человек знаком в ней ровно с шестью людьми и для любой группы из
шести человек найдется член компании, знакомый с каждым из
этой шестерки. Сколько человек в компании?
1.24. В некоторой стране любые 2 города соединены либо
авиалинией, либо железной дорогой. Докажите, что а) можно
выбрать вид транспорта так, чтобы от любого города можно
было добраться до любого другого, пользуясь только этим видом транспорта; б) из некоторого города, выбрав один из видов
транспорта, можно добраться до любого другого города не более,
чем с одной пересадкой (пользоваться можно только выбранным
видом транспорта).
1.25. В одном городе есть несколько (более одного) автобусных маршрутов. При этом: 1) на каждом маршруте ровно три
остановки; 2) с каждого маршрута на каждый можно пересесть,
и притом на одной остановке; 3) с каждой остановки на каждую
можно проехать без пересадки, и притом только одним маршрутом. Сколько автобусных маршрутов в этом городе?
1.26. В некоторой стране любые два города связаны одним
из трёх видов транспорта. Не существует города, обеспеченного
всеми тремя видами транспорта, и в то же время не существует
трёх городов, любые два из которых связаны одним и тем же
средством сообщения. Найти наибольшее возможное количество
городов в этой стране.
1.27. В Тридевятом царстве лишь один вид транспорта –
ковёр-самолёт. Из столицы выходит 21 ковролиния, из города
Дальний – одна, а из всех остальных городов – по 20. Докажите,
что из столицы можно долететь в Дальний (возможно, с пересадками).
1.28. Как соединить 50 городов наименьшим числом авиалиний так, чтобы из любого города можно было попасть в любой
другой, сделав не более двух пересадок?
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.29. Во время бала каждый юноша танцевал с девушкой либо
более красивой, либо более умной, чем в предыдущем танце, а хотя
бы один – с девушкой одновременно более красивой и более умной.
Могло ли такое быть? (Юношей и девушек на балу было поровну.)
1.30. В стране из каждого города выходит 100 дорог, и от
любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города
можно добраться до любого другого.
1.31. Учитель танцев хочет расставить 10 мальчиков и несколько девочек так, чтобы рядом с каждым мальчиком стояли
мальчик и девочка и через одного от каждой девочки тоже стояли
мальчик и девочка. Сколько девочек он должен пригласить?
1.32. Показать, что самодополнительный граф связен.
1.33. Пусть G – произвольный граф без петель и кратных
ребер, а
– его дополнение. Доказать, что а) хотя бы один из
графов G или
связен; б) если n(G) > 4, то в хотя бы одном из
графов G или
есть цикл.
1.34. Докажите, что граф с n вершинами, степень каждой из
которых не менее
, является связным графом.
1.35. Докажите, что если в графе все вершины имеют четную
степень, то в графе нет ребра, удаление которого приводит к увеличению количества компонент связности.
1.2. Представление графа в памяти компьютера.
Алгоритмы обхода графа
Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке
эффективных алгоритмов. При решении задач используются
следующие два стандартных способа представления графа
G = (V, E): как набора списков смежных вершин или как
матрицы смежности. Оба способа представления применимы
как для ориентированных, так и для неориентированных графов.
Обычно более предпочтительно представление с помощью
списков смежности, поскольку оно обеспечивает компактное
представление разреженных графов, т. е. таких, для которых
число ребер гораздо меньше квадрата числа вершин.
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Представление при помощи матрицы смежности предпочтительнее в случае плотных графов, т. е. когда число ребер близко к
n(G)2,или когда нам надо иметь возможность быстро определить,
имеется ли ребро, соединяющее две данные вершины. Например,
алгоритм поиска кратчайшего пути для всех пар вершин использует представление графов именно в виде матриц смежности.
0
1
2
3
4
0
0
1
1
0
1
1
1
0
0
0
0
2
1
0
0
1
1
3
0
0
1
0
1
4
1
0
1
1
0
а) б) в)
Рис. 1.10. Два представления неориентированного графа
Представление графа G = (V, ������������������������������
�����������������������������
) в виде списка смежности и��
спользует массив EdgeList из n(G) списков, по одному для каждой
вершины из V. Для каждой вершины u ∈ V список EdgeList[u]
содержит все вершины v, такие что {u, v} ∈ Е, т. е. EdgeList[u]
состоит из всех вершин, смежных с u в графе G (список может
содержать не сами вершины, а указатели на них). Вершины
в каждом списке обычно хранятся в произвольном порядке.
На рис. 1.10 б) показано представление обыкновенного
графа, изображенного на рис 1.10 а) в виде списка смежности.
Аналогично на рис. 1.11 а) и б) показаны ориентированный граф
и его представление через список смежных вершин.
Рис. 1.11. Два представления ориентированного графа
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Представление графа G = (V, Е�������������������������
��������������������������
) с помощью матрицы смежности предполагает, что вершины перенумерованы в некотором
порядке числами 1, 2,..., n. В таком случае представление графа
G с использованием матрицы смежности представляет собой
матрицу А размером n × n, такую что
На рис. 1.10 в) и 1.11 в) показаны представления
с использованием матрицы смежности неориентированного
и ориентированного графов, изображенных на рис. 1.10 а) и 1.11 а)
соответственно. Матрица смежности графа требует объем памяти,
равный n2, независимо от количества ребер графа.
Списки и матрица смежности легко адаптируются для
представления взвешенных графов, т. е. графов, с каждым ребром
которых связан определенный вес���������������������������
, обычно определяемый вес��
овой функцией w: Е  R. В этом случае в каждый элемент списка
добавляется весовое поле, а для матрицы смежности
Все основные служебные операции при работе с графами�����
(�
апример, преобразование графа из одного представления в другое,
распечатка или рисование графа) предполагают его систематический
обход, то есть посещение каждой вершины и каждого ребра графа.
Если представить лабиринт в виде графа, где ребра – проходы,
а вершины – точки пересечения проходов, то любой правильный
алгоритм обхода графа должен найти выход из произвольного
лабиринта. Наиболее известными из таких алгоритмов являются
поиск в глубину (depth first search, DFS) и поиск в ширину (breadth first
search, BFS), причем они являются базисными для многих других
алгоритмов решения прикладных задач.
Пусть задан граф G = (V, E) и выделена начальная вершина v.
Алгоритм поиска в ширину систематически обходит все ребра
графа G для «открытия» всех вершин, достижимых из v. В процессе
обхода строится дерево поиска в ширину с корнем в начальной
вершине, содержащее все достижимые вершины. Заметим, что
расстояние (количество ребер) от корневой вершины до любой
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вершины этого дерева является кратчайшим. Алгоритм работает
как для ориентированных, так и для неориентированных графов.
Идея алгоритма: все вершины, смежные с начальной,
открываются, то есть помещаются в список, и получают
единичную пометку. После этого начальная вершина обработана
полностью и имеет пометку 2.
Следующей текущей вершиной становится первая вершина
списка. Все ранее непомеченные вершины, смежные с текущей,
заносятся в конец списка (становятся открытыми). Текущая
вершина удаляется из списка и помечается числом 2. Процесс
продолжается, пока список вершин не пуст. Такая организация
списка данных называется очередью.
Рассмотрим пример. Исходный граф на левом рисунке.
На правом рисунке рядом с вершинами в скобках указана
очередность просмотра вершин графа. Ребра, образующие дерево
поиска в ширину, выделены толстой линией.
Рис. 1.12. Просмотр вершин графа в процессе поиска в ширину
Основная идея поиска в глубину, как и следует из его названия, состоит в том, чтобы идти «вглубь» графа, пока это возможно. Просмотр начинается с некоторой начальной вершины v.
Она считается «открытой». Выбирается вершина u, смежная с v,
открывается, то есть помечается значением 1, и процесс повторяется с одной из вершин, смежных с u.
Если на очередном шаге мы работаем с вершиной q, и нет вершин, смежных с q, и неоткрытых, то возвращаемся на предыдущий
шаг. Если попадаем в начальную вершину, то обход графа завершен.
В процессе обхода графа строится дерево поиска в глубину.
Вершина v, через которую открывается вершина u, является ее
предком. Эта информация сохраняется в массиве Parent.
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для определения состояния вершины (неоткрытая, открытая или
обработанная), как и раньше, используется массив пометок Mark.
Если вершина i открыта, то Mark[i]=1, обработана – 2, в исходном состоянии Mark[i]=0. Для хранения последовательности открытых, но
не обработанных вершин используется стек. Эта структура данных
обеспечивает возврат к предыдущей открытой вершине.
Также с каждой вершиной связываются две метки времени:
время открытия вершины time_in и время завершения ее обработки
time_out, которые обладают рядом интересных свойств. Рассмотрим
их на примере графа, изображенного на рис. 1.13 слева. Пусть поиск
в глубину начинается с нулевой вершины. На рис. 1.13 справа
у вершин в скобках указаны две метки времени. Фактически первая
метка – это та очередность, в которой вершины графа просматривались
в процессе обхода. Разница во времени обработки и открытия для
вершины v дает информацию о количестве потомков этой вершины
в дереве поиска в глубину. Показания часов увеличиваются на единицу
при каждом входе и каждом выходе из вершины, поэтому количество
потомков данной вершины будет равно половине разности между
моментом завершения обработки вершины и моментом ее открытия.
Рис. 1.13 Порядок просмотра вершин графа при поиске в глубину
Замечание: предложенные методы обходят все вершины,
содержащиеся в одной компонете связности с начальной
вершиной. Поэтому можно использовать любой из алгоритмов
обхода для определения связности графа.
Задачи
1.36. Построить граф и задать его матрицей смежности.
Граф задан массивом ребер (в каждой ячейке в столбик записаны
номера соседних вершин и вес соединяющего их ребра).
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a) 1 1 1 2 2 2 3 3 4 5
b) 1 1 1 1 1 2 2 3 4 4 5
4563564656
32456355566
3597226367
48343534593
c) 1 1 1 2 2 2 3 3 4 4
d) 1 1 1 1 2 2 2 3 3 4
3454565456
2346346455
3331253791
2334543332
e) 1 1 1 1 2 2 2 3 4 4 5
f) 1 1 1 1 1 2 2 3 4 5
23563464566
2345645556
23434342342
4549343254
g) 1 1 2 2 2 3 3 4 4 5
h) 1 2 2 2 2 3 3 4 4 5 5
2634545566
23456475767
4213456123
54312274321
1.37. Обойти все вершины графа задания 1.36, используя алгоритм поиска a) в ширину; b) в глубину. Ответ записать в виде
последовательности вершин.
1.38. Для графа задания 1.36 написать его представление
через список смежных вершин.
1.39. Охарактеризуйте матрицу смежности графа G и его
дополнения .
1.40. Дана матрица смежности графа. Найти все вершины,
входящие в одну компоненту связности с вершиной 6.
1
2
3
4
5
6
7
8
9
1
0
0
0
1
1
0
0
1
0
2
0
0
0
0
0
1
0
0
1
3
0
0
0
0
0
0
1
0
1
4
1
0
0
0
1
0
0
1
0
5
1
0
0
1
0
0
0
0
0
6
0
1
0
0
0
0
1
0
0
7
0
0
1
0
0
1
0
0
1
8
1
0
0
1
0
0
0
0
0
9
0
1
1
0
0
0
1
0
0
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.41. Дана симметричная матрица размером n х n. В каждой
строке расположено нечетное число единиц, остальные элементы
равны нулю. Элементы на главной диагонали равны нулю. Доказать, что n является четным.
1.42. Имеется N человек и квадратная таблица А N × N;
элемент A[i, j] равен 1, если человек i знаком с человеком j,
А[i, j] = А[j, i]. Можно ли разбить людей на 2 группы, чтобы
в каждой группе были только незнакомые люди? Придумайте
алгоритм, решающий эту задачу.
1.43. Выделите все компоненты связности графа. Граф задан
списком смежных вершин.
а)
б)
в)
1
3, 7, 8
1
4, 6, 8
1
4, 7
2
4, 6
2
5, 7
2
5
3
1, 5, 8
3
7
3
6, 8
4
2, 6
4
1, 6, 8
4
1, 7
5
3, 8
5
2
5
2
6
2, 4
6
1, 4
6
3, 8
7
1
7
2, 3
7
1, 4
8
1, 3, 5
8
1, 4
8
3, 6
1.3. Деревья. Остов минимального веса
Деревом называется связный граф, не содержащий циклов.
Любой граф без циклов называется ациклическим, или лесом. Таким образом, компонентами леса являются деревья.
В теории графов и ее приложениях используются и другие
определения понятия дерева, равносильные введенному выше;
некоторые из них отражены в следующей теореме.
Теорема 1. Для графа G следующие утверждения эквивалентны:
1) G – дерево;
2) G – связный граф, и m(G)= n(G)-1;
3) G – ациклический граф, и m(G)= n(G)-1;
4) любые две несовпадающие вершины графа G соединяет
единственный простой путь;
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5) G – ациклический граф, обладающий тем свойством, что
если какую-либо пару его несмежных вершин соединить ребром,
то полученный граф будет содержать ровно один цикл.
Пример 1. Доказать, что а) при удалении любого ребра из дерева оно превращается в несвязный граф; б) в дереве любые две
вершины соединены ровно одним простым путем.
Решение. а) Предположим, что концы удаленного ребра в
новом графе соединены простым путем. Тогда этот путь вместе
с удаленным ребром образует в исходном графе цикл.
б) Предположим противное и рассмотрим те две вершины,
которые соединены двумя разными простыми путями. На первый
взгляд кажется, что, пройдя от одной вершины к другой по первому пути и вернувшись по второму, мы получим цикл. К сожалению, это не совсем так. Дело в том, что первый и второй пути
могут иметь общие вершины (кроме начала и конца), а по определению простого цикла вершины в нем не должны повторяться.
Для того чтобы выделить настоящий цикл из уже полученного,
нужно сделать следующее: а) выбрать первую точку, в которой
пути расходятся; б) за выбранной точкой на пути 1 найти первую
точку, принадлежащую также и пути 2. Теперь участки первого
и второго путей между точками а) и б) образуют простой цикл.
Рассмотрим следующую задачу: во взвешенном связном графе
требуется найти остов минимального веса. Так как полный граф
Kn содержит nn-2 различных остовных деревьев, то решение этой
задачи перебором вариантов потребовало бы чрезвычайно больших
вычислений даже при малых n. Существуют эффективные алгоритмы,
решающие эту задачу, например алгоритм Дж. Краскала (1956 г.)
и Р. Прима (1957 г.), применимые к произвольному связному графу.
Общая формулировка задачи об остове минимального веса
(о кратчайшем остове): в связном взвешенном графе G порядка
n найти остов минимального веса. Алгоритм Краскала,
решающий эту задачу, заключается в следующем.
1. Строим граф T1 = On + e1 , присоединяя к пустому графу
на множестве вершин V(G) ребро e1 ∈ E(G) минимального веса.
2. Если граф Ti уже построен и i < n-1 , то строим граф
T i + 1 =Ti + ei + 1 , где ei + 1 – ребро графа G, имеющее минимальный
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вес среди ребер, не входящих в Ti и не составляющих циклов
с ребрами из Ti .
Алгоритм Прима отличается от алгоритма Краскала только
тем, что на каждом шаге строится не просто ациклический граф,
а дерево. Именно:
1. Выбираем ребро e1 ={a, b} минимального веса и строим
дерево T1 , полагая V(T1) = { a, b}, E( T1) ={ e1}.
2. Если дерево Ti порядка i + 1 уже построено и i < n-1,
то среди ребер, соединяющих вершины этого дерева с вершинами
графа G, не входящими в Ti, выбираем ребро ei + 1 минимального
веса. Строим дерево Ti + 1, присоединяя к Ti ребро ei + 1 вместе с его
не входящим в Ti концом.
На рисунке 1.14 посередине приведен исходный граф,
а справа и слева – его минимальные остовные деревья, построенные
по алгоритмам Краскала и Прима. Числа на ребрах остовных
деревьев обозначают последовательность их добавления. Легко
видно, что остовные деревья абсолютно одинаковы, но порядок
добавления в них ребер различен.
Рис. 1.14. Граф G и его минимальные остовные деревья
Задачи
1.44. Изобразить все попарно неизоморфные деревья:
1) с 6 ребрами и 3 висячими вершинами; 2) с 6 ребрами и 4 висячими вершинами; 3) с 7 ребрами и 3 висячими вершинами;
4) с 8 ребрами и 3 вершинами степени 3.
1.45. В графе все вершины имеют степень 3. Докажите,
что в нем есть цикл.
1.46. В некоторой стране 30 городов, причём каждый соединён с
каждым дорогой. Какое наибольшее число дорог можно закрыть на
ремонт так, чтобы из каждого города можно было проехать в каждый?
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.47. В стране 100 городов, некоторые из которых соединены
авиалиниями. Известно, что от любого города можно долететь до
любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более а) 198 перелётов; б) 196 перелётов.
1.48. Квадрат 8 × 8 выложили из спичек. Какое наименьшее
число спичек надо убрать, чтобы с любого поля можно было
пройти на любое другое, не перепрыгивая через спички?
1.49. Расстоянием между двумя вершинами дерева назовем
длину простого пути, соединяющего их; а удалённостью вершины дерева – сумму расстояний от неё до всех остальных вершин.
Докажите, что в дереве, у которого есть две вершины с удалённостями, отличающимися на 1, нечётное число вершин.
1.50. Доказать, что во всяком дереве с n ≥ 2 вершинами содержится не менее двух висячих вершин.
1.51. Какое максимальное число висячих вершин может
иметь дерево, обладающее 9 вершинами?
1.52. Сколько ребер нужно удалить из связного графа, имеющего q ребер и p вершин, чтобы получить дерево, содержащее все
вершины этого графа.
1.53. Докажите, что в любом связном графе можно удалить
вершину вместе со всеми выходящими из неё рёбрами так, чтобы
он остался связным.
1.54. Докажите, что при удалении любого ребра из дерева
оно превращается в несвязный граф.
1.55. Пусть k – число висячих вершин у n-вершинного дерева, не содержащего вершин степени 2. Доказать, что k ≥ n/2 + 1.
1.56. Индукцией по n доказать, что каждое дерево с n ≥ 2 вершинами является двудольным графом.
1.57. Какие деревья являются полными двудольными графами?
1.58.������������������������������������������������������
 �����������������������������������������������������
Для графа задания 1.36�������������������������������
�����������������������������������
найти кратчайший остов: a�����
������
) �
спользовать алгоритм Краскала; b) алгоритм Прима. В качестве
ответа привести список ребер, составляющих остов, в порядке их
добавления.
1.59. В дереве удалили вершину, степень которой была
больше 1. Оставшийся в результате граф связный?
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.60. Город имеет форму квадрата (100n × 100n) метров
с (n + 1) прямолинейной улицей, идущей параллельно одной стороне квадрата, и (n + 1) прямолинейной улицей, идущей параллельно другой его стороне. Расстояние между любыми двумя соседними параллельными улицами – 100 метров, длина каждой улицы
– 100n метров. Мэр города решил выполнить свое предвыборное
обещание: заасфальтировать за свой счет улицы так, чтобы с любого перекрестка на любой другой можно было проехать по асфальту.
Конечно, мэр хочет истратить как можно меньше своих денег. Какой
наименьшей длины асфальтовое покрытие улиц может сделать мэр?
1.4. Плоские и планарные графы
Плоским графом назовем граф, вершины которого являются
точками плоскости, а ребра – непрерывными плоскими линиями
без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.
Любой граф, изоморфный плоскому графу, будем называть
планарным. Например, любое дерево, любой простой цикл – планарные. Граф K4 является планарным, так как он изоморфен графам G1 и G2 на рисунке 1.15.
Рис. 1.15.
О планарных графах говорят, что они укладываются
на плоскости или имеют плоскую укладку.
Теорема Жордана. Замкнутая несамопересекающаяся кривая (т.е. цикл) делит плоскость ровно на две части. При этом одна
часть ограничена, другая не ограничена, причем две точки плоскости, не принадлежащие кривой, лежат в одной части тогда и
только тогда, когда их можно соединить ломаной, не пересекающей кривой.
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Из теоремы Жордана следует, что любой плоский граф разбивает плоскость на конечное число связных частей. Эти части
называются гранями изображения графа на плоскости.
Теорема 2 (Формула Эйлера).�����������������������������
Для всякого связного плоского графа с n вершинами, m ребрами и f гранями верно равенство
n – m + f = 2.
Два графа называются гомеоморфными, если один из них
можно получить из другого с помощью конечного числа операций подразбиения ребра и стягивания ребра.
Если граф планарный, то очевидно, что любой граф, гомеоморфный ему, также является планарным.
Теорема Понтрягина – Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 или K3,3.
Пример. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
Решение.����������������������������������������������
Будем считать отмеченные точки и вершины квадрата вершинами, а соединяющие их отрезки и стороны квадрата
– ребрами плоского графа. Для каждого куска, на которые этот
граф разбивает плоскость, подсчитаем число ограничивающих
его ребер, и все полученные числа сложим. Поскольку каждое
ребро разделяет два куска, то в итоге получим удвоенное число
ребер. Так как все куски, кроме внешнего – треугольники, а внешний кусок ограничен 4 ребрами, то получаем 3(f-1) + 4 = 2m(G),
т. е. m(G) = 3(f-1)/2 + 2.
Заметим, что число вершин нашего графа равно 24 и подставим количества вершин и ребер в формулу Эйлера:
24 - (3(f-1) /2 + 2) + f = 2. Отсюда f = 43. Таким образом, число
треугольников, на которые разбился квадрат, равно 42.
Задачи
1.61. В стране Озёрная 7 озёр, соединённых между собой
10 каналами, причём от любого озера можно доплыть до любого
другого. Сколько в этой стране островов?
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.62. Докажите, что для плоского графа верно неравенство
2m(G)≥ 3f.
1.63. Докажите, что для плоского связного графа справедливо неравенство a) m(G) ≤ 3n(G) – 6; б) для плоского графа (в том
числе и несвязного) справедливо m(G) ≤ 3n(G) – 6.
1.64. Нарисовать плоский граф, имеющий 6 вершин, степень
каждой из которых равна а) 3; б) 4.
1.65. Нарисовать плоский граф, имеющий 8 вершин, степень
каждой из которой равна 4.
1.66. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, неплоский.
1.67. Мэрия решила построить в каждом квартале города,
имеющего 155 перекрестков и 260 отрезков улиц между перекрестками, универсам. Сколько будет построено универсамов?
1.68. Печатная плата представляет собой пластинку из изолирующего материала, в специально изготовленные гнезда которой устанавливают электронные приборы. В качестве проводников, соединяющих эти приборы, служат напыленные металлические дорожки.
Поскольку проводники не изолируются, то дорожки не должны пересекаться. Если это может произойти, то одну из дорожек переносят на другую сторону платы. Конструктор Иванов придумал схему
печатной платы, которая состоит из 12 приборов и 32 проводников,
соединяющих их. Можно ли изготовить такую плату так, что все
проводники будут расположены на одной её стороне?
1.69. Инженер Иванов усовершенствовал свою плату. Теперь
она имеет 9 приборов и 17 проводников. Схема платы представлена
на рис. 1.16. Можно ли изготовить
такую плату так, что все проводники будут расположены на одной
Рис. 1.16. 
её стороне?
1.70. Инженер Иванов придумал схему печатной суперплаты, которая может заменить целый компьютер. Плата состоит
из 200 приборов и 2000 проводников. Ясно, что для реализации
такой схемы нужно будет использовать многослойную плату,
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
на которой проводники будут располагаться в разных слоях. Докажите, что разработанную схему нельзя изготовить в виде трехслойной платы.
1.71. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо
«красный», либо «синий» граф не является плоским.
1.72. Построить все попарно неизоморфные непланарные графы без петель и кратных ребер, содержащие 6 вершин и 11 ребер.
1.73. Какое наибольшее число граней может быть у плоского 5-вершинного графа, не имеющего петель и кратных ребер?
Изобразите такой граф.
1.5. Циклы в графах
Цикл в графе называется эйлеровым, если он содержит
все ребра графа. Связный граф, в котором есть эйлеров цикл,
называется эйлеровым графом.
Такой граф можно нарисовать, не отрывая карандаша
от бумаги и не повторяя линий.
Теорема 1 (Л. Эйлер). Связный неориентированный граф
является эйлеровым тогда и только тогда, когда степени всех его
вершин четны. Эйлеров путь в графе существует тогда и только
тогда, когда две вершины в графе имеют нечетную локальную
степень, а остальные – четную.
Пример 1. �����������������������������������������������
Можно ли начертить, не отрывая карандаша от бумаги (одним росчерком)
a) квадрат с диагоналями?
b) шестиугольник со всеми диагоналями?
c) связное множество, состоящее из нескольких окружностей?
d) связный граф, проходя по каждому ребру дважды?
Решение. a), b) Нет, так как все вершины графов K4 и K6 имеют нечетные степени.
c) Да. Рассмотрим граф, вершинами которого будут точки
пересечения (касания) окружностей, а ребрами – дуги. В этом
графе все степени вершин четны.
d) Да. Перейдем от данного графа к мультиграфу, удвоив
каждое ребро. Степени всех вершин в полученном мультиграфе
четны, а значит, по теореме 1 он эйлеров.
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам этот
цикл также называется гамильтоновым.
Ответить на вопрос, является ли данный граф гамильтоновым,
как правило, очень трудно. Интуитивно ясно, что если граф содержит много ребер и эти ребра к тому же достаточно равномерно
распределены, то граф «предрасположен» быть гамильтоновым.
Подтверждением этому может служить следующая теорема.
Теорема 2. Если n(G) ≥ 3 и для любой пары x и y несмежных
вершин графа G dx + dy ≥ n(G), то граф G – гамильтонов.
Пример 2. Является ли
гамильтоновым граф, изображенный на рис. 1.17 ?
Представленный  г р а ф
имеет семь вершин, значит,
соответствующий
гамильтонов цикл состоит из семи
ребер. Но по рис. 1.17 видно,
Рис. 1.17. 
что этот граф является
полным двудольным графом K3,4. В двудольном графе могут быть
только циклы чётной длины. Действительно, пусть в двудольном
графе G существует цикл длиной k. Пройдем все ребра этого
цикла в том порядке, в котором они в нем расположены, начиная
с некоторой вершины v. Через k шагов вернемся в v. Так как
концы каждого ребра лежат в разных долях, то k – четное число.
Поэтому граф K3,4 не является гамильтоновым, как и любой
другой двудольный граф с нечетным количеством вершин.
Цикломатическое число графа ν(G) – минимальное число
ребер, которые надо удалить, чтобы граф стал ациклическим.
Для обыкновенного графа существует соотношение: ν(G) = m(G)
– n(G) + k, где k – число компонент связности графа, m(G) и
n(G) – число рёбер и вершин графа соответственно. Очевидно,
что цикломатическое число всегда неотрицательно.
Для ориентированных графов для вычисления цикломатического числа вместо дуг рассматривают ребра. Цикломатическое число мультиграфа равно максимальному числу
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
независимых циклов. Знание цикломатического числа оказывается
полезным при анализе топологии электронных схем, а также для
решения целого класса задач конструкторского проектирования
радиоэлектронных средств.
Задачи
1.74. Имеется группа островов, соединённых мостами так,
что от каждого острова можно добраться до любого другого. Турист обошёл все острова, пройдя по каждому мосту ровно один
раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист а) не с него начал и не на
нем закончил? б) с него начал, но не на нем закончил? в) с него
начал и на нем закончил?
1.75. Докажите, что связный граф с 2k нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно
k – 1 раз и не проводя никакое ребро дважды.
1.76. Можно ли, не отрывая карандаш от бумаги и не проводя
по одной линии дважды, нарисовать правильный пятиугольник с
диагоналями?
1.77. Турист обошёл 6 улиц одного города, пройдя каждую
ровно два раза, но не смог обойти их, пройдя каждую по одному
разу. Могло ли так быть, если а) улицы могут оканчиваться тупиком; б) конец каждой улицы – перекрёсток?
1.78. Все города страны, кроме столицы, расположены вдоль
шоссе. Из столицы в каждый город ведет прямая дорога. Две компании хотят приватизировать дороги и участки шоссе так, чтобы каждая компания могла проехать из любого города в любой
другой только по своим дорогам. Смогут ли они это сделать при
каком-нибудь числе городов, большем одного?
1.79. Рёбра бесконечной треугольной решётки раскрашены
в два цвета. Докажите, что найдутся две сколь угодно далёкие
точки, соединённые одноцветным путём.
1.80. Для каких чисел p, q, n граф G является эйлеровым:
1) Kn – полный граф с n вершинами?
2) Kp,q – полный двудольный граф с p, q вершинами?
3) Wn – колесо с n вершинами (см. рис. 1.18)?
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1.18. Граф Wn , где n = 3, 4, 5
1.81. Для каких чисел n граф является гамильтоновым:
1) Kn – полный граф с n вершинами?
2) Wn – колесо с n вершинами?
1.82. Мышка грызет куб сыра с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает какойлибо кубик, она переходит к другому кубику, имеющему общую грань
Рис. 1.19.
с предыдущим. Может ли мышка съесть
Граф
Петерсена
весь куб, кроме центрального кубика?
1.83. Найдите цикломатическое число для графов:
1) клики Kn;
4) полного двудольного графа Kp,q;
5) любого связного регулярного
2) колеса Wn ;
графа с n вершинами степени
3) графа Петерсена
регулярности r.
(см. рис. 1.19.)
1.84. Докажите, что полный двудольный граф с p вершинами
в одной доле и q вершинами в другой имеет не менее pq – p – q +
1 различных циклов?
1.6. Независимость и раскраски
Независимым подмножеством графа G называется такое
подмножество его вершин V0, в котором никакие две вершины не
соединены ребром. Иными словами, если S ⊆ V(G) и S независимо в
графе G, то порожденный подграф G(S) является пустым. Очевидно, что если при этом S’ ⊆ S, то S’ также независимое множество.
Независимое множество называется максимальным, если оно
не является собственным подмножеством некоторого другого независимого множества. Максимальное по мощности независимое
множество называется наибольшим. Ясно, что наибольшее неза28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
висимое множество является максимальным. Обратное, в общем
случае, неверно.
Число вершин в наибольшем независимом множестве графа
G называется числом независимости этого графа и обозначается α0(G). Например, для пустого графа α0(On) = n, для полного
α0(Kn) = 1, для простого цикла как на 2k вершинах, так и на 2k + 1
вершине α0(С2k) = α0(С2k + 1) = k.
Число вершин в наибольшем полном подграфе графа G называется плотностью ϕ(G) этого графа.
Произвольное подмножество попарно несмежных ребер графа
называется паросочетанием (или независимым множеством ребер).
Паросочетание графа G называется максимальным, если
оно не содержится в паросочетании с большим числом ребер,
и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа G. Число ребер в наибольшем паросочетании графа G называется числом паросочетания и обозначается через α1(G)
С понятием паросочетания тесно связано понятие реберного
покрытия. Реберным покрытием графа G называется такое подмножество ребер E’⊆ EG, которое покрывает все вершины графа,
т. е. такое, что каждая вершина в G инцидентна, по крайней мере,
одному ребру из E’. Из этого определения следует, что лишь графы с изолированными вершинами не имеют реберных покрытий.
Реберное покрытие графа называется минимальным,
если в нем не содержится покрытий с меньшим числом ребер,
и наименьшим, если число ребер в нем наименьшее среди всех
покрытий. Число ребер в наименьшем реберном покрытии графа
G называется числом реберного покрытия и обозначается через
β1(G). Очевидно, что β1(G) ≥ n(G)/2.
Пример. Для графа на рис. 1.20
найти α0(G), ϕ(G), указать, какие
ребра входят в наибольшее паросочетание, и какие – в наименьшее
реберное покрытие.
Решение. Легко видно, что
ϕ(G) = 4, α0(G) =3. Наибольшее
паросочетание состоит из 4х реРис. 1.20
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
бер, например {A,F}, {C,H}, {E,R}, {D,T}. Реберное покрытие –
из пяти: {A,H}, {C,F}, {E,T}, {D,R}, {B,E}.
Пусть G – некоторый граф, k – натуральное число. Произвольная функция вида f: V(G) → 1,2, …, k называется вершинной
k-раскраской, или просто k-раскраской графа G. Раскраска называется правильной, если f(u) ≠ f(v) для любых смежных вершин u
и v. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым.
Минимальное число k, при котором граф G является
k-раскрашиваемым, называется хроматическим числом этого
графа и обозначается χ(G). Если χ(G) = k, то граф G называется
k-хроматическим. Правильная k-раскраска графа G при k = χ(G)
называется минимальной. Множества вершин, принадлежащих
одному цветному классу, являются независимыми.
Для некоторых графов хроматические числа найти несложно.
Например, χ(Kn) =n, χ(Kn – e) = n-1, χ(C2n)=2, χ(Kn,m) =2, χ(C2n + 1) =3.
Для хроматического числа графа G справедливы следующие
оценки:
1) χ(G)≤5, если G – планарный граф;
2) χ(G) ≥ ϕ(G);
3) χ(G) ≤ ∆(G) + 1, ∆(G) = max dv;
4) χ(G) ≥ n2/(n2- 2m).
Аналогично вершинной определяется реберная k-раскраска.
Реберная раскраска называется правильной, если смежные ребра
имеют разные цвета. Минимальное число k, при котором граф G
является реберно k-раскрашиваемым, называется хроматическим
индексом χ’(G) графа G. Если χ’(G) = k, то граф G называется
реберно k-хроматическим.
При правильной реберной раскраске каждое множество ребер одного цвета является паросочетанием. Поэтому число χ’(G)
можно рассматривать как наименьшее число паросочетаний, на
которые разбивается множество ребер графа G.
Для хроматического индекса мультиграфа G имеют место
следующие оценки:
1) χ’(G) ≥ ∆(G), где ∆(G) = max dv;
2) χ’(G) ≤ [1.5∙ ∆(G) ] (теорема К. Шеннона);
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) χ’(G) ≤ ∆(G) + µ( G), где µ( G) – максимальная кратность
ребра (В. Г. Визинг).
Для обыкновенного графа ∆(G)≤ χ’(G) ≤ ∆(G) + 1.
Задачи
1.85. Для графов задания 1.36 найти α0(G), ϕ(G), указать, какие ребра входят в наибольшее паросочетание и какие – в наименьшее реберное покрытие.
1.86. Для графов, изображенных на рис. 1.19 и 1.21 найти α0(G),
ϕ(G) и указать, какие ребра входят в наибольшее паросочетание.
Рис. 1.21.
1.87. В некоторой группе из 12 человек среди каждых девяти
найдутся пять попарно знакомых. Докажите, что в этой группе
найдутся шесть попарно знакомых.
1.88. Каждое из рёбер полного графа с 6 вершинами
покрашено в один из двух цветов. Докажите, что есть три
вершины, все рёбра между которыми – одного цвета.
1.89. Сколькими способами можно раскрасить полный помеченный граф на 6 вершинах шестью цветами? (Два способа считаются различными, если некоторая вершина при одном способе
имеет один цвет, а при другом способе – другой.)
1.90. Определите хроматические числа для графов платоновых тел( см. рис. 1.22).
Рис. 1.22
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.91. Граф называется критическим, если удаление любой
его вершины вместе с инцидентными ей ребрами приводит к графу с меньшим хроматическим числом. Покажите, что Kn, является критическим графом при n >1.
1.92. Докажите, что всякий критический граф, являющийся
k-хроматическим:
– связен;
– не имеет точек сочленения;
– степень каждой его вершины не меньше, чем k – 1.
1.93. Пусть G – граф без петель и кратных ребер и ∆(G) –
наибольшая из степеней его вершин. Доказать, что χ(G) ≤∆( G) + 1.
1.94. Доказать, что вершины всякого плоского графа (без
петель и кратных ребер) можно правильно окрасить в q ≤ 6 цветов.
1.95. Доказать, что для правильной раскраски ребер всякого
кубического мультиграфа достаточно 4 цветов.
1.96. Найти хроматические числа и хроматические индексы
графов, изображенных на рис. 1.6–1.8, 1.19, 1.21.
1.97. Все страны, расположенные на острове, имеют форму
треугольников, причем любые две граничащие страны имеют
целую общую сторону (то есть вершина одного треугольника не
может лежать на стороне другого). Докажите, что для раскраски
карты этого острова так, чтобы никакие две соседние страны не
были окрашены в один цвет, достаточно трех красок.
1.98. Известно, что на карте некоторой области нет точек,
в которых сходятся границы нечетного числа районов. Докажите,
что такую карту можно раскрасить двумя цветами так, что любые
два соседних района будут покрашены разными красками.
1.99. Докажите, что для раскраски карты, полученной при
пересечении прямых и окружностей на плоскости, достаточно
двух цветов.
1.100. Некоторый коммерческий университет арендует здание для проведения занятий. По понедельникам проводится
8 лекций: микроэкономика, правоведение, менеджмент, маркетинг, статистика, финансы, основы аудита и страхование. Чтение
каждой лекции в отдельности занимает один час, но некоторые
лекции не могут читаться одновременно. В таблице крестиком
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
помечены лекции, которые не могут читаться одновременно.
Определите минимальное время, за которое могут быть прочитаны лекции в понедельник.
МЭ
Микроэкономика
Правоведение
Менеджмент
Маркетинг
Статистика
Финансы
Основы аудита
Страхование
П
+
+
МН
МК
+
+
+
+
+
+
+
+
+
+
+
+
+
СТ
Ф
+
+
+
+
+
+
+
ОА
+
СХ
+
+
+
+
+
+
+
1.7. Задача о максимальном потоке
Одной из задач теории графов является задача определения
максимального потока, протекающего от некоторой вершины s
ориентированного графа (источника) к некоторой конечной вершине
t (стоку). При этом каждой дуге (u, v) графа G приписана некоторая
пропускная способность c(u, v) > 0, определяющая наибольшее
значение потока, который может протекать по данной дуге. Эта задача
и ее варианты могут возникать во многих практических приложениях,
например при определении максимальной интенсивности
транспортного потока между двумя пунктами на карте дорог, при
поиске наиболее выгодного способа транспортировки продукции
между множеством предприятий и множеством магазинов или при
распределении ресурсов в сетях связи.
Ориентированный связный взвешенный граф G = (V, Е), на
котором решается эта задача, называется транспортной сетью
или просто сетью. Для удобства предполагается, что каждая
вершина лежит на некотором пути от источника к стоку, т. е. для
любой вершины v ∈V существует путь s → v → t.
Потоком в G является действительная функция f: V × V → R,
удовлетворяющая следующим трем условиям:
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ограничение пропускной способности: f(u,v) ≤ c(u,v) для всех
u, v ∈ V;
антисимметричность: f (u, v) = – f (v, u) для всех u, v ∈ V;
cохранение потока: для всех u∈ V \ {s, t}
Величина потока определяется как суммарный поток,
выходящий из источника.
Классический метод решения задачи о максимальном потоке
был предложен Фордом и Фалкерсоном. Он базируется на трех
концепциях: разрезы, увеличивающие пути и остаточные сети.
Разрезом называют множество дуг, удаление которых из сети
приводит к «разрыву» всех путей, ведущих из s в t. Пропускная
способность разреза – это суммарная пропускная способность
дуг, его составляющих. Разрез с минимальной пропускной способностью называют минимальным разрезом.
Для заданной транспортной сети G=(V, E) и потока f
остаточной сетью в G, порожденной потоком f, является сеть
Gf , состоящая только из тех ребер исходной сети, по которым
можно направить поток больший 0. Увеличивающий путь – это
простой путь от источника s к стоку t, вдоль которого можно послать больший поток.
Одним из фундаментальных фактов теории потоков в сетях
является классическая теорема о максимальном потоке и минимальном разрезе.
Теорема (Форд и Фалкерсон). Величина каждого потока из
s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий
этого значения.
Теорема устанавливает эквивалентность задач нахождения
максимального потока и минимального разреза, однако не определяет метода их поиска.
На рис. 1.23а показана сеть, у каждого ребра приведена
пропускная способность. На рис. 1.23б показаны потоки в
транспортной сети. Поток f в сети G имеет значение | f | = 8.
Минимальный разрез составляют ребра {{v1,v2}, {v3, v4}, {v5, t}}.
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1.23
Алгоритм Эдмонса-Карпа, реализующий метод ФордаФалкерсона нахождения максимального потока в транспортной
сети, состоит в следующем:
1) для всех ребер G=(V, E) поток равен нулю. Остаточная
сеть Gf совпадает с исходной сетью: Gf ( V, Ef) – сеть с пропускной
способностью cf(u,v) = c(u,v) – f(u,v);
2) в остаточной сети Gf находим кратчайший путь p из источника s в сток t ( cf(u,v)>0 для всех ребер {u, v} ∈ p). Если такого
пути нет, останавливаемся;
3) пускаем через найденный путь (он является увеличивающим
путём) максимально возможный поток:
3.1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью сmin:
сmin = min { cf(u,v) | {u, v} ∈ p}.
3.2. Для каждого ребра {u, v} на найденном пути p увеличиваем поток на сmin, а в противоположном ему – уменьшаем на сmin:
f(u,v) = f(u,v) + сmin; f(v, u) = f(v,u) – сmin.
3.3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер вычисляем
новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;
4) Возвращаемся на шаг 2.
Данный алгоритм сходится для любых вещественных весов
за время O(|V||E|2). Кратчайший путь на шаге 2 ищется, например, поиском в ширину.
Пример. Найдем максимальный поток для графа, изображенного на рис. 1.24.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1.24
Рис. 1.25
1. Остаточная сеть совпадает с исходным графом. С помощью поиска в ширину найдем кратчайший путь p1 = {s, v2, v4, t}.
Минимальная пропускная способность ребра на этом пути
cmin(p1) = 3. Пустим поток мощности 3 по этому пути и модифицируем остаточную сеть (см. рис. 1.25).
2. Как и при первой итерации, найдем кратчайший путь
p2 = {s, v2, v5, t}. И пустим по нему поток мощности cmin(p2) = 1.
Модифицированная остаточная сеть изображена на рис. 1.26.
Рис. 1.26
Рис. 1.27
3. Теперь кратчайший путь состоит из 5 вершин: p3 = { s, v1,
v2, v6, t}. Минимальная пропускная способность ребра на этом
пути cmin(p3) = 3. Граф потока после третьей итерации и остаточная сеть изображены на рис. 1.27.
4. На четвертой итерации алгоритма будет найден кратчайший путь p4 = { s, v1, v5, v6, t}.
По этому пути пустим поток
мощности cmin(p4) = 2. Модифицированная остаточная сеть
изображена на рис. 1.28.
5. Кратчайший путь из источника s в сток t p5 = { s, v3, v1,
v5, v6, t}. Минимальная пропускРис. 1.28
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ная способность ребра на этом пути cmin(p5) = 2. Пустим поток
мощности 2 по этому пути и модифицируем остаточную сеть
(см. рис. 1.29).
6. На последней итерации будет найден кратчайший путь
p6 = { s, v3, v4, v2, v5, v6, t}. По этому пути пустим поток мощности
cmin(p6) = 1.
7. Других путей из источника s в сток t нет. Алгоритм
завершает свою работу. Величина суммарного потока
| f | = 12. Граф потока изображен на рис. 1.30.
Рис. 1.29
Рис. 1.30
Задачи
1.101. Определить максимальный поток от источника к стоку
для графа, изображенного на рисунке.
а)
e)
b)
f)
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
c)
g)
d)
h)
1.8. Алгоритмы поиска кратчайших путей
в графах
Пусть дан граф G = (V, E), ребрам (или дугам в случае ориентированного графа) которого приписаны веса (стоимости), задаваемые взвешенной матрицей смежности A. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной
начальной вершины s ∈ V(G) до заданной конечной вершины
t ∈ V(G) при условии, что такой путь существует, то есть вершины s и t принадлежат одной компоненте связности.
Веса (стоимости), приписанные ребрам, могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в графе не было циклов с суммарным
отрицательным весом. Если такой цикл все же существует и u –
некоторая его вершина, то, двигаясь от s к u, обходя затем этот
цикл достаточно большое число раз и попадая наконец в t, получим путь со сколь угодно малым весом. Таким образом, в этом
случае кратчайшего пути не существует.
Поэтому будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.
Алгоритм Дейкстры (1959 г.) находит кратчайшие пути
от заданной начальной вершины s до всех остальных вершин
графа. Основная идея этого алгоритма: на каждом шаге пытаемся
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
уменьшить кратчайшее расстояние до непросмотренных вершин,
используя очередную вершину, длину пути к которой уменьшить
уже нельзя. А именно: допустим, что кратчайший путь от вершины
s к некоторой вершине u графа G проходит через промежуточную
вершину y. Очевидно, что этот путь должен содержать кратчайший
путь от s к y, так как в противном случае можно было бы уменьшить
длину пути от s к u за счет выбора более короткого пути от s к y.
Таким образом, сначала надо найти кратчайший путь к вершине y.
Для достижения этой цели определяется множество
непросмотренных вершин. Первоначально в нем содержатся
все вершины графа, кроме начальной. На каждом шаге из этого
множества выбирается та из вершин, расстояние до которой от
начальной меньше, чем для других оставшихся вершин. Текущие
кратчайшие расстояния от s до соответствующей вершины
хранятся в массиве distance. Далее пробуем с помощью ребер
выбранной вершины v_min уменьшить длину пути до оставшихся
непросмотренными вершин. Если это удается, то массив distance
корректируется. Алгоритм Дейкстры также использует массив
parent, который содержит номера вершин – элемент parent[k] есть
номер предпоследней вершины на текущем кратчайшем пути из
начальной вершины в k-ю.
Здесь предполагается, что граф задан взвешенной матрицей
смежности w, w[u,v] – вес ребра между вершинами u и v. Если
дуги (ребра) между вершинами u и v не существует, то вместо
нуля в соответствующую ячейку записывается большое число,
равное «машинной бесконечности». Приведем более формальное
описание алгоритма:
1. Инициализация. distance[s] = 0; parent[s]=-1. Для всех
вершин v ∈ V(G) и отличных от s положим: distance[v] = w[s,v],
Множество непросмотренных вершин U = V(G) \ {s}.
2. Выберем вершину v_min такую, что distance[v_min] =
. Если distance[v_min]= ∞, то конец. Иначе
U =U \ {v_min}.
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Для всех вершин u ∈ U, таких что ребро {v_min, u} ∈ E(G)
если distance[u] > distance[v_min] + w[ v_min, u], то
distance[u] = distance[v_min] + w[ v_min, u]
parent[u] = v_min.
4. Если множество U ≠ ∅, то шаг 2. Иначе конец.
Рассмотрим работу алгоритма на примере взвешенного ориентированного графа, изображенного на рис. 1.31.
0
1
2
3
Мн-во
непросмотренных
вершин
{1, 2, 3, 4}
{2, 3, 4}
{2, 4}
{4 }
distance
parent
Тек.
вершина
Номер
итерации
Рис. 1.31. Взвешенный орграф
1
2
0
1
2
3
4
1
3
2
10
10
10
10
∞ ∞ 90 -1
∞ 40 90 -1
50 40 80 -1
50 40 65 -1
0
0
0
0
-1 -1
-1 1
3 1
3 1
0
0
3
2
3
4
После выполнения алгоритма кратчайший путь к каждой
вершине можно найти с помощью обратного прохождения по
предшествующим вершинам массива parent.
Заметим, что если требуется построить путь от начальной
вершины только до одной конечной, то при исключении конечной вершины из множества еще непросмотренных вершин, можно завершать работу алгоритма.
Общая задача нахождения кратчайших путей заключается в
нахождении для каждой упорядоченной пары вершин (v, u) такого пути от вершины v в вершину u, что его длина будет минимальна среди всех возможных путей от v к u. Эта задача мо40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
жет возникнуть, например, если имеется компьютерная сеть и
известно время прохождения сетевого пакета между соседними
компьютерами. Требуется узнать время прохождения пакета от
каждого компьютера к каждому или максимальный временной
интервал для прохождения пакета. Подобные задачи можно решить, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве начальной. Но существует
прямой способ решения, использующий алгоритм Флойда.
Алгоритм Флойда использует матрицу Distance размера
n × n, где n – количество вершин в графе, в которой вычисляются
длины кратчайших путей. Вначале каждый элемент матрицы
Distance равен соответствующему элементу матрицы смежности,
диагональные элементы равны 0. Если в графе дуга между
вершинами u и v отсутствует, то Distance[ u, v] =∞.
Над матрицей Distance выполняется n итераций. После
k-й итерации Distance[v, u] содержит значение наименьшей длины путей из вершины v в вершину u, которые не проходят через
вершины с номером, большим k. Другими словами, между концевыми вершинами пути v и u могут находиться только вершины,
номера которых меньше или равны k.
На k-й итерации для вычисления матрицы Distance
применяется следующая формула:
Distance [v, u] = min (Distance [v, u], Distance [v, k] + Distance [k, u]).
Одновременно с матрицей расстояний ведется построение
матрицы предков parent, которая необходима для вос���������
становления последовательности вершин, составляющих кратчайший
путь. В элемент parent[v, u] записывается номер последней промежуточной вершины на пути от v к u.
Псевдокод алгоритма:
1. Инициализация. Для всех вершин v, u ∈ V(G)
2. Для каждого k от 1 до n рассмотрим все пары вершин {v, u}
и пересчитаем значение Distance [v, u]:
Distance [v, u] = min (Distance [v, u], Distance [v, k] + Distance [k, u]).
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если значение Distance [v, u] изменилось, то parent[v, u] =
parent[k,u].
Рассмотрим
работу
алгоритма
на
примере
взвешенного ориентированного графа,
изображенного на рис. 1.32.
Исходная
матрица
расстояний
Рис. 1.32
алгоритма Флойда:
k
1
Distance =
.
Ниже приведены результаты выполнения каждой из четырех итераций
Distance
parent
2
3
4
Задачи
1.102. Разработайте алгоритм для поиска самого длинного
пути из заданной вершины.
1.103. Определить кратчайший путь от источника к стоку для
графов задания 1.101 с помощью алгоритма Дейкстры.
1.104. Приведите пример ориентированного графа с отрицательными весами ребер, для которого алгоритм Дейкстры дает
неправильные ответы.
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.105. Определить кратчайшие пути между всеми парами
вершин для графов, изображенных ниже:
a)
b)
1.106. Пусть с каждым ребром орграфа связано число r(u,v)
(0 ≤ r(u,v) ≤ 1). Будем интерпретировать r(u,v) как надежность –
вероятность того, что сигнал успешно пройдет по каналу из u в v.
Считая, что события прохождения сигнала по различным каналам независимы, предложите алгоритм для нахождения наиболее
надежного пути между двумя данными вершинами.
1.107. Разработайте алгоритм для решения следующей
задачи: на олимпиаду прибыло N человек. Некоторые из них
знакомы между собой. Можно ли опосредованно перезнакомить
их всех между собой? (Незнакомые люди могут познакомиться
только через общего знакомого.)
2. Алфавитное кодирование
При подготовке этой части были использованы материалы из
книг [6], [11].
2. 1. Основные определения.
Критерий однозначности кодирования
Пусть задан конечный алфавит A= {a1, a2, …, an}. Конечная последовательность символов из A называется словом в алфавите A.
Через A* будет обозначаться множество всех слов в алфавите A.
Пусть A = {a1, a2, …, an} и B = {b1, b2, …, bm} – два алфавита,
первый из которых будет называться алфавитом сообщений,
а второй – алфавитом кодов (кодовых слов). Любое отображение
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
φ: A* → B* может быть названо кодированием слов в алфавите
A словами в алфавите B. При этом для произвольного слова W
в алфавите A слово φ(W) называется его кодом, а сам переход
от W к φ(W) – кодированием.
Кодирование φ называется взаимно однозначным или
однозначно декодируемым, если каждый код сообщения является
кодом ровно одного сообщения.
Пусть задано отображение S букв алфавита A в множество B*
вида: S: a1 → B1, a2 →B2, …, an→ Bn.
Кодирование F(S): A* → B*, удовлетворяющее свойствам:
1) F(S) (ai ) = Bi (i = 1, 2, …, n);
2) F(S) (ai1, ai2, …, aik ) = Bi1, Bi2, . . ., Bik,
где под произведением слов WU понимается приписывание
слова U справа к слову W, называется алфавитным кодированием, задаваемым схемой S.
Естественен вопрос о возможности однозначного декодирования для кодирования, заданного схемой S.
Слово U называется началом или префиксом слова W, если
найдется такое слово V, что W = UV.
Слово U называется концом или постфиксом слова W, если
найдется такое слово V, что W = VU.
Длиной слова называется число букв в нем.
Схема кодирования S: a1 → B1, a2 →B2, …, an→ Bn обладает
свойством префикса или является префиксной, если при i≠ j слово Bi не является префиксом слова Bj.
Теорема 1. Если схема кодирования S: a1 → B1, a2 →B2, …,
an→ Bn обладает свойством префикса, то задаваемое схемой кодирование допускает однозначное раскодирование.
Один из алгоритмов распознавания однозначности декодирования, предложенный А. А. Марковым, заключается в следующем. Рассмотрим алфавитное кодирование, заданное схемой
S: a1 → B1, a2 →B2, …, an→ Bn . С каждым элементарным кодом Bi свяжем всевозможные разложения вида:
Bi = β' Bi1 . . . Bit β". (*)
Рассмотрим граф, одна из вершин которого помечена пустым словом ε, а остальные – словами β, которые встречаются
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
в разложениях вида (*), как в качестве начал элементарных кодов, так и в качестве окончаний.
Для каждого разложения вида (*) проведем дугу из β' в β",
помеченную словом Bi1 . . . Bit. Дуги вида (β, β), ведущие из β
в β, рассматриваться не будут, за исключением случая β = ε. Дуга
(петля) из ε в ε присутствует в графе тогда и только тогда, когда
существуют кодовое слово Bj и последовательность кодовых слов
Р = Bi, ..., Bk, где k ≥ 2, такие что Bj = Bi, ..., Bk. Петле (����������
��������
, ε) припишем слово Bj. Полученный размеченный граф обозначим через
G(S). Справедлива следующая
Теорема 2 (Ал. А. Марков). Для алфавитного кодирования,
заданного схемой S, нарушается условие взаимной однозначности тогда и только тогда, когда в графе G(S) имеется
ориентированный цикл, проходящий через вершину ε.
Теорема 3 (неравенство Макмиллана). Для всякого
однозначно декодируемого кода в m-буквенном кодирующем
алфавите с набором длин кодовых слов li, (i = 1...n) выполнено
неравенство:
Теорема 4. Если для схемы кодирования S: a1 → B1, a2 →B2,
…, an→ Bn, где B1, B2, …, Bn – слова в m-буквенном алфавите,
выполняется неравенство
, то существует схема
кодирования S’: a1 → B1’, a2 →B2’, …, an→ Bn’, где элементарные
коды B1’, B2’, …, Bn’ – слова в том же самом m-буквенном алфавите, что и элементарные коды B1, B2, …, Bn, для которой выполнено свойство префикса и справедливы равенства li’ = li( i = 1...n).
Пример 1. Выяснить, является ли кодирование FS взаимно
однозначным, если S: a1 → 0 =B1, a2 → 10 =B2, a3 → 011 =B3,
a4 → 1011 =B4, a5 → 1111 =B5. Если нет, то указать слово,
декодируемое двумя способами.
Для построения графа G(S) найдем нетривиальные разложения элементарных кодов:
B 2 = (1)B1,
B3 = B1(11) ;
B4 = (1)B1 (11) = (1) B3 = B2 (11).
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
На основании этих разложений строим граф G(S), изображенный на рис. 2.1а.
а)
б)
Рис. 2.1
В графе G(S) отсутствует цикл, проходящий через вершину ε, поэтому схема S задает кодирование с однозначным
раскодированием.
Пример 2. Та же задача для S: a1 → 0 =B1, a2 → 01 =B2,
a3 → 201 =B3, a4 → 1002 =B4.
Соответствующий граф показан на рис. 2.1б. В нем
существует контур, проходящий через вершину ε. Выписывая
слова, приписанные вершинам и дугам контура, получаем слово,
декодируемое неоднозначно: 0100201= 0 1002 01 = 01 0 0 201.
Задачи
Всюду ниже для задания алфавитного кодирования будем
использовать перечисление его правых частей. Так, схеме S:
a1 → 10 =B1, a2 → 01 =B2, a3 → 010 =B3 будет соответствовать код
C = {10, 01, 010}.
2.1. Выяснить, обладает ли код С свойством префикса:
а) C = { a, ab, ba, aab };
б) C = { ba, ab, bba, aab };
в) C = {a, ba, cba, cab, acb };
г) C = { a, ca, cba, cab, acb, ccba };
д) C = { a, ba, bba, … ,(b)n a.. };
е) C = { ca, cba, bca, acb, cbc, cca }.
2.2. Выяснить, является ли код С с кодирующим алфавитом
{0, 1, 2} однозначно декодируемым:
1) С = {01, 201, 112, 122, 0112};
2) С = {001, 021, 102, 201, 001121, 01012101};
3) С = {0, 01, 0010001001};
4) С = {20, 01202, 22, 2001, 2012010, 10201121, 1112};
5) С = 01, 011, 100, 2100, 101210, 001210};
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
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, 10, 210, 121, 0210, 0112}.
2.3. С помощью неравенства Макмиллана выяснить, может
ли набор чисел L быть набором длин кодовых слов однозначно
декодируемого кода в q-значном алфавите:
а) L = ( 1, 2, 2, 3), q = 2;
б) L = ( 2, 2, 2, 4, 4, 4), q = 2;
в) L = ( 1, 1, 2, 2, 3, 3, 3), q = 3;
г) L = ( 1, 1, 1, 2, 2, 2, 2, 3), q = 4;
2.2. Коды с минимальной избыточностью
Рассмотрим кодирования слов в алфавите An = { a1, a2, …,
an} словами в алфавите Bm = { b1, b2, …, bm }. Пусть задано распределение вероятностей p1, p2, …, pn (
) появления
букв a1, a2, …, an в тексте. В качестве характеристики схемы
кодирования S: a1 → B1, a2 →B2, …, an→ Bn может рассматриваться
величина Lср, называемая��������������������������������
������������������������������������������
избыточностью
�������������������������������
кодирования������
, равная математическому
ожиданию
длины
элементарного
кода:
n
L
(S)
=
Lñðср( S ) = ∑ pi | Bi |.
i =1
Для фиксированного распределения вероятностей p1, p2, …, pn
(
) величина L* определяется равенством: L* = minSLcp(S),
где точная нижняя грань берется по схемам S, задающим взаимно
однозначное кодирование.
Кодирования, задаваемые схемой S, для которой Lср(S) = L*, называются m-ичными кодированиями с минимальной избыточностью.
Метод Хаффмена для построения оптимальных двоичных
кодов опирается на следующие утверждения.
1. Среди кодовых слов максимальной длины l оптимального
двоичного кода найдутся два слова, имеющие один и тот же префикс длины l – 1.
2. Если слова wi , wj оптимального m-кода соответствуют вероятностям pi , pj и pi > pj, то длины l(wi) и 1(wj) этих слов связаны
неравенством l(wi) ≤ l(wj).
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Теорема редукции. Пусть С = (w1, w2, ..., wr) – двоичный
код, Р = (p1, p2, ... , pr), p1 ≥ p2 ≥…≥ pr, pi > 0,
= 1 – распределение вероятностей. Пусть wi, wj (слова, имеющие максимальную
длину l и соответствующие вероятностям pi , pj) обладают одинаковыми префиксами w длины l – 1. Положим р' = pi + pj и рассмотрим распределение вероятностей Р' = (p1, ..., pk-1, p',
pk + 1, ..., pi-1, pi + 1, ..., pj-1, pj + 1, ...,pr), в котором вероятности расположены в порядке невозрастания. Код С' = (С   {w}) \ {wi, wj} является (P', 2)-оптимальным тогда и только тогда, когда код С является (Р, 2)-оптимальным.
Процедура Хаффмена для построения оптимального двоичного кода заключается в следующем. Пусть вероятности в распределении p1, p2, …, pn расположены в порядке невозрастания.
Исключим вероятности pn-1 и pn, а их сумму р вставим в оставшийся набор таким образом, чтобы в получившемся новом наборе вероятности не возрастали. Эта процедура повторяется до
тех пор, пока не получится набор из двух вероятностей. Для такого набора вероятностей оптимальным является код, в котором
каждой букве из алфавита сообщений А ставится в соответствие
0 или 1. Исходя из полученного на некотором шаге оптимального кода С в соответствии с теоремой редукции можно перейти
к расширенному оптимальному коду С, имеющему мощность, на
единицу большую, чем код С. Продолжая этот процесс, придем
к искомому оптимальному двоичному коду с n сообщениями.
Пример 1. A = { 1, 2, 3, 4, 5, 6 }, B = {0, 1}, P = { 0,4; 0,2; 0,15;
0,1; 0,1; 0,05}, r =6.
Схема построения оптимального (P, 2) кода выглядит следующим образом:
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Последний столбец представляет собой оптимальный код
для распределения вероятностей P.
Всякому префиксному коду С в q-ичном алфавите В с заданным набором вероятностей Р можно сопоставить помеченное дерево D(C, P, q), называемое в дальнейшем деревом кода С, следующим
образом. Сопоставим каждому кодовому слову висячую вершину,
каждому собственному префиксу внутреннюю вершину, причем
одинаковым префиксам разных кодовых слов сопоставим одну и ту
же внутреннюю вершину. Пустому префиксу сопоставим вершину,
называемую корнем дерева. Соединим две вершины, соответствующие префиксам v и w, ребром с пометкой b, если v = wb или w = vb,
где b – буква алфавита В. Висячим вершинам припишем вероятности, с которыми встречаются соответствующие кодовые слова.
Дерево D(C, P, q) устроено так,
что последовательность пометок, приписанных ребрам цепи, соединяющей
корень дерева с висячей вершиной,
представляет собой соответствующее
кодовое слово.
На рис. 2.2 представлено дерево
оптимального кода для примера 1.
Пример 2. Построить (Р, 3)-оптимальный код для Р = (0,4; 0,3; 0,1; 0,1;
Рис. 2.2. Дерево кода
0,05; 0,05).
Решение. Поскольку r = 6, q = 3
и r/(q – 1) – целое число, то на первом шаге будем склеивать
q – 1 = 2 вероятности. Построение кода проводится аналогично
примеру 1. Схема построения оптимального (Р, 3)-кода имеет вид:
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи
2.4. С помощью процедуры Хаффмена построить двоичный
код с минимальной избыточностью для набора вероятностей Р:
P= (0,4; 0,2; 0,2; 0,1; 0,1);
P = (0,6; 0,1; 0,1; 0,1; 0,1);
P= (0,2; 0,2; 0,2; 0,2; 0,2);
P = (0,5; 0,2; 0,1; 0,09; 0,08; 0,03);
P= (0,3; 0,3; 0,18; 0,06; 0,04; 0,04; 0,04; 0,04);
P = (0,35; 0,25; 0,2; 0,04; 0,03; 0,03; 0,03; 0,03; 0,03; 0,01);
P = (0,3; 0,2; 0,1; 0,1; 0,06; 0,06; 0,06; 0,06; 0,06);
P = (0,4; 0,2; 0,1; 0,05; 0,05; 0,05; 0,05; 0,05; 0,05).
2.5. Построить оптимальный (P, q)-код для заданных P и q:
P=(0,35; 0,2; 0,2; 0,15; 0,1), q = 3;
P=(0,4; 0,15; 0,15; 0,1; 0,1;0,1), q = 3;
P = (0,3; 0,2; 0,2; 0,1; 0,1; 0,1), q = 3;
P = (0,4; 0,1; 0,1; 0,1; 0,1; 0,08; 0,06; 0,06), q = 3;
P = (0,2; 0,2; 0,2; 0,1; 0,1; 0,1; 0,1), q = 4;
P = (0,21; 0,21; 0,17; 0,15; 0,12; 0,08; 0,04; 0,02), q = 4;
P= (0,21; 0,15; 0,14; 0,13; 0,12; 0,11; 0,11; 0,03), q = 4;
P= (0,23; 0,22; 0,18; 0,17; 0,08; 0,04; 0,02; 0,02; 0,02; 0,02), q = 4.
2.6. Для заданного q указать набор вероятностей P, при котором
существует q-ичный префиксный код с заданным набором длин к��
одовых слов L, являющийся (P, q)-оптимальным. Построить этот код:
q = 2, L= (l, 2, 3, 4, 5, 5);
q = 2, L = (2, 2, 2, 3, 3);
q = 2, L= (2, 2, 3, 3, 4, 4, 4, 4);
q = 3, L = (1, 1, 2, 3, 3, 3);
q = 3, L = (1, 2, 2, 2, 2, 2, 2);
q = 4, L= (l, 1, 2, 2, 2, 2, 2, 2);
q = 4, L= (l, 1, 1, 2, 2, 2, 3, 3, 3);
q = 4, L = (l, 1, 2, 2, 2, 2, 2, 2).
2.7. Для префиксного кода C с заданным набором
вероятностей P построить дерево D (C, P, q), соответствующее
коду. Выяснить, является ли код C оптимальным:
C = {1, 00, 01, 02, 20, 21}, P = ( 0,5; 0,1; 0,1; 0,1; 0,1; 0,1);
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
C = {00, 01, 10, 110, 111}, P = (0,25; 0,25; 0,25; 0,125; 0,125);
2.8. Выяснить, существует ли двоичный код с минимальной
избыточностью, обладающий заданной последовательностью L
длин кодовых слов:
a) L = (3, 3, 3, 3);
b) L = (1, 2, 3, 4);
c) L = (2, 3, 3, 3);
d) L = (1, 3, 3, 3, 3);
e) L = (1, 2, 3, 4, 4);
f) L = (1, 2, 3, 4, 4, 4);
g) L = (1, 2, 3, 4, 4, 4, 4);
h) L = (1, 3, 3, 3, 3, 3, 3);
i) L = (3, 3, 3, 3, 3, 3).
2.3. Помехоустойчивое кодирование
Допустим, без ограничения общности, что исходные сообщения и их коды – слова в одном и том же алфавите A= B= {0, 1}.
Исходное сообщение α = a1, a2, …, am, слово длины m в двубуквенном алфавите {0,1}, кодируется словом длины n>m β = b1, b2,
…, bn в том же алфавите.
На множестве слов фиксированной длины в двубуквенном
алфавите {0,1} определим расстояние Хэмминга, полагая для
двух таких слов α = a1, a2, …, ak и α’ = a1’, a2’, …, ak’ d(������������
����������
, ��������
������
’) равным числу позиций, в которых эти слова не совпадают. Для слов
α и β разной длины расстояние Хэмминга равно бесконечности.
Для произвольного алфавита S через Sk обозначим множество всех слов длины k в этом алфавите.
Пусть E – кодирование слов – сообщений α = a1,a2, …, am длины m в двубуквенном алфавите {0,1} словами E(α) длины n в том
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
же алфавите. Кодовым расстоянием назовем число d(E), определенное равенством:
Обозначим через B(β , r) замкнутый шар радиуса r с центром
в точке β, т. е. B(β, r) = {δ | d (β,δ) ≤ r }. Если δ ∈ B(E(α), r),
то считаем, что передавалось сообщение E(���������������������
�������������������
) и произошло не более r ошибок. Принятое сообщение δ заменяем на E(α) и говорим,
что при этом устранено не более r ошибок.
Теорема 1. Кодирование E позволяет исправлять p ошибок
(или меньше) тогда и только тогда, когда 2p + 1 ≤ d(E).
Рассмотрим предложенный Хэммингом способ кодирования,
позволяющий исправлять одну ошибку типа замещения, т. е. когда вместо 0 может появиться 1 либо вместо 1 может появиться
0. Предварительно определим последовательности натуральных
чисел исходя из их представления в двоичной системе счисления.
1) V1 – 1, 3, 5, 7, 9,... – все числа, у которых разряд № 1 равен 1,
2) V2 – 2, 3, 6, 7, 10,... – все числа, у которых разряд № 2 равен 1,
3) V3 – 4, 5, 6, 7, 12,... – все числа, у которых разряд № 3 равен 1,
и т. д. Последовательность Vt начинается с числа 2t-1.
Сообщение α = a1, a2, …, am, слово длины m в двубуквенном
алфавите {0,1}, кодируется словом длины n > m β = b1, b2, …, bn
в том же алфавите. Полагаем k = n – m. Число n подбирается так,
чтобы было выполнено неравенство 2k ≥ n + 1. Это связано с тем, что
если при передаче сообщения длины n происходит не более одной
ошибки, то на выходе возможно получить n + 1 вариантов сообщения и неравенство 2k ≥ n + 1 дает возможность закодировать все эти
варианты. Это неравенство равносильно неравенству 2m≤ 2n/(n + 1).
В кодовом слове β = b1, b2, …, bn разряды с номерами 20=1,
21=2, 22=4, ... , 2k-1 называются контрольными, их число равно
k. Остальные m разрядов информационные, в них помещаются
m букв сообщения a1, a2, …, am.
Контрольные разряды заполняются в соответствии со следующими равенствами:
1) b1 = b3 ⊕ b5 ⊕ b7 ⊕ ... , т. е. сумма всех информационных
разрядов с номерами из V1 (сумма всех, кроме первого),
52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) b2 = b3 ⊕ b6 ⊕ b7 ⊕ ... , т. е. сумма всех информационных
разрядов с номерами из V2 (сумма всех, кроме первого),
3) b4 = b5 ⊕b6 ⊕ b7 ⊕ ..., т. е. сумма всех информационных разрядов с номерами из V3 (сумма всех, кроме первого),
в общем случае b2t-1 =
bi.
Пусть после прохождения через канал связи сообщения b1, b2,
…, bn получено сообщение c1, c2, …, cn, отличающееся от него возможно лишь в позиции с номером I, т. е. при t ≠ I ct = bt. Покажем,
как можно определить двоичное представление I = it…i1 номера I
разряда, в котором, возможно, произошла ошибка замещения.
1) i1 = c1 ⊕ c3 ⊕ c5 ⊕ c7 ⊕ … , т. е. сумма всех разрядов с номерами из V1,
2) i2 = c2 ⊕ c3 ⊕ c6 ⊕ c7 ⊕ …, т. е. сумма всех разрядов с номерами из V2,
3) i3 = c4 ⊕ c5 ⊕ c6 ⊕ c7 ⊕… , т. е. сумма всех разрядов с номерами из V3,
в общем случае ct =
ci.
Для устранения ошибки:
1) вычисляем I,
2) если I =0, то ошибки нет,
3) если I ≠ 0, то bJ = ⌐cJ,
4) из исправленного сообщения извлекаются информационные разряды, напомним, что их номера отличны от 20=1, 21=2,
22=4, ... , 2k-1.
Пример 1. Построим кодовое слово по методу Хэмминга для
сообщения α = 1010. Имеем m = 4, подберем n исходя из неравенства 2m≤ 2n/(n + 1), 16 ≤ 2n/(n + 1), отсюда n = 7.
Кодовое слово β имеет вид b1b2 b3 b4 b5 b6 b7= b1b2 1 b4 010.
Значения контрольных разрядов определяются из равенств:
b1 = b3 ⊕ b5 ⊕ b7 = 1 ⊕ 0 ⊕ 0 = 1,
b2 = b3 ⊕ b6 ⊕ b7 = 1 ⊕ 1 ⊕ 0 = 0,
b4 = b5 ⊕b6 ⊕ b7 = 0 ⊕ 1 ⊕ 0 = 1.
Таким образом, кодовым словом для α является вектор
β = (1011010).
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 2. Декодировать вектор β = (1011110). Имеем n = 7,
m = [log2(27/8)] = 4, k = n – m = 3. Вычислим I = i3 i2 i1
i1 = c1 ⊕ c3 ⊕ c5 ⊕ c7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 =1,
i2 = c2 ⊕ c3 ⊕ c6 ⊕ c7 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0,
i3 = c4 ⊕ c5 ⊕ c6 ⊕ c7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1.
Получаем, что ошибка произошла в разряде I = 1012 = 5. Исправленный кодовый вектор �����������������������������������������
���������������������������������������
= (1011010). Вычеркнем контрольные разряды с номерами 1, 2 и 4 и получим исходное сообщение α = 1010.
Задачи
2.9. Для данного множества С ⊆ Bn найти кодовое расстояние:
С = {11000, 10101, 01110};
С = {111100, 110011, 001111);
С = {00001, 11111, 10100, 01010);
С = {101010, 010110, 000001);
С = {01101010, 11000110, 00011001, 10101100).
2.10. Для каждого из кодов С предыдущей задачи найти:
число ошибок, которые код С обнаруживает;
число ошибок, которые код С исправляет.
2.11. Построить по методу Хэмминга кодовое слово
для сообщения:
a) α = 001;
b) α = 100;
c) α = 1011;
d) α = 1001;
e) α = 10101011;
f) α = 111001111.
2.12. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения α. После передачи по
каналу связи, искажающему слово не более чем в одном разряде,
было получено слово β. Восстановить исходное сообщение:
a) β = 110;
b) β = 101110;
c) β = 011110;
d) β = 0101101;
e) β = 1001011;
f) β = 1100011;
54
g) β = 11011100110;
h) β = 1010101010100;
i) β = 001011110111111.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Детерминированные
и ограниченно-детерминированные
функции
Данная глава существенно использует [6].
3.1. Детерминированные функции
Пусть C – непустой конечный или счетный алфавит, элементы
которого называются буквами. Словом в алфавите С называется
последовательность, составленная из букв этого алфавита. Длина
(число букв) в слове w обозначается |w|. Слово длины 0 (пустое
слово) обозначается символом Λ. Множество всех слов длины s
s
+
обозначим Cs. Тогда C = ∪ C и C * = C 0 ∪ C + . Пусть Cw – мноs ≥1
жество бесконечных слов в алфавите C.
Слово w, получающееся приписыванием конечного слова w2
длины s2 к конечному слову w1 длины s1, называется соединением
(конкатенацией) слов w1 и w2 и обозначается w1w2. При этом
w1 = w] s1 называется префиксом (началом), а слово w2 = [ s w –
2
суффиксом (окончанием) слова w.
Слово w = w(1) w(2)… из Сw называется квазипериодическим,
если существуют такие целые числа n0 и T, что n0 ≥ 1, T ≥ 1 и
w(n + T) = w(n) при n ≥ n0 . Префикс w(1) w(2)…w(n0 – 1) слова
w в этом случае называется предпериодом, число (n0 – 1) – длиной
предпериода, слово w(n0) w(n0 + 1)…w(n0 + T – 1) – периодом слова
w, а число T – длиной периода. Квазипериодическое слово будем
записывать в виде
w(1) w(2)…w(n0 – 1)[ w(n0) w(n0 + 1)…w(n0 + T – 1) ]w.
Символом aw обозначается слово из Cw, в котором w(t) = a
при любом t = 1, 2, … ( a ∈ C ).
Пусть A и B – конечные непустые алфавиты, называемые
входным и выходным, соответственно. Детерминированной
функцией (д.функцией) называется отображение ϕ : A w → B w ,
удовлетворяющее свойствам:
любая s-я буква выходного слова φ(α) является однозначной
функцией первых s символов входного слова α ] s = α(1)α(2)…α(s);
при α = α1α2 и α′ = α1α3 выполнено φ(α)]|α1| = φ(α′)]|α1| .
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Класс всех д.функций обозначим PäA, B .
Пусть А=А1×А2×…×Аn и B=B1×B2×…×Bm, то отображение
ϕ : A w → B w индуцирует m функций от n переменных, каждая
из которых принадлежит своему множеству Аj. Определим эти
функции. Пусть α w = α (1)α (2) α (l )  ∈ A w и β w = ϕ (α w ) =
= β (1) β (2)  β (l )  Тогда α(t) = (α1(t), α2(t), …, αn(t)), где αj(t)∈
Aj, j = 1, …, n, и β(t) = (β1(t), β2(t), …, βm(t)), где βi(t)∈ Bi, i = 1, …, m.
w
w
w
w
Получаем α w = (α 1w , α 2w ,  , α nw ) и β = ( β1 , β 2 ,  , β m ) ,
w
где α wj = α j (1)α j (2) α j (l )  и β i = β i (1) β i (2)  β i (l )  ,
причем β iw = ϕ i (α 1w , α 2w ,  , α nw ) .
Можно поступить наоборот – исходя из функций φi построить
отображение φ.
Переменная xj функции φ(x1, x2, …, xj, …, xn) назывется
существенной, если существуют два набора значений переменных
α 1w = (α1w , α12w ,, α1wj ,, α1wn ) и α 2w = (α1w , α12w ,, α 2wj ,, α1wn ) ,
w
w
отличающиеся только j-й компонентой, что ϕ (α 1 ) ≠ ϕ (α 2 ) . В этом
случае говорят, что функция зависит существенно от переменной
xj, j = 1, …, n. Если переменная xj не является существенной, то она
называется фиктивной (или несущественной), а функция от нее
зависит несущественно.
Можно считать, что д.функция φ реализуется некоторым
дискретным устройством (автоматом) Аφ, работающим в дискретные
моменты времени t = 1, 2, … На вход этого устройства в каждый момент t подается сигнал x(t), а на выходе появляется сигнал y(t).
Рис. 3.1.
Слова xw называют входными, слова yw – выходными,
А называют входным алфавитом автомата Аφ, B – выходным
алфавитом автомата Аφ.
Любые две д.функции φ1 и φ2 называются различимыми, если
существует входное слово, перерабатываемое ими в разные выходные слова. Если такого слова не существует, то эти функции
называются неразличимыми или эквивалентными.
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 1. Выяснить, является ли д.функцией отображение
ϕ : {0,1}w → {0,1}w , определяемое
Решение. Если ориентироваться на форму задания
функции, то естественно предположить, что она не является
детерминированной. Однако указанная в определении функции
зависимость может оказаться «фиктивой», возникшей из-за
неудачного описания функции. Проанализируем эту зависимость.
Пусть t = 2s + 1, где s ≥ 0 . Имеем
y (2 s + 1) = x(2 s + 1) ⊕ y (2 s + 2) = x(2 s + 1) ⊕ x(2 s + 1) = 0 .
Следовательно, при всяком нечетном t выход y(t) равен 0,
то есть является однозначной функцией первых t символов
входного слова. Очевидно, что однозначность имеет место и для
четных значений t. Таким образом, рассматриваемая функция является детерминированной.
Пример 2. Выяснить, является ли д.функцией отображение
ϕ : {0,1}w → {0,1}w , определяемое
Решение. При x(s) = 0 неравенство 3x( s) ≤ x( s + 1) + x( s + 2)
выполняется независимо от значений x(s + 1) и x(s + 2), а при x(s)
= 1 оно не выполняется ни при каких значениях x(s + 1) и x(s + 2).
Следовательно,
то есть отображение φ является д.функцией.
Пример 3. Выяснить, является ли д.функцией отображение
ϕ : {0,1}w → {0,1}w , определяемое условием:
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение. При x(t) = 1 по определению функции имеем y(t) = 0,
а при x(t) = 0 значение y(t) определяется наличием среди последующих входных сигналов 1. Следовательно, данное отображение
не является д.функцией.
Задачи
3.1. Выяснить,
ϕ : {0,1}w → {0,1}w .
является
ли
д.функцией
отображение
а) φ(x(1) x(2)…) = x(2) x(3)…, то есть y(t) = x(t + 1), t ≥ 1;
б) φ(xw) = 10100100010… при любом входном слове xw;
в) φ(x(1) x(2) x(3)…) = x(1) x(2) x(1) x(2) x(3)…, то есть y(1)
= x(1), y(2) = x(2) и y(t) = x(t – 1) при t ≥ 2;
г) φ(x(1) x(2)…) = 0 x(1 + x(2)) x(1 + x(3))…, то есть
y(1) = 0, y(t) = x(1 + x(t)), t ≥ 2;
д) функция φ перерабатывает слово xw в нулевое слово
0w = 000…, если существует такое t, что x(t) = 0; и в единичное
слово 1w = 111… иначе;
е) функция φ перерабатывает слово xw по правилу:
y(s) = 0, если при некотором t ≤ s выполняется неравенство
x(t ) < x(t + 1) + x(t + 2) ; иначе y(s)=1;
ж) функция φ перерабатывает слово xw по правилу:
з) функция φ перерабатывает слово xw по правилу: y(1) = 0
и при s ≥ 2 число нулей в префиксе y(1) y(2) … y(s) слова yw на
единицу больше числа нулей в слове x(1) x(2) … x(s);
и) функция φ перерабатывает слово xw по правилу:
y(1)=x(1) и y (t ) = x(1) ⊕ x(2) ⊕  ⊕ x(t ) при t ≥ 2;
к) функция φ перерабатывает слово xw по правилу:
y (t ) = x(1) ∨ x(2) ∨  ∨ x(t + 1) при t ≥ 1;
л) функция φ перерабатывает слово xw по правилу: y(1) = 1
и y (t + 1) = x(t + 1) → y (t ) при t ≥ 1;
м) функция φ перерабатывает слово xw по правилу:
y (t ) = x(t ) → ( x(t + 1) → x(t ) при t ≥ 1;
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
н) функция φ перерабатывает слово xw по правилу:
y (t ) = x([log 2 t ] + 1) при t ≥ 1;
о) функция φ перерабатывает слово xw по правилу:
t −1
y(1) = y(2) = 1 и y (t ) = x(2 − t ) при t ≥ 3;
п) функция φ перерабатывает слово xw по правилу: y(1) = 1
и y(t)=x(2 + x(t)) при t ≥ 2;
р) функция φ перерабатывает слово xw по правилу:
y(1) = y(2) = 0 и y(t)=x(2 + x(t)) при t ≥ 3;
с) функция φ перерабатывает слово xw по правилу: y(1) = 1
и y(t)=x(2 + y(t–1)) при t ≥ 2;
59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
э) функция φ перерабатывает слово xw по правилу: y(2l) =
x(2l – 1) и y (2l − 1) = x(2l − 1) ∨ y (2l ) , l = 1, 2, …
Каждому слову xw = x(1) x(2) … из {0, 1}w соответствует число
w
ν(x ) из отрезка [0, 1], двоичное разложение которого имеет вид
0, x(1) x(2) … Обратно, если a ∈ [0, 1] , то его двоичное разложение (если a = p 2 n ( n ≥ 1), то рассматривается такое двоичное
разложение, которое содержит бесконечно много нулей) 0, a1a2…
порождает слово <a> = x(1) x(2)…, где x(t) = at ( t ≥ 1).
3.2. Выяснить, является ли д.функцией отображение
ϕ : {0,1}w → {0,1}w .
2
ν (x w )
а) ϕ ( x w ) =
;
в)
;
ϕ(x w ) =
2
3
ν (x w )
ϕ ( x w ) = 1 −ν ( x w ) .
;
г)
2
3.3. Выяснить, является ли д.функцией отображение
б) ϕ ( x w ) =
3.4. Приведенные ниже частичные функции ϕ : {0,1}w → {0,1}w
не определены только на слове 0w = 00… Выяснить, какие из них
можно доопределить до детерминированных, а какие – нельзя.
а)
б)
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.5. Выяснить, эквивалентны ли д.функции φ1 и φ2, если
Для описания д.функций бывает удобно пользоваться
бесконечными информативными деревьями. Пусть А – алфавит,
состоящий из l букв ( l ≥ 1). Через DA обозначим бесконечное
ориентированное корневое дерево, удовлетворяющее следующим
условиям:
а) из каждой вершины дерева, включая корень, выходят
ровно l дуг;
б) в каждую вершину дерева, отличную от корня, входит
только одна дуга, а в корень не входит ни одной;
в) каждой дуге дерева DA приписана некоторая буква
алфавита А, причем разным дугам, выходящим из одной и той же
вершины дерева, приписаны разные буквы.
Корень дерева DA считается вершиной нулевого ранга; если
вершина дерева DA является концом дуги, выходящей из вершины
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
i-го ранга ( i ≥ 0 ), то она называется вершиной (i + 1)-го ранга. Дугой
j-го яруса ( j ≥ 1) называется всякая дуга, выходящая из вершины
(j–1)-го ранга. Каждой бесконечной ориентированной цепи в дереве
DA соответствует вполне определенное слово из множества Aw.
На рис. 3.2 изображен фрагмент дерева DA (где А={0, 1}),
состоящий из трех первых ярусов этого дерева (здесь и в дальнейшем мы предполагаем, что
символу 0 соответствует левая
дуга, выходящая из вершины,
а символу 1 – правая. Жирными
дугами выделена цепь, соответРис. 3.2
ствующая слову 101.
Нагруженное дерево DA,B получается из дерева DA приписыванием
каждой дуге некоторой буквы из алфавита B. Всякой бесконечной
ориентированной цепи в дереве DA,B отвечает слово из множества
Bw, составленное из букв, приписанных дугам этой цепи.
Поэтому можно считать, что
нагруженное дерево DA,B задает
(реализует) вполне определенное
отображение φ: Aw→Bw, являющееся д.функцией.
На рис. 3.3 изображен
фрагмент нагруженного дерева
DA,B (где А={0, 1}, B={0, 1, 2}).
Д.функция, соответствующая этому дереву, «перерабатывает», например, слово 1010 в слово 2012.
Рис. 3.3
3.6. Для д.функции ϕ : {0,1}w → {0,1}w построить фрагмент
нагруженного дерева, содержащий s первых ярусов.
а) y(1) = 1 и y(t) = x(t – 1) при t ≥ 2, s = 3;
б) y(1) = 0 и y(t) = x(t) ⊕ y(t – 1) при t ≥ 2, s = 4;
в) ϕ ( x w ) =
1
,
3
s = 3;
62
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ν (x w )
, s = 4.
4
3.7. Для заданной д.функции ϕ : {0,1}w → {0,1}w изобразить
в нагруженном дереве цепь, соответствующую префиксу x w ] s
w
входного слова x , и написать соответствующий префикс выходного слова.
2
а) φ(xw) = 10100100010… (то есть y(t) = 1 лишь для t = Ci , i =
2, 3, …), x w ]7 = 0101001;
г) ϕ ( x w ) =
б) ϕ ( x w ) =
ν (x w )
2
,
w
w
(1) x ]7 = 1111101, (2) x ]7 = 1010110 ;
3.2. Ограниченно-детерминированные функции
Для д.функции φ и конечного слова α ∈ A* определим
остаточную д.функцию ϕα ( x) = [ | x| ϕ (αx) .
Д.функция φ является ограниченно-детерминированной
(о.д.функцией), если у нее множество остаточных функций конечно.
Элементы этого множества называются состояниями д.функции
φ. Состояние, отвечающее функции φ, называется начальным.
Число различных состояний о.д.функции называется ее весом. Вес
д.функции, не являющейся о.д.функцией, равен ∞.
Класс всех о.д.функций обозначим PîäA, B .
Пусть DA,B – нагруженное дерево, реализующее о.д.функцию φ.
Остаточной функции ϕα (x) отвечает поддерево DA,B (α ) , растущее
из такой вершины v(α) | α | -го ранга, в которой оканчивается цепь,
исходящая из корня и содержащая ровно | α | дуг, причем этой
цепи в i-ом ярусе принадлежит дуга, помеченная буквой α (i ) ∈ A .
Если остаточные функции ϕα1 и ϕα 2 эквивалентны, то
соответствующие им вершины v(α 1 ) и v(α 2 ) и растущие из этих
вершин поддеревья также называются эквивалентными. Вес
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дерева, реализующего о.д.функцию, равен весу этой функции,
а следовательно, максимальному числу попарно неэквивалентных
вершин (или поддеревьев) данного дерева.
Пример 4. Выяснить, является ли о.д.функцией отображение
φ : {0,1}w → {0,1}w, определяемое
и найти ее вес.
Решение. Построим три яруса информативного дерева
заданной функции:
Рис. 3.4
Все вершины дерева разбиваются на 2 класса эквивалентности:
первый класс содержит вершины 0, 2, 6 и т. д., второй – вершины
1, 3, 4, 5 и т. д. Вершинам из первого класса соответствуют
остаточные функции ϕ1s (xw), второго – ϕ s (xw), где s ≥ 0 .
1 0
Таким образом, заданная функция является о.д.функцией веса 2.
Пример 5. Выяснить, является ли о.д.функцией отображение
ϕ : {0,1}w → {0,1}w , определяемое
и найти ее вес.
Решение. Из описания функции следует, что символ,
поступивший в момент времени s, на выходе появится в момент
3s. При росте s задержка становится все больше, что соответствует
бесконечному множеству состояний.
64
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для обоснования того, что данная функция не является
ограниченно-детерминированной,
рассмотрим
остаточные
функции, порожденные словами
, где s ≥ 1, и сравним
значения этих функций на входном слове 1w:
Значит, для разных значений s эти функции попарно не
эквивалентны. Таким образом, вес функции φ равен ∞, т. е. она
не является о.д.функцией.
К такому же выводу можно прийти, построив информативное дерево. Однако потребуется построить 8–9 ярусов, что весьма громоздко.
Задачи
3.8. Эквивалентны ли остаточные операторы ϕα1 и ϕα 2
д.функции ϕ : {0,1}w → {0,1}w ?
2
а) ϕ ( x w ) = 10100100010  (т. е. y(t) = 1 только для t = C i ,
i = 2, 3, …), α1 = 101, α2=010;
б)
, α1 = 10, α2=00101;
w
в) ϕ ( x w ) = ν ( x ) , α1 = 1, α2=001;
2
г) φ(xw)=y(1)y(2)… и
(1) α1 = 10, α2= 010110; (2) α1 = 110, α2= 001;
(3) α1 = 100101, α2= 010101;
д) φ(xw)=y(1)y(2)… и
(1) α1 = 10, α2=010110;
(2) α1 = 010, α2=1001;
е) φ(xw)=y(1)y(2)… и
(1) α1 = 10, α2=011;(2) α1 = 111, α2=00101;(3) α1 = 0101, α2=1000;
65
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ж)
(1) α1 = 00, α2=100101; (2) α1 = 101, α2=110; (3) α1 = 0101,
α2=11111;
з)
(1) α1 = 00, α2=110; (2) α1 = 0110, α2=0101; (3) α1 = 11111,
α2=001001;
и)
(1) α1 = 10, α2=010;
(3) α1 = 110, α2=00101;
(2) α1 = 1110, α2=1011101;
к)
(1) α1 = 011, α2=1111; (2) α1 = 01111, α2=00111; (3) α1 = 0100,
α2=111010;
л) φ(xw)=y(1)y(2)… и y(t) есть t-я цифра после запятой в дв��
оичном разложении числа 9/20,
(1) α1 = 0, α2=001110; (2) α1 = 101, α2= 1001011; (3) α1 = 1101,
α2= 00100;
м) φ(xw)=y(1)y(2)… и y(t) есть t-я цифра после запятой в дв��
оичном разложении числа 23/28,
(1) α1 = 1, α2= 0110; (2) α1 = 10, α2= 00110; (3) α1 = 110,
α2= 111101111;
3.9. Выяснить, является ли φ1 остаточным оператором
функции ϕ : {0,1}w → {0,1}w ?
w
 y (1) = 0,
а) ϕ ( x ) : 
 y (t ) = x(t ) ⊕ y (t − 1), t ≥ 2,
 y (1) = 1,
ϕ1 ( x w ) : 
 y (1) = 0,
б) ϕ ( x ) : 
 y (t ) = y (t − 1),
w
 y (t ) = y (t − 1),
t ≥ 2,
 y (1) = 0,
ϕ1 ( x w ) : 
66
 y (t ) = y (t − 1),
t ≥ 2;
t ≥ 2;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
в)
г)
д)
е)
w
ж) ϕ ( x ) : y (t ) = x(t ), t ≥ 1 ,
з)
3.10 Выяснить, является ли функция φ : {0,1}w → {0,1}w о.д.функцией, и найти ее вес.
а)
б)
в)
г)
67
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.3. Представление ограниченнодетерминированных функций диаграммами,
таблицами, каноническими уравнениями
Пусть Q = {q0, q1, …, qs} – множество всех состояний
о. д. функции φ. Сопоставим функции φ ориентированный граф Γφ:
1) множеством вершин Γφ является множество Eφ = {0, 1, …,
s}, причем вершина j соответствует состоянию qj;
2) еслиφi и φj –остаточные функции, реализуемыесоответственно
состояниями qi и qj, и φj является остаточной функцией функции φi,
порождаемой словом a, причем φi(axw) = bφj(xw), то в графе Γφ имеется
дуга (i, j), ей приписывается выражение a(b);
3) дуга (i, j) существует в графе Γφ только при выполнении
условий пункта 2).
68
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Начальное состояние будем обозначать q0. Если из вершины
i в вершину j идут m дуг, которым приписаны выражения a1(b1),
a2(b2), …, am(bm) (a p ≠ a q при p ≠ q ), то будем соединять вершины i и j только одной дугой (i, j) и приписывать ей все выражения ap(bp) (p = 1, 2, …, m). Ориентированный граф Γφ называется
диаграммой Мили функции φ.
С диаграммой Γφ функции φ можно связать две функции:
1) F: Q×A → B (функция выходов);
2) G: Q×A → Q (функция переходов).
Функции F и G по графу Γφ определяются так: по паре (a, j)
находим вершину j и такую дугу, исходящую из j, которой приписан входной символ a (пусть эта дуга есть (j, l)); значением
функции F на паре (a, j) является выходной символ, приписанный
дуге (j, l) и стоящий в скобках за символом a; значение функции G на паре (a, j) совпадает с l, то есть равно «номеру» того
состояния, которое «является концом» дуги (j, l).
Система уравнений
q(0) = q0,
q(t) = G(q(t–1), x(t)),
y(t) = F(q(t–1), x(t)),
где x(t ) ∈ A , y (t ) ∈ B , q (t ) ∈ Q (t = 1, 2, …) и q 0 ∈ Q ,
называется каноническими уравнениями функции φ с начальным
условием q0.
Замечание. С помощью диаграмм Мили и канонических
уравнений можно задавать и детерминированные функции,
которые не являются о.д.функциями.
Если φ – о.д.функция, то функции G(q(t–1), x(t)) и F(q(t–1), x(t))
и аргументы, от которых они зависят, принимают конечное число
значений. Поэтому возможно табличное задание о.д.функции φ
с помощью канонической таблицы:
x(t)
q(t–1)


j
F(a, j)
G(a, j)




a
y(t–1)

69
q(t)

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 6. Построить диаграмму Мили, каноническую
таблицу и канонические уравнения функции ϕ : {0,1}w → {0,1}w ,
где
Решение. В примере 4 было построено информативное
дерево данной функции, тогда «усеченное» дерево имеет вид:
Рис. 3.5
Вес функции равен 2. Два класса эквивалентности описаны
в примере 4. Строим диаграмму Мили (начальное состояние
помечено 0):
Строим таблицу:
x(t)
0
0
1
1
q(t–1)
0
1
0
1
y(t)
0
0
1
0
q(t)
1
1
0
1
Канонические уравнения и начальное условия заданной
функции имеют вид:
q(0) = 0,
70
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
q(t) = x (t ) ∨ q (t − 1) ,
y(t) = x(t ) & q (t − 1) .
Задачи
3.11. Построить диаграмму Мили, каноническую таблицу
и канонические уравнения функции ϕ : {0,1}w → {0,1}w , где
а)
б)
в)
г)
д)
е)
ж)
з)
и)
71
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
к)
л)
м)
н)
о)
п)
72
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Список литературы
1. Андерсон, Дж. А. Дискретная математика и комбинаторика:
пер. с англ. / Дж. А. Андерсон. – М.: Вильямс, 2004. – 960 с.
2. Анндрухаев, Х. М. Сборник задач по теории вероятностей
/ Х. М. Анндрухаев. – М.: Просвещение, 1985. – 100 с.
3. Башкин, М. А. Дискретная математика: учеб. пособие
/ М. А. Башкин, Н. И. Гусарова, В. А. Короткий. – Ч. 1. – Рыбинск:
Из-во РГАТУ, 2012. – 100 с.
4. Булгакова, И. Н. Дискретная математика. Элементы
теории. Задачи и упражнения: учеб. пособие / И. Н. Булгакова,
Г. Ф. Федотенко. – Воронеж: Из-во ВГУ, 2004. – 62 с.
5. Виленкин, Н. Я. Комбинаторика / Н. Я. Виленкин,
А. Н. Виленкин, П. А. Виленкин. – М.: ФИМА, 2006. – 400 с.
6. Гаврилов, Г. П. Задачи и упражнения по дискретной
математике: учеб. пособие / Г. П. Гаврилов, А. А. Сапоженко. –
3-е изд., перераб. – М.: ФИЗМАТЛИТ, 2005. – 416 с.
7. Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-Пресс, 2007.
– 152 с.
8. Горбатов, В. А. Основы дискретной математики: учеб. пособие для студентов вузов / В. А. Горбатов. – М.: Высш. шк., 1986.
– 311 с.
9. Горбачёв, Н. В. Сборник олимпиадных задач по математике
/ Н. В. Горбачёв. – М.: МЦНМО, 2004. – 560 с.
10. Дурнев, В. Г. Элементы дискретной математики
/ В. Г. Дурнев, М. А. Башкин, О. П. Якимова. – Ярославль: ЯрГУ,
2007. – Ч. 1. – 168 с.
11. Дурнев, В. Г. Элементы дискретной математики
/ В. Г. Дурнев, М. А. Башкин, О. П. Якимова. – Ярославль: ЯрГУ,
2007. – Ч. 2. – 168 с.
12. Ерош, И. А. Дискретная математика. Комбинаторика
/ И. А. Ерош. – СПб.: ГУАП, 2001. – 37 с.
13. Задачи по дискретной математике / сост.: М. А. Башкин,
О. П. Полякова. – Ярославль: ЯрГУ, 2005. – Ч. 1. – 32 с.
73
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
14. Канунников, А. Л. Комбинаторика / А. Л. Канунников,
С. Л. Кузнецов. – М.:ЦПИ МГУ, 2009. – 31 с.
15. Корнилов, П. А. Элементы дискретной математики
/ Корнилов П. А., Никулина Н. И., Семенова О. Г. – Ярославль:
ЯГПУ им. К. Д.Ушинского, 2005. – 91 с.
16. Логинов, Б. М. Введение в дискретную математику
/ Б. М. Логинов. – Калуга, 1998. – 423 с.
17. Новиков, Ф. А. Дискретная математика для программистов
/ Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.
74
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оглавление
1. Графы.............................................................................................3
1.1. Основные определения...............................................................3
1.2. Представление графа в памяти компьютера.
Алгоритмы обхода графа.........................................................12
1.3. Деревья. Остов минимального веса........................................18
1.4. Плоские и планарные графы....................................................22
1.5. Циклы в графах.........................................................................25
1.6. Независимость и раскраски.....................................................28
1.7. Задача о максимальном потоке...............................................33
1.8. Алгоритмы поиска кратчайших путей в графах....................38
2. Алфавитное кодирование..........................................................43
2. 1. Основные определения. Критерий однозначности
кодирования...............................................................................43
2.2. Коды с минимальной избыточностью....................................47
2.3. Помехоустойчивое кодирование.............................................51
3. Детерминированные и ограниченно-детерминированные
функции.....................................................................................55
3.1. Детерминированные функции.................................................55
3.2. Ограниченно-детерминированные функции.........................63
3.3. Представление ограниченно-детерминированных функций
диаграммами, таблицами, каноническими уравнениями.....68
Список  литературы......................................................................73
75
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Башкин Михаил Анатольевич
Якимова Ольга Павловна
Дискретная математика
Часть 2
Сборник задач
Редактор, корректор М. В. Никулина
Правка, верстка Е. Б. Половкова
Подписано в печать 01.07.2013. Формат 60×841/16.
Усл. печ. л. 4,42. Уч.-изд. л. 4,0
Тираж 40 экз. Заказ
.
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрГУ.
Ярославский государственный университет
им. П. Г. Демидова.
150000, Ярославль, ул. Советская, 14.
76
Документ
Категория
Без категории
Просмотров
161
Размер файла
3 457 Кб
Теги
дискретное, башкина, 1544, математика
1/--страниц
Пожаловаться на содержимое документа