Задача 1. Для графа G перечислить все вершины, все ребра, указать степени каждой из вершин. Какие из них являются висячими, а какие изолированными?
| x 78 |
| v 6 |
| v 2 |
| v 5 |
| v 4 |
| v 3 |
| v 1 |
| x 5 |
| x 3 |
| x 4 |
| x 2 |
| x 1 |
Задача 2. Для графа G записать матрицу смежности А(G).
| x 88 |
| x 68 |
| v 6 |
| x 78 |
| v 2 |
| v 5 |
| v 4 |
| v 3 |
| v 1 |
| x 5 |
| x 3 |
| x 4 |
| x 2 |
| x 1 |
Задача 3. Дана матрица смежности А(G) графа G. Восстановить по ней граф.
Задача 4. Для орграфа Д записать матрицу смежности A(G) и матрицу инцидентности В(Д)
| x 8 |
| v 2 |
| x 6 |
| x 7 |
| v 5 |
| v 4 |
| v 3 |
| v 1 |
| x 5 |
| x 3 |
| x 4 |
| x 2 |
| x 1 |
Задача 4. По матрице инцидентности В(Д) восстановить орграф.
Задача 5. Дана матрица смежности орграфа Д. Восстановить по ней орграф и найти число путей длины 4 из 1 вершины в 3. Указать эти пути.
Задача 6. Дана матрица смежности графа G. Восстановить по ней граф и найти число путей длины 3 из 2 вершины в 4. Указать эти пути.
Задача о кратчайшем пути
Исторически сложились три задачи о поиске пути в графе.
Задача 1. Найти любой путь (цепь) из А в В.
Задача 2. Найти кратчайший путь из А в В в смысле количества ребер (дуг).
Алгоритм решения задачи о нахождении кратчайшего пути из А в В в смысле наименьшего количества ребер:
1. Вершине А припишем индекс 0.
2. Всем вершинам, смежным с А, припишем индекс 1.
3. Всем вершинам, смежным с вершинами индекса 1 и не имеющим индекса, припишем индекс 2 и т.д.
4. Как только вершина В получит некоторый индекс, процесс присвоения останавливается. Значение индекса n вершины В и есть длина кратчайшего пути из А в В. Построим этот путь.
5. Среди вершин, смежных с В, обязательно найдется вершина с индексом n-1 (одна или несколько), возвращаемся в эту вершину и продолжаем этот процесс.
6. Через n шагов придем в вершину с индексом 0, т.е. в А. Один или несколько путей построены.
Если каждому ребру (дуге) графа приписано некоторое число lk³0 (вес ребра), то граф называется взвешенным (нагруженным)
Задача 3. Найти кратчайший путь из А в В во взвешенном графе (в смысле суммы весов ребер (дуг)).
Приведем алгоритм решения задачи 3.
Будем постепенно приписывать всем вершинам графа числовые индексы:
1. Вершине А припишем индекс 0, всем остальным вершинам значение +¥.
2. Будем постепенно перебирать все пары смежных вершин vx и vy. Каждый раз проверим первенство 
, если оно
3.
| vy |
, заменив его на 
.
| vx |
|
|
|
|
4. Процесс останавливаем, когда ни один индекс уже нельзя уменьшить. В этот момент вершина В имеет некий индекс m. Это и есть наименьшая сумма весов всех дуг.
5. Построим путь с такой суммой. Будем возвращаться из вершины В в А. Среди вершин, смежных с В, обязательно найдется вершина С, для которой выполняется точно равенство mВ=mС+lСВ.
Возвращаемся к С и повторяем процесс. Поскольку индексы все время уменьшаются, то через несколько шагов придем в вершину с индексом 0, т.е. вершину А.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1. Задан граф.
| v 7 |
| v 5 |
| v 6 |
| v 4 |
| v 3 |
| v 2 |
| v 1 |
| v 8 |
Найти кратчайший путь из вершины v1 в вершину v8.
Решение. Используя алгоритм задачи о нахождении кратчайшего пути из v1 в v8 в смысле наименьшего количества ребер, получим:
1. Вершине v1 припишем индекс 0.
2. Всем вершинам, смежным с v1 (v2 и v3), припишем индекс 1.
3. Всем вершинам, смежным v2 и v3 и не имеющим индекса (v5,v4,v6,v7), припишем индекс 2.
4. Всем вершинам, смежным с вершинами (v4,v5,v6,v7) и не имеющим индекса v8, припишем индекс 3.
Таким образом, вершина v8 получила индекс 3, а значит, длина кратчайшего пути из v1 в v8 равна 3. Построим этот путь или пути, если их несколько.
5. Среди вершин, смежных с v8, найдем вершины с индексом 3-1=2. Таких вершин три: v6,v7, v4.
6. Среди вершин, смежных с v4,v6,v7, найдем вершины с индексом 1. Таких вершин две: v2 и v3.
7. Среди вершин, смежных с v2 и v3, найдем вершины с индексом 0. Такая вершина одна и это v1.
Таким образом, было получено три кратчайших пути длины 3. Перечислим их: 1) v1,v2,v6,v8; 2) v1,v3,v7,v8; 3) v1,v3,v4,v8.
| v 7 (2) |
| v 5 (2) |
| v 6 (2) |
| v 4 (2) |
| v 3 (1) |
| v 2 (1) |
| v 1 (0) |
| v 8 (3) |
Задача 2. Задан орграф.
| v 5 |
| v 6 |
| v 7 |
| v 3 |
| v 4 |
| v 1 |
| v 2 |
Найти кратчайший путь из вершины v1 в вершину v6 в смысле суммы весов дуг.
Решение. Используя алгоритм решения задачи о нахождении кратчайшего пути в смысле суммы весов дуг, получим:
1. Вершине v1 присвоим индекс 0, а всем остальным +¥.
2. Переберем вершины орграфа, смежные с вершиной v1 и имеющие дугу из v1 в эту же вершину. Вершине v4 присвоим индекс 0+2=2, так как 2<+¥. Вершине v3 присвоим индекс min {0+1, 2+2}=1, так как 1<+¥. Вершине v2 присвоим индекс min{0+1, 2+5}=2, так как 1<+¥.
3. Аналогично проведем рассуждения для вершин орграфа, смежных с вершинами v2,v3,v4. Так как в вершину v5 ведет две дуги, то присвоим ей индекс min{1+4, 2+3}=5<+¥. Вершине v7 присвоим индекс min{2+5, 1+3}=4<+¥.
4. Вершине v6 присвоим индекс min{5+2, 2+6, 4+1}=4+1=5. Таким образом, кратчайший путь из вершины v1 в v6 в смысле суммы весов дуг равен 5.
Построим этот путь.
5. Среди вершин, смежных с вершиной v6, найдем вершину С, для которой выполняется равенство 
. Такой вершиной является v7, так как 
или 4+1=5.
6. Среди вершин, смежных с вершиной v7, найдем вершину Д, для которой выполняется равенство 
. Такой вершиной является v3, так как 
или 1+3.
7. Среди вершин, смежных с вершиной v3, найдем такую вершину Е, для которой выполняется равенство 
. Такая вершина одна и это v1.
Таким образом, мы вернулись из вершины v6 в вершину v1.
Запишем кратчайший путь из v1 в v6: v1 v3 v7 v6.
| v 5 (5) |
| v 2 (1) |
| v 6 |
| v 7(4) |
| v 3 (1) |
| v 4(2) |
| v 1 (0) |
