Выдержка из текста работы
Граф есть упорядоченная пара (V, E), где V — непустое множество, называемое множеством вершин; E — неупорядоченное бинарное отношение на V, т.е. V&V. E называют множеством ребер. Говорят, что ребро, принадлежащее множеству E, инцидентно вершинам, которые оно соединяет. Таким образом, мы определим неориентированный граф. Он полностью определяется списком вершин и указанием, какие пары вершин имеют соединяющие их ребра (в случае нагруженного графа каждому ребру или дуге еще приписывается вес). Во многом базовые определения теории графов обязаны своему появлению Л. Эйлеру (1707-1782), решившему в 1736 г. широко известную «задачу о кенигсбергских мостах».
Ориентированный граф — упорядоченная пара (V, E), где V — множество вершин, а E — упорядоченное отношение на V (т.е. V&V). В этом случае E называют множеством дуг. Первая и вторая вершины дуги называются соответственно начальной и конечной.
В большинстве практических задач (как и в данном задании) рассматриваются графы с конечным числом ребер и вершин; их называют конечными. Для аналитического решения большинства задач желательно отойти от графического представления графов в пользу их матричного описания.
Вопросам описания графов, решению элементарных задач на графах и их программной реализации и посвящена данная работа.
1. Математическое описание графа
Исходный граф из задания представлен на рис1.1.
Gор (V, X)
Рисунок 1.1 Исходный граф для расчетов
Описание графа Gор множествами вершин V и дуг X:
Нумерация вершин см. рис. 1.1.
V={0,1,2,3,4,5,6,7,8,9}
X={{0,1}, {0,2}, {0,3}, {1,6}, {2,1}, {2,5}, {2,8}, {2,5}, {3,9}, {3,8}, {4,6}, {5,4},
{5,6}, {5,7}, {5,8}, {5,3}, {6,9}, {7,8}, {7,6}, {8,9}}
1.2.2 Описание графа Gор списками смежности:
Г0={1,2,3}; Г1={0,2,6,}; Г2={0,1,3,5,8}; Г3={0,2,5,8,9};
Г4={5,6}; Г5={2,3,4,6,7,8}; Г6={1,4,5,7,9}; Г7={5,6,8};
Г8={2,3,5,7,9}; Г9={3,6,8};
Описание графа Gор матрицей инцидентности:
Данный граф может описан матрицей инцидентности вершина-ребро (нумерация вершин и ребер приведена для удобства, обычно она не пишется)
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
||
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
2 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
3 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
6 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Матрица весов соответствующего неориентированного графа:
Соответствующий неориентированный граф можно представить матрицей весов:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||
|
0 |
? |
2 |
3 |
5 |
? |
? |
? |
? |
? |
? |
|
|
1 |
? |
1 |
? |
? |
? |
4 |
? |
? |
? |
||
|
2 |
? |
1 |
? |
5 |
? |
? |
5 |
? |
|||
|
3 |
? |
? |
1 |
? |
? |
2 |
6 |
||||
|
4 |
? |
10 |
2 |
? |
? |
? |
|||||
|
5 |
? |
5 |
6 |
1 |
? |
||||||
|
6 |
? |
11 |
? |
2 |
|||||||
|
7 |
? |
1 |
? |
||||||||
|
8 |
? |
6 |
|||||||||
|
9 |
? |
Примечание. Показана верхняя половина матрицы, т.к. матрица весов неориентированного графа симметрична относительно главной диагонали.
Описание графа Gор матрицей смежности
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||
|
0 |
? |
1 |
1 |
1 |
? |
? |
? |
? |
? |
? |
|
|
1 |
-1 |
? |
-1 |
? |
? |
? |
1 |
? |
? |
? |
|
|
2 |
-1 |
1 |
? |
1 |
? |
1 |
? |
? |
? |
? |
|
|
3 |
-1 |
? |
-1 |
? |
? |
-1 |
? |
? |
1 |
1 |
|
|
4 |
? |
? |
? |
? |
? |
-1 |
1 |
? |
? |
? |
|
|
5 |
? |
? |
-1 |
1 |
1 |
? |
1 |
1 |
1 |
? |
|
|
6 |
? |
-1 |
? |
? |
-1 |
-1 |
? |
-1 |
? |
1 |
|
|
7 |
? |
? |
? |
? |
? |
-1 |
1 |
? |
1 |
? |
|
|
8 |
? |
? |
-1 |
-1 |
? |
-1 |
? |
-1 |
? |
1 |
|
|
9 |
? |
? |
? |
-1 |
? |
? |
-1 |
? |
-1 |
? |
Степени вершин неориентированного графа:
Степени вершин рассматриваемого неориентированного графа приведены в табл. 1.1
Таблица 1.1 Степенная последовательность вершин графа G
|
Вершины |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
Степени |
3 |
3 |
5 |
5 |
2 |
6 |
5 |
3 |
5 |
3 |
Выбираем из таблицы наибольшую и наименьшую степени:
Dmax = 6; Dmin = 2.
Примечание. Степенью вершины неориентированного графа называется количество ребер, инцидентных данной вершине.
Нумерация вершин графа G «поисков в глубину»:
Рассмотрим стек нумерации «поиском в глубину». Правило построения LIFO — Last In First Out. Использованы номера вершин исходного графа. Просмотренные вершины выделены жирным шрифтом, уже внесенные в стек вершины заключены в скобки.
|
Текущая вершина |
Стек дополнения |
Состояние стека |
|
|
0 |
1,2,3 |
01,2,3 |
|
|
3 |
8,9 |
0,1,2,38,9 |
|
|
9 |
пусто |
0,1,2,3,8,9 |
|
|
8 |
(9) |
0,1,2,3,8,9 |
|
|
2 |
(1), 5, (3), (8) |
0,1,2,3,8,95 |
|
|
5 |
(3), 4,6,7, (8) |
0,1,2,3,8,9,54,6,7 |
|
|
7 |
(6), (8) |
0,1,2,3,8,9,5,4,6,7 |
|
|
6 |
(9) |
0,1,2,3,8,9,5,4,6,7 |
|
|
4 |
(6) |
0,1,2,3,8,9,5,6,4,7 |
|
|
1 |
(6) |
0,1,2,3,8,9,5,4,6,7 |
Перенумерация
|
Старые номера |
0 |
3 |
9 |
8 |
2 |
5 |
7 |
6 |
4 |
1 |
|
|
Новые номера |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Реализация нумерации представлена на рис. 1.2. Исходная вершина — .
Рисунок 1.2 — Нумерация «поиском в глубину»
Нумерация вершин графа G «поиском в ширину»:
Рассмотрим стек нумерации «поиском в глубину». Правило построения FIFO — First In First Out. Использованы номер а вершин исходного графа. Просмотренные вершины выделены жирным шрифтом, уже внесенные в стек вершины заключены в скобки.
|
Текущая вершина |
Стек дополнения |
Состояние стека |
|
|
0 |
1,2,3 |
01,2,3 |
|
|
1 |
6, |
0,1,2,36 |
|
|
2 |
(1), (3), 5,8 |
0,1,2,3,65,8 |
|
|
3 |
(8), 9 |
0,1,2,3,6,5,89 |
|
|
6 |
(9) |
0,1,2,3,6,5,8,9 |
|
|
5 |
4, (6), 7, (8), (3) |
0,1,2,3,4,6,5,8,94,7 |
|
|
8 |
(9) |
0,1,2,3,6,5,8,9,4,7 |
|
|
9 |
Пусто |
0,1,2,3,6,5,8,9,4,7 |
|
|
4 |
(6) |
0,1,2,3,6,5,8,9,4,7 |
|
|
7 |
(6), (8) |
0,1,2,3,6,5,8,9,4,7 |
Перенумерация в данном случае не нужна, поскольку граф уже пронумерован «поиском в ширину», рис. 1.3. Исходная вершина — .
Рисунок 1.3 — Нумерация «поиском в ширину»
2. Эйлеров путь и Эйлеров цикл на графе
Для определения Эйлерова путь требуется выписать степенную последовательность вершин графа G и указать в графе G Эйлеров путь. Если такового пути не существует, то в графе G добавить наименьшее число ребер таким образом, чтобы в новом графе можно было указать Эйлерову цепь.
Степенная последовательность вершин графа G:
(3,3,5,5,2,6,5,3,5,3)
Для существования Эйлерова пути допустимо только две вершины с нечетными степенями, поэтому необходимо добавить три ребра, скажем между вершинами 1 и 3, 6 и 8, 7 и 9.
Полученный Эйлеров путь: 0,1,6,4,5,6,8,3,0,2,5,7,9,6,7,8,2,1,3,5,8,9,3,2.
Схема Эйлерова пути приведена на рис. 2.1 (добавленные ребра показано пунктиром):
Рисунок 2.1 — Эйлеров путь, полученный путем добавления ребра
Эйлеров цикл
Эйлеров цикл позволяет обойти граф, проходя по каждому ребру только один раз. Незадействованных ребер быть не должно. Если такого цикла не существует, то в графе G добавить наименьшее число ребер таким образом, чтобы в новом графе можно было указать Эйлеров цикл.
Аналогично пункту добавляем ребра {0,2}, {1,3}, {6,8}, {7,9} замыкая Эйлерову цепь (при этом выполняя условие существования Эйлерова цикла — четность степеней всех вершин).
Полученный Эйлеров цикл: 0,1,6,4,5,6,8,3,0,2,5,7,9,6,7,8,2,1,3,5,8,9,3,2,0.
Схема Эйлерова цикла (добавленные ребра показаны пунктиром):
Рисунок 2.2 — добавление двух ребер для получения Эйлерова цикла
3. Проверка ориентированного графа на наличие циклов путем отбрасывания «истоков» и «стоков»
У нас исток вершина V0, ее исходящие дуги X0={(0,1), (0,2), (0,3)}, рис. 3.1.
Рисунок 3.1 — Выделение первого истока
Рисунок 3.2 — Новые истоки после отбрасывания V0
Теперь истоком стала вершина V2, отбрасываем ее и дуги X2={(2,1), (2,3), (2,5), (2,8)}, рис. 3.3.
Рисунок 3.3 — Подграф, полученный отбрасыванием вершины V2
В оставшемся подграфе истоком является вершина V5, отбрасываем ее и дуги X5={(5,4), (5,6), (5,7), (5,8), (5,3)}.
Рисунок 3.4 — Подграф, полученный отбрасыванием вершины V5
В оставшемся подграфе истоком является вершина V3, отбрасываем ее и дуги X3 ={(3,9), (3,8)}, рис. 3.5.
Рисунок 3.5 — Подграф, полученный отбрасыванием вершины V3
В оставшемся подграфе истоком является вершина V7, отбрасываем ее и дуги X7 ={(7,6), (7,8)}, рис. 3.6.
Рисунок 3.6 — Подграф, полученный отбрасыванием вершины V7
В результате у нас остается подграф слабо связный, а следовательно, в результате исследования графа мы доказали, что граф Gор циклов не имеет.
4. Поиск основного (остевого) дерева алгоритмом Прима-Краскала
Выписываем таблицу весов ребер, упорядоченную по убыванию, табл. 4.1.
Таблица 4.1. Веса ребер графа G
|
Вес |
Ребра |
|
|
1 |
(2,1), (2,3), (5,3), (5,8), (7,8) |
|
|
2 |
(0,1), (3,8), (4,6), (6,9) |
|
|
3 |
(0,2) |
|
|
4 |
(1,6) |
|
|
5 |
(2,5), (2,8), (5,6), (0,3) |
|
|
6 |
(5,7), (3,9), (8,9) |
|
|
10 |
(5,4) |
|
|
11 |
(7,6) |
Последовательность шагов по решению задачи Прима-Краскла:
1) выбираем ребро (2,1), окрашиваем вершины V1 и V2 в красный цвет;
2) выбираем ребро (2,3), вершина V2 — красная, V3 пока бесцветная, следовательно, заливаем V3 красным цветом;
3) следующим выбираем ребро (3,5), вершина V3 красная, V5 — бесцветная, следовательно, заливаем V5 красным цветом;
4) выбираем ребро (5,8), вершина V5 красная, вершина V8 пока бесцветная, закрашиваем V8 в красный цвет;
5) выбираем ребро (7,8), вершина V8 красная, вершина V7 пока бесцветная, закрашиваем V7 в красный цвет;
6) выбираем ребро (0,1), вершина V1 красная, вершина V0 пока бесцветная, закрашиваем V0 в красный цвет;
7) пытаемся выбрать ребро (3,8), но обе его вершины уже красного цвета: это ребро в решение не войдет;
8) выбираем ребро (4,6), обе его вершины бесцветные, следовательно, заливаем V4 и V6 в синий цвет;
9) выбираем ребро (6,9), вершина V6 синяя, вершина V9 пока бесцветная, закрашиваем V9 в синий цвет;
10) пытаемся выбрать ребро (0,2), но обе его вершины уже красного цвета: это ребро в решение не войдет;
11) выбираем ребро (1,6), вершина V1 красная, вершина V6 синяя, следовательно, вершины V6, V4, V9 заливаем красным цветом.
12) мы выбрали 9 ребер на графе из 10 вершин, дерево построено.
Вес найденного дерева — 15. Построенное дерево приведено на рис. 4.2.
Рисунок 4.2 — Основное дерево, полученное по алгоритму Прима-Краскла
5. Определение дерева кратчайших путей по алгоритму Дейкстры
В работе требуется определить кратчайший маршрут от вершины 0 до вершины 9 по алгоритму Дейкстры. В данном параграфе рассматриваем граф как неориентированный (игнорируем направленность дуг, полагая их ребрами).
Достижимость минимальных весов:
q0,1 = 2;
q0,2 = 3;
q0,3 = 4;
q0,5 = 5;
q0,6 = 6;
q0,8 = 6;
q0,7 = 7;
q0,4 = 8;
q0,9 = 8;
Можно продолжать расчеты по алгоритму Дейкстры для вершин 4, 5 и 6, но они уже не повлияют на полученное решение.
Рис. 5.1. Кратчайшие пути, полученные по алгоритму Дейкстры
6. Задача коммивояжера
Решение задачи коммивояжера методом Литтла
Получим матрицу стоимости для нашего графа, элементами которой являются веса соответствующих дуг. Все элементы по диагонали матрицы приравниваем к бесконечности
|
? |
2 |
3 |
5 |
? |
? |
? |
? |
? |
|
|
2 |
? |
1 |
? |
? |
? |
4 |
? |
? |
|
|
3 |
1 |
? |
1 |
? |
5 |
? |
? |
5 |
|
|
5 |
? |
1 |
? |
? |
1 |
? |
? |
2 |
|
|
? |
? |
? |
? |
? |
10 |
2 |
? |
? |
|
|
? |
? |
5 |
1 |
10 |
? |
5 |
6 |
1 |
|
|
? |
4 |
? |
? |
2 |
5 |
? |
11 |
? |
|
|
? |
? |
? |
? |
? |
6 |
11 |
? |
1 |
|
|
? |
? |
5 |
2 |
? |
1 |
? |
1 |
? |
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
? |
? |
? |
|
|
1 |
1 |
? |
0 |
? |
? |
? |
3 |
? |
? |
|
|
2 |
2 |
0 |
? |
0 |
? |
4 |
? |
? |
4 |
|
|
3 |
4 |
? |
0 |
? |
? |
0 |
? |
? |
1 |
|
|
4 |
? |
? |
? |
? |
? |
8 |
0 |
? |
? |
|
|
5 |
? |
? |
4 |
0 |
9 |
? |
4 |
5 |
0 |
|
|
6 |
? |
2 |
? |
? |
0 |
3 |
? |
9 |
? |
|
|
7 |
? |
? |
? |
? |
? |
5 |
10 |
? |
0 |
|
|
8 |
? |
? |
4 |
1 |
? |
0 |
? |
0 |
? |
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
? |
? |
? |
|
|
1 |
0 |
? |
0 |
? |
? |
? |
3 |
? |
? |
|
|
2 |
1 |
0 |
? |
0 |
? |
4 |
? |
? |
4 |
|
|
3 |
3 |
? |
0 |
? |
? |
0 |
? |
? |
1 |
|
|
4 |
? |
? |
? |
? |
? |
8 |
0 |
? |
? |
|
|
5 |
? |
? |
4 |
0 |
9 |
? |
4 |
5 |
0 |
|
|
6 |
? |
2 |
? |
? |
0 |
3 |
? |
9 |
? |
|
|
7 |
? |
? |
? |
? |
? |
5 |
10 |
? |
0 |
|
|
8 |
? |
? |
4 |
1 |
? |
0 |
? |
0 |
? |
Текущая Нижняя граница=13 у. е.
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г0,1=1, Г1,0=1, Г1,2=0, Г2,1=0, Г2,3=0, Г3,2=0, Г3,5=0, Г4,6=8, Г5,3=0, Г5,9=0, Г6,4=9, Г7,8=5, Г8,7=5, Г8,5=0.
Максимальное значение имеет Г6,4=9
Удалим из матрицы стоимости строку 6 и столбец 4. Внесем в текущий ориентированный граф дугу (6,4). Присвоим элементу (4,6) значение бесконечности, чтобы избежать преждевременного замыкания контура.
|
0 |
1 |
2 |
3 |
5 |
6 |
7 |
8 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
? |
? |
|
|
1 |
0 |
? |
0 |
? |
? |
3 |
? |
? |
|
|
2 |
1 |
0 |
? |
0 |
4 |
? |
? |
4 |
|
|
3 |
3 |
? |
0 |
? |
0 |
? |
? |
1 |
|
|
4 |
? |
? |
? |
? |
8 |
? |
? |
? |
|
|
5 |
? |
? |
4 |
0 |
? |
4 |
5 |
0 |
|
|
7 |
? |
? |
? |
? |
5 |
10 |
? |
0 |
|
|
8 |
? |
? |
4 |
1 |
0 |
? |
0 |
? |
То же проделаем. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
|
0 |
1 |
2 |
3 |
5 |
6 |
7 |
8 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
? |
? |
|
|
1 |
0 |
? |
0 |
? |
? |
0 |
? |
? |
|
|
2 |
1 |
0 |
? |
0 |
4 |
? |
? |
4 |
|
|
3 |
3 |
? |
0 |
? |
0 |
? |
? |
1 |
|
|
4 |
? |
? |
? |
? |
0 |
? |
? |
? |
|
|
5 |
? |
? |
4 |
0 |
? |
1 |
5 |
0 |
|
|
7 |
? |
? |
? |
? |
5 |
7 |
? |
0 |
|
|
8 |
? |
? |
4 |
1 |
0 |
? |
0 |
? |
Текущая Нижняя граница=24 у. е.
Максимальное значение имеет Г4,5=?.
Удалим из матрицы стоимости строку 4 и столбец 5. Внесем в текущий ориентированный граф дугу (4,5). Присвоим элементу (5,6) значение бесконечности, чтобы избежать преждевременного замыкания контура.
Каждая трока и каждый столбец содержит ноль.
|
0 |
1 |
2 |
3 |
6 |
7 |
8 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
? |
|
|
1 |
0 |
? |
0 |
? |
0 |
? |
? |
|
|
2 |
1 |
0 |
? |
0 |
? |
? |
4 |
|
|
3 |
3 |
? |
0 |
? |
? |
? |
1 |
|
|
5 |
? |
? |
4 |
0 |
? |
5 |
0 |
|
|
7 |
? |
? |
? |
? |
7 |
? |
0 |
|
|
8 |
? |
? |
4 |
1 |
? |
0 |
? |
Максимальное значение имеет Г7,8=7
Удалим из матрицы стоимости строку 7 и столбец 8. Внесем в текущий ориентированный граф дугу (7,8). Присвоим элементу (8,7) значение бесконечности, чтобы избежать преждевременного замыкания контура.
|
0 |
1 |
2 |
3 |
6 |
7 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
|
|
1 |
0 |
? |
0 |
? |
0 |
? |
|
|
2 |
1 |
0 |
? |
0 |
? |
? |
|
|
3 |
3 |
? |
0 |
? |
? |
? |
|
|
5 |
? |
? |
4 |
0 |
? |
5 |
|
|
8 |
? |
? |
4 |
1 |
? |
? |
То же проделаем. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
|
0 |
1 |
2 |
3 |
6 |
7 |
||
|
0 |
? |
0 |
1 |
3 |
? |
? |
|
|
1 |
0 |
? |
0 |
? |
0 |
? |
|
|
2 |
1 |
0 |
? |
0 |
? |
? |
|
|
3 |
3 |
? |
0 |
? |
? |
? |
|
|
5 |
? |
? |
4 |
0 |
? |
0 |
|
|
8 |
? |
? |
3 |
0 |
? |
? |
Текущая Нижняя граница=30 у. е.
Максимальное значение имеет Г5,7=?
Удалим из матрицы стоимости строку 5 и столбец 7. Внесем в текущий ориентированный граф дугу (5,7).
|
0 |
1 |
2 |
3 |
6 |
||
|
0 |
? |
0 |
1 |
3 |
? |
|
|
1 |
0 |
? |
0 |
? |
0 |
|
|
2 |
1 |
0 |
? |
0 |
? |
|
|
3 |
3 |
? |
0 |
? |
? |
|
|
8 |
? |
? |
3 |
0 |
? |
Максимальное значение имеет Г1,6=?.
Удалим из матрицы стоимости строку 1 и столбец 6. Внесем в текущий ориентированный граф дугу (1,6).
|
0 |
1 |
2 |
3 |
||
|
0 |
? |
0 |
1 |
3 |
|
|
2 |
1 |
0 |
? |
0 |
|
|
3 |
3 |
? |
0 |
? |
|
|
8 |
? |
? |
3 |
0 |
Получим матрицу, содержащую нули в каждой строке и каждом столбце.
Текущая Нижняя граница=31 у. е.
|
0 |
1 |
2 |
3 |
||
|
0 |
? |
0 |
1 |
3 |
|
|
2 |
0 |
0 |
? |
0 |
|
|
3 |
2 |
? |
0 |
? |
|
|
8 |
? |
? |
3 |
0 |
Максимальное значение имеет Г8,3=3.
Удалим из матрицы стоимости строку 8 и столбец 3. Внесем в текущий ориентированный граф дугу (8,3).
|
0 |
1 |
2 |
||
|
0 |
? |
0 |
1 |
|
|
2 |
0 |
0 |
? |
|
|
3 |
2 |
? |
0 |
Максимальное значение имеет Г3,2=3.
Удалим из матрицы стоимости строку 3 и столбец 2. Внесем в текущий ориентированный граф дугу (3,2). Присвоим элементу (2,1) значение бесконечности, чтобы избежать преждевременного замыкания контура.
|
0 |
1 |
||
|
0 |
? |
0 |
|
|
2 |
0 |
? |
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы (2,0) и (0,1).
Рис. 6.1. Самый выгодный путь, полученный методом Литтла
7. Поиск всех деревьев на графе
Рис. 7.1 — Исходный граф для поиска всех деревьев
Определим количество деревьев с помощью матрицы Кирхгофа и алгоритма Трента. Матрица (по диагонали степени вершин, элементы — число путей со знаком «-»).
|
1 |
2 |
3 |
4 |
5 |
|||
|
1 |
3 |
-1
|
0 |
-1 |
-1 |
||
|
2 |
-1
|
4
|
-1 |
-1
|
-1 |
||
|
A = |
3 |
0 |
-1 |
3
|
-1 |
-1
|
|
|
4 |
-1 |
-1 |
-1 |
4
|
-1 |
||
|
5 |
-1 |
-1 |
-1
|
-1 |
4
|
По алгоритму выбираем один из главных миноров (вычеркиваем строку и столбец, соответствующие элементу главной диагонали). Например, 1 и 1 — в данном случае это полностью безразлично, граф полносвязный без кратных ребер.
|
4
|
-1 |
-1 |
-1 |
||
|
11 = |
-1 |
3
|
-1 |
-1
|
|
|
-1 |
-1 |
4
|
-1 |
||
|
-1 |
-1
|
-1 |
4
|
|
0
|
11 |
-5 |
-5 |
||||||||
|
-1 |
3
|
-1 |
-1
|
11 |
-5 |
-5 |
+(3) |
||||
|
0 |
-4 |
5
|
0 |
= |
(-1) |
(-1)1+2
|
-4 |
5 |
0 |
= |
|
|
0 |
-4
|
0 |
5
|
-4 |
0 |
5 |
|
7 |
-5 |
|
|
-4 |
5 |
= 5* = 5*(35 — 20) = 75.
Итого, мы ожидаем получить 75 деревьев.
Рис. 7.2. Примеры деревьев
Заключение
Граф есть упорядоченная пара (V, E), где V — непустое множество, называемое множеством вершин; E — неупорядоченное бинарное отношение на V, т.е. V&V. E называют множеством ребер. Говорят, что ребро, принадлежащее множеству E, инцидентно вершинам, которые оно соединяет. Таким образом, мы определим неориентированный граф. Он полностью определяется списком вершин и указанием, какие пары вершин имеют соединяющие их ребра (в случае нагруженного графа каждому ребру или дуге еще приписывается вес). Во многом базовые определения теории графов обязаны своему появлению Л. Эйлеру (1707-1782), решившему в 1736 г. широко известную «задачу о кенигсбергских мостах».
Ориентированный граф — упорядоченная пара (V, E), где V — множество вершин, а E — упорядоченное отношение на V (т.е. V&V). В этом случае E называют множеством дуг. Первая и вторая вершины дуги называются соответственно начальной и конечной.
В большинстве практических задач (как и в данном задании) рассматриваются графы с конечным числом ребер и вершин; их называют конечными. Для аналитического решения большинства задач желательно отойти от графического представления графов в пользу их матричного описания.
Литература
1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2011. — 1296 с.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. — М.: Энергоатомиздат, 2008. — 480 с.
3. Альфа и Омега [Электронный ресурс]. Режим доступа: http://alfa2omega.ru. Дата доступа: 13.12.2012.
4. Игошин В.И. Математическая логика и теория алгоритмов. — М.: Издательский центр «Академия», 2009. — 448 с.
5. Кнут Д. Искусство программирования, том 1. Основные алгоритмы — М.: Издательский дом «Вильямс», 2007. — 720 с.
Размещено на
