Задание
Неориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7} задан списком ребер Е = {(1, 2), (1, 4), (1, 6), (1, 7), (2, 3), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6), (5, 7)}.
Построить реализацию графа G. Найти цикломатическое число графа G. Выбрать остов
графа G. Построить базис циклов графа G.
Решение
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Построить реализацию графа G | Процесс построения реализации графа описан в тренинге умений 3 и 4
| |
| Найти цикломатическое число графа G | Цикломатическое число, равное размерности пространства циклов графа, определяется формулой ν = p – b + k, где p – число ребер, b – число вершин, k – число компонент связности графа; p = 13, b = 7, k = 1(нетрудно убедиться, что граф связный). Следовательно, ν = 13 – 7 + 1 = 7 | |
| Выбрать остов графа G | Поскольку число вершин графа равно 7, в любом его остове – 6 ребер. При заданном упорядочении вершин 1-7, начиная с вершины 1, последовательно добавляем ребра, присоединяющие к строящемуся дереву новую вершину: (1, 2), (1, 4), (1, 6), (1, 7), (2, 3), (2, 5). | |
| Построить базис циклов графа G: а) составить список хорд относительно выбранного остова (все остальные ребра графа); б) поочередно присоединяя к остову по одной хорде, выделять элементарный цикл, состоящий из этой хорды и части ребер остова – единственной цепи, связывающей в остове концы хорды | (2, 6), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6), (6, 7). Число хорд должно быть равно цикломатическому числу графа, т.е. 7. ХордаДобавляемая цепь * (2, 6) (6, 1), (1, 2) (3, 4) (4, 1), (1, 2), (2, 3) (3, 6) (6, 1), (2, 1), (2, 3) * (4, 5) (5, 2), (2, 1), (1, 4) (4, 6) (6, 1), (1, 4) * (5, 6) (6, 1), (1, 2), (2, 5) (6, 7) (7, 1), (1, 6) | |
| Выразить в построенном базисе заданный элементарный цикл С | Пусть задан цикл С = [6, 2, 1, 4, 5, 6]. Он получается сложением по модулю 2 тех базисных циклов, которые содержат хорды, принадлежащие С (они отмечены звездочкой в предыдущей таблице: (6, 2), (4, 5), (5, 6). Проверьте, что ребра цикла С содержатся в совокупности базисных циклов нечетное число раз (в частности, все хорды – ровно по одному разу), а ребра, не принадлежащие С (например, ребро (5, 2)), - четное |
Решите самостоятельно следующие задачи:
Постройте самостоятельно остов и базис циклов неориентированных графов, заданных списком ребер, определите цикломатическое число графа:
1. {(1, 2), (1, 3), (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (3, 6), (4, 7), (5, 6), (6, 7)};
2. {(1, 2), (1, 4), (1, 5), (1, 7), (2, 3), (2, 4), (3, 4), (3, 5), (3, 7), (4, 5), (5, 7)};
3. {(1, 2), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6)};
4. {(1, 2), (1, 4), (1, 5), (1, 7), (2, 5), (2, 6), (3, 4), (3, 5), (3, 7), (4, 5), (5, 6), (5, 7)};
5. {(1, 2), (1, 4), (1, 6), (1, 7), (2, 5), (2, 6), (2, 7), (3, 4), (3, 5), (3, 7), (4, 5), (5, 6), (6, 7)}.
Пример выполнения упражнения тренинга на умение № 6
Задание
В неориентированном графе G с заданными длинами ребер найти расстояние между вершинами А и В и кратчайшую цепь [ АВ ].
Решение
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Установить метки M (v) (они представляют собой расстояния от вершины А) в вершинах, соседних с вершиной А | Для вершин a, g, b метки M (a) = 4, M (g) = 5, M (b) = 4 равны длинам ребер, связывающих их с вершиной А
|
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Установить метки M (v) в вершинах, соседних с предыдущими | Для вершин c, d, f, e метки M (c) = 4+3 = 7,
M (d) = 5 + 5 = 10, M (f) = 4 + 11 = 15, M (e) = 4 + 3 = 7
| |
| Пересчитывать метки M (v) при обнаружении более коротких цепей | Для вершины d меткa M (d) = 7 + 2 = 9, M (B) = 9 + 6 = 15, M (f) = 9 + 4 = 13, M (e) = 4 + 3 = 7, M (B) = 13 + 1 = 14.
Пересчет закончен. Вершина В получила метку 14; это определяет расстояние d(A, B)
| |
| Выделить кратчайшую цепь [ А, В ] | 
Кратчайшая цепь [ А, В ] строится обратным ходом из вершины В. Она проходит через те вершины, по которым установлено последнее для каждой вершины значение метки. Тем самым, цепь проходит последовательно через вершины В, f, d, c, a, A.
Кратчайшая цепь - [ АacdfВ ]
|
Решите самостоятельно следующие задачи:
Найти расстояние между вершинами А и В и кратчайшую цепь [ АВ ]
в неориентированном графе G с заданными длинами ребер:
1)
2)
3)
4)
