Задания для самостоятельной работы
СОДЕРЖАНИЕ
| Введение | |
| Литература | |
| Тема. Теория графов | |
| Вопросы программы | |
| Решение типовых задач | |
| Задания для самостоятельной работы |
Введение
Предмет дискретной математики охватывает такие разделы математического знания, как комбинаторика, математическая логика и теория алгоритмов, теория графов, теория кодирования и т.д. Дискретная математика считается одной из наиболее динамичных областей знания. Наибольшей областью применения методов дискретной математики сегодня является область компьютерных технологий. Причем это связано как с функционированием компьютерной техники, так и с совершенствованием работы различного рода компьютерных программ. На грани дискретной математики и программирования появляются новые дисциплины, такие как разработка и анализ вычислительных алгоритмов, нечисленное программирование, комбинаторные алгоритмы, алгоритмизация процессов.
Цель методических рекомендаций – научить студентов основам дискретной математики, показать ее роль в современных компьютерных технологиях, рассмотреть методы, применяемые для решения широкого круга задач.
Методическое пособие направлено на изучение такой темы дискретной математики, как теория графов.
По указанному разделу учебным планом заочного обучения предусмотрен зачет.
Настоящие рекомендации помогут студентам-заочникам овладеть базовыми понятиями по теории графов через систему задач. При самостоятельной подготовке студент обязан изучить решение типовой задачи, данное в рекомендациях и решить аналогичные задачи из "Заданий для самостоятельной работы". Для изучаемого раздела приведены вопросы программы обязательные для усвоения студентами.
Для овладения алгоритмами решений алгебраических задач нужно изучить основные понятия по данной теме и решить достаточное количество задач.
ЛИТЕРАТУРА
Основная
1. Новиков Ф.А. Дискретная математика для программистов./ СПб: Питер, 2000. – 304с.: ил.
2. Иванов Б.И. Дискретная математика. Алгоритмы и программы: Учебное пособие. - М.: Лаборатория базовых знаний, 2002 – 288с.
3. Капитонова Ю.В., Кривой С.Л., Летичевский А.А., Луцкий Г.М. Лекции по дискретной математике./ СПб.: БХВ-Петербург, 2004. – 624 с.: ил.
4. 5. Гаврилов Г.П., Сапоженко А.А., Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2005 – 416с.
Дополнительная
6. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие. – Ростов н/Д: «Феникс», Харьков: «Торсинг», 2003. – 144с.
Тема. Теория графов.
Вопросы программы:Графы, виды графов. Вершины и ребра графа. Степень вершины. Теорема Эйлера о рукопожатиях. Операции над графами. Изоморфизм графов. Эйлеровы и гамильтоновы графы. [1] (c. 189-193), [3] (c.241-253).
Представления графов в ЭВМ. Матрицы смежности и инцидентности. Списки смежности. Массивы дуг. Обходы графа в ширину и глубину. [1] (c. 201-203), [3] (c.265-269).
Маршруты, цепи циклы графов. Геодезические цепи. Разделяющее множество. Теорема Менгера. Связность графа. [1] (c. 195-197), [3] (c.253).
Укладки графов, планарность. Формула Эйлера. Деревья и их свойства, каркасы. Основная теорема о деревьях. Алгоритмы Краскала и Дейкстры. [1] (c. 234-259), [3] (c.289-304).
Раскраска графа. Хроматическое число. Теорема о пяти красках. Гипотеза о четырех красках. [1] (c. 281-289), [3] (c.277-283).
Решение типовых задач
Задача 1. Установите, являются ли указанные графы изоморфными?
Решение: Занумеруем вершины одного из графов в произвольном порядке цифрами, а другого буквами. Требуется установить, существует ли биективное отображение вершин первого и второго графов, при котором каждому ребру одного графа будет соответствовать ребро другого графа.
Перебирать все возможные биекции (а их ровно 9!) слишком долго и нерационально, поэтом воспользуемся тем фактом, что степени вершин при изоморфизме не изменяются.
Составим схему степеней вершин первого графа (первое число номер вершины, второе число степень вершины): 1-2, 2-2, 3-2, 4-2, 5-3, 6-2, 7-2, 8-3, 9-4.
Составим схему степеней вершин второго графа: a-2, b-2, c-2, d-2, e-3, f-2, g-2, h-4, k-2.
Если изоморфизм графов существует, то вершине 9 первого графа соответствует вершина h второго.
Вершина 9 первого графа смежная с вершинами 5 и 8 степени 3. Вершина h второго графа смежная вершинам e и f степени 3. Следовательно, вершины 5 и 8 изоморфны вершинам e и f. Пусть 5 изоморфна e, а 8 изоморфна f.
Вершина 9 первого графа изоморфна двум вершинам 6 и 7 степени 2. Вершина h второго графа смежная вершинам g и k степени 2. Следовательно, вершины 6 и 7 изоморфны вершинам g и k. Пусть 6 изоморфна g, а 7 изоморфна k.
Для вершины 5 первого графа осталась вершина 3 степени 2, которая должна соответствовать вершине c, а для вершины 4 соответствует вершина d.
Остается две вершины 1 и 2, которые изоморфны вершинам a и b.
Таким образом, установим изоморфизм: 1®a, 2®b, 3®c, 4®d, 5®e, 6®g, 7®k, 8®f, 9®h.
Тогда (1,2)®(a,b), (1,3)®(a,c), (2,4)®(b,d), (3,5)®(c,e), (4,8)®(d,f), (5,6)®(e,g), (7,8)®(k,f), (5,9)®(e,h), (6,9)®(g,h), (7,9)®(k,h) и (8,9)®(f,h).
Следовательно, графы изоморфны.
Задача 2. Для данного графа найти максимальное количество геодезических цепей, соединяющих вершины 1, 25 и разделяющее множество, содержащее минимальное количество вершин.
Решение: Для того, чтобы построить максимальное количество геодезических цепей, будем строить их по следующему правилу. Смежные вершины включены в цепь, если эти вершины не включены ни в одну ранее построенную геодезическую цепь и последующая вершина лежит по возможности «выше» предыдущей.
Строим первую геодезическую цепь: 1-2 (вершина 2 смежная вершине 1 и лежит «выше»), 2-5-12-18-20-25.
Строим вторую геодезическую цепь: 1-3-8-13 (вершину 5 выбрать нельзя, так как она принадлежит первой цепи) 13-15-19-24-25.
Строим третью геодезическую цепь: 1-6-11-16-22 (вершину 19 выбрать нельзя, так как она принадлежит второй цепи) 22-23-25.
Строим четвертую геодезическую цепь: 1-10-14-17-25.
Построить пятую геодезическую цепь нельзя, так как цепь, проходящая через вершину 4, обязательно пройдет через вершину 10, которая входит в четвертую цепь.
Итак, максимальное количество геодезических цепей – четыре.
По теореме Менгера, минимальное количество вершин разделяющего множества равно максимальному количеству геодезических цепей, то есть необходимо найти разделяющее множество из четырех вершин.
Пятую геодезическую цепь невозможно было построить, так как она должна была пройти через 10 вершину. Поэтому включим ее в разделяющее множество.
Для того чтобы найти вторую вершину разделяющего множества, выберем на третьей геодезической цепи вершину таким образом, чтобы нельзя было попасть в вершину 25 с помощью цепи, не смежной первой и второй геодезической цепям. Такой вершиной является вершина 6 (если взять вершину 11, то существует обходной путь 6-9-14).
Для того чтобы найти третью вершину разделяющего множества, выберем на второй геодезической цепи вершину таким образом, чтобы нельзя было попасть в вершину 25 с помощью цепи, не смежной первой геодезической цепям. Такой вершиной является вершина 3 (если взять вершину 8, то существует обходной путь 3-11).
Четвертую вершину выберем на первой геодезической цепи, это вершина 2 (если взять вершину 5, то существует обходной путь 2-8).
Итак, разделяющее множество S={10, 6, 3, 2}.
Задача 3. Для данного графа составить матрицу смежности, матрицу инцидентности. Провести поиски в глубину и в ширину.
Решение: Для того чтобы составить, матрицу смежности определим вначале размерность матрицы. Так как граф содержит 9 вершин, то матрица смежности будет состоять из 9 строк и 9 столбцов. Если существует ребро (i, j), то в матрице на i-ой строке в j-ом столбце будет находиться символ 1, если такого ребра нет, то символ 0. В итоге получим:
Для того чтобы составить матрицу инцидентности необходимо занумеровать ребра графа: (1, 2) – I, (1, 5) – II, (2, 3) – III, (2, 5) – IV, (2, 6) –V, (3, 4) – VI, (3, 7) – VII, (6, 8) – VIII, (6, 9) – IX, (8, 9) – X.
Так как граф содержит 10 ребер, матрица инцидентности будет состоять из 9 строк и 10 столбцов. Если ребро i инцидентно вершине j, то в i-ой строке j-ом столбце матрицы будет находиться символ 1, если ребро i не инцидентно вершине j, то в i-ой строке j-ом столбце матрицы будет находиться символ 0. В итоге получим:
Для поиска в глубину или ширину введем понятие очереди. Если есть некоторая вершина, то по отношению к ней зададим упорядоченное множество вершин, смежных ей в порядке возрастания номера. Если в это множество необходимо добавить вершину, то она вносится в конец очереди.
Для поиска в глубину необходимо задать упорядоченное множество всех вершин графа, по следующему правилу: начинаем перечисление с первой вершины. Для нее зададим множество всех вершин, ей смежных и упорядочим по возрастанию номеров. Из полученной очереди извлечем номер первой вершины и перенесем его в искомое, упорядоченное множество, а в очередь добавим все вершины смежные изъятой, не содержащиеся в очереди. Продолжим процесс, пока искомое множество не будет содержать всех вершин графа, а очередь будет пустой.
| 2, 5 | |
| 1, 2 | 5, 3, 6 |
| 1, 2, 5 | 3, 6 |
| 1, 2, 5, 3 | 6, 4, 7 |
| 1, 2, 5, 3, 6 | 4, 7, 8, 9 |
| 1, 2, 5, 3, 6, 4 | 7, 8, 9 |
| 1, 2, 5, 3, 6, 4, 7 | 8, 9 |
| 1, 2, 5, 3, 6, 4, 7, 8 | 9 |
| 1, 2, 5, 3, 6, 4, 7, 8, 9 |
Поиск в глубину: 1, 2, 5, 3, 6, 4, 7, 8, 9.
Для того, чтобы задать поиск в ширину, необходимо в алгоритме поиска в глубину из очереди извлекать последний номер. Таким образом, получим:
| 2, 5 | |
| 1, 5 | 2 |
| 1, 5, 2 | 3, 6 |
| 1, 5, 2, 6 | 3, 8, 9 |
| 1, 5, 2, 6, 9 | 3, 8 |
| 1, 5, 2, 6, 9, 8 | 3 |
| 1, 5, 2, 6, 9, 8, 3 | 4, 7 |
| 1, 5, 2, 6, 9, 8, 3, 7 | 4 |
| 1, 5, 2, 6, 9, 8, 3, 7, 4 |
Поиск в ширину: 1, 5, 2, 6, 9, 8, 3, 7, 4.
Задание 4. Для заданного графа составить остовый подграф наименьшего веса с помощью алгоритма Краскала.
3 4
5 2 7
4 2 6 3 3
5 2 3 1
1 3 5 3 2 4
4 5 3
Решение: Для решения задачи упорядочим все ребра графа по весу в порядке убывания: (7, 12) – 7, (5, 7) – 6, (1,5) – 5, (4, 5) – 5, (5, 6) – 5, (6, 10) – 5, (1, 2) – 4, (3, 6) – 4, (4, 7) – 4, (9, 10) – 4, (2, 4) – 3, (3, 5) – 3, (6, 8) – 3, (7, 8) – 3, (9, 11) – 3, (9, 12) – 3, (10, 11) – 3, (2, 5) – 2, (7, 9) – 2, (8, 9) – 2, (8, 10) – 2, (1, 3) – 1, (11, 12) – 1.
Начинаем выбирать ребра из перечисленных ребер в обратном порядке. Последнее ребро выбирается всегда (11, 12). Каждое последующее ребро выбирается в том случае, если его выбор не образует циклов в новом подграфе. Так следующее ребро (1, 3) тоже выбираем. Выбранные ребра рекомендуется выделять на исходном графе другим цветом. Аналогично выбираем следующие ребра: (8, 10) , (8, 9), (7, 9), (2, 5), (10, 11) . Ребро (9, 12) выбрать нельзя, так как образуется цикл: 9-8-10-11-12. Продолжаем выбор: (9, 11), (7, 8) – нельзя; (6, 8) , (3, 5) , (2, 4) выбираем; (9, 10) – нельзя; (4, 7) выбираем; (7, 12), (5, 7), (1,5), (4, 5), (5, 6), (6, 10), (1, 2), (3, 6).
Для контроля, количество выбранных ребер в связном конечном графе равно количеству вершин минус один, то есть в нашем случае 12 -1=11.
Для определения веса выбранного подграфа, достаточно просуммировать веса выбранных ребер: 1+1+2+2+2+2+3+3+3+3+4=26.
Замечание: Если начать выбор с первого ребра (вес этого ребра самый большой), то по указанному алгоритму можно выбрать подграф максимального веса.
Задание 5. Для заданного графа найти путь из вершины 1 в вершину 12 наименьшего веса.
3 4 7
2 5 6 2 3
4 5 2 1 3 1
3 2 2
1 5 3 4
4 5
Решение: Решение состоит в пересчете меток для каждой вершины. Для этого каждой вершине ставим в соответствие первоначальную метку ¥. Далее определим два множества: множество вершин P, метки которых не окончательные; множество вершин T, метки которых окончательны (минимальны).
Вначале P=Æ, T={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.
1 шаг. Поместим во множество P первую вершину пути 1 с меткой 0, удаляя эту вершину из множества T, и пересчитаем метки всех вершин, в которые можно попасть из вершин множества P (1). Из вершины 1 можно попасть в вершину 2 за 4. То есть вершине 2 ставим в соответствие новую метку 4. Аналогично, вершине 5 метку 2, вершине 3 метку 1.
2 шаг. Из всех вершин множества T выбираем вершину, метка которой самая наименьшая (если таких вершин несколько, то можно выбрать произвольную), и перемещаем ее во множество P. Для остальных вершин множества T пересчитаем все метки.
Продолжаем этот процесс до тех пор, пока во множество P не войдут все вершины, а множество T станет пустым. Процесс пересчета и выбора меток оформим в виде таблицы:
| ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ |
| 0 | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ |
| ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||
| 1 | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||
| 4 | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||
| 4 | ¥ | ¥ | ¥ | ¥ | ¥ | ||||||
| 5 | ¥ | ¥ | ¥ | ||||||||
| 7 | ¥ | ¥ | ¥ | ||||||||
| 8 | ¥ | ¥ | |||||||||
| 9 | |||||||||||
| 10 | |||||||||||
| 10 | |||||||||||
| 12 | |||||||||||
| 12 |
3 шаг. Метка последней вершины равна 12. Следовательно, длина кратчайшего пути из вершины 1 в вершину 12 равна 12. Восстановим этот путь. В вершину 12 за 12 можно попасть из вершины 9. В вершину 9 можно попасть за 9 из вершины 8. В вершину 8 можно попасть за 8 из вершины 6. В вершину 6 можно попасть за 5 из вершины 3. В вершину 3 за 1 можно попасть из вершины 1. Таким образом, искомый путь: 1 – 3 – 6 – 8 – 9 – 12.
Задание 6. Для заданного графа найти максимальный поток и разрез минимального веса.
s
14 12
16 17
13 9 4 3 10
5 10 7 6 5
11 11
17 13 17
t
Решение: Для решения задачи необходимо перебрать все возможные вершинно не пересекающиеся простые цепи из истока s в сток t. На каждой такой цепи определить дугу с минимальной пропускной способностью, с учетом предыдущих цепей и добавить каждой дуге найденную величину.
Если все возможные цепи построены и определены величины потока для каждой дуги, то из множества всех дуг, в которых величина потока равна пропускной способности можно составить разрез, такой, что его вес будет равен величине потока. Тогда по теореме Форда-Фалкерсона, найденный поток будет максимальным, а соответствующий разрез – минимальным.
Для определения путей занумеруем вершины графа:
14 12
13 16 17
9 4 3 10
5 10 7 6 5
17 11 13 11 17
Начинаем перебирать все возможные цепи либо «справа» либо «слева» на выбор. Выберем вариант перебора цепей «справа».
Первая возможная цепь: s-1-5-t. Дуга минимального веса – (1,5) с пропускной способностью 13. Поэтому всем дугам этой цепи (s,1), (1,5), (5,t) сопоставим величину потока равную 13. Отметим, что ребро (1,5) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13 12
13 16 17
13 9 4 3 10
5 10 7 6 5
17 11 13 11 17
13
Вторая возможная цепь: s-1-6-t. С учетом предыдущей цепи дуга минимального веса – (s,1) с пропускной способностью 14-13=1. Поэтому всем дугам этой цепи (s,1), (1,6), (6,t) сопоставим величину потока равную 1. Отметим, что ребро (s,1) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+1 12
13 16 17
13 9 1 4 3 10
5 10 7 6 5
1
17 11 13 11 17
13
Третья возможная цепь: s-3-6-t. С учетом предыдущих цепей дуга минимального веса – (3,6) с пропускной способностью 5. Поэтому всем дугам этой цепи (s,3), (3,6), (6,t) сопоставим величину потока равную 5. Отметим, что ребро (3,6) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+1 12
13 5 16 17
13 9 1 4 3 10
5 5 10 7 6 5
1+5
17 11 13 11 17
13
Четвертая возможная цепь: s-3-7-t. С учетом предыдущих цепей дуга минимального веса – (3,7) с пропускной способностью 10. Поэтому всем дугам этой цепи (s,3), (3,7), (7,t) сопоставим величину потока равную 10. Отметим, что ребро (3,7) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+1 12
13 5+10 16 17
13 9 1 4 3 10
5 510 10 7 6 5
1+5
17 11 13 11 17
13 10
Пятая возможная цепь: s-4-7-t. С учетом предыдущих цепей дуга минимального веса – (7,t) с пропускной способностью 13-10=3. Поэтому всем дугам этой цепи (s,4), (4,7), (7,t) сопоставим величину потока равную 3. Отметим, что ребро (7,t) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+1 12
13 5+10 16 3 17
13 9 1 4 3 10
5 510 10 3 7 6 5
1+5
17 11 10+3 11 17
13 13
Шестая возможная цепь: s-4-8-t. С учетом предыдущих цепей дуга минимального веса – (4,8) с пропускной способностью 4. Поэтому всем дугам этой цепи (s,4), (4,8), (8,t) сопоставим величину потока равную 4. Отметим, что ребро (4,8) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+1 12
13 5+10 16 3+4 17
13 9 14 4 3 10
5 510 10 3 7 6 5
1+5 4
17 11 10+3 11 17
13 13
Седьмая возможная цепь: s-2-8-t. С учетом предыдущих цепей дуга минимального веса – (2,8) с пропускной способностью 3. Поэтому всем дугам этой цепи (s,2), (2,8), (8,t) сопоставим величину потока равную 3. Отметим, что ребро (2,8) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+13 12
13 5+10 16 3+4 17
13 9 14 4 3 3 10
5 510 10 3 7 6 5
1+5 4+3
17 11 10+3 11 17
13 13
Восьмая возможная цепь: s-2-9-t. С учетом предыдущих цепей дуга минимального веса – (s,2) с пропускной способностью 12-3=9. Поэтому всем дугам этой цепи (s,2), (2,9), (9,t) сопоставим величину потока равную 9. Отметим, что ребро (s,2) максимально загружено, и значит, его нельзя использовать в остальных цепях.
14 13+13+9 12
13 5+10 16 3+4 17 9
13 9 14 4 3 3 10