Задачи для самостоятельного решения. Задача 1. Для графа g перечислить все вершины, все ребра, указать степени каждой из вершин

Задача 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, т.е. в А. Один или несколько путей построены.

Если каждому ребру (дуге) графа приписано некоторое число l_k³0 (вес ребра), то граф называется взвешенным (нагруженным)

Задача 3. Найти кратчайший путь из А в В во взвешенном графе (в смысле суммы весов ребер (дуг)).

Приведем алгоритм решения задачи 3.

Будем постепенно приписывать всем вершинам графа числовые индексы:

1. Вершине А припишем индекс 0, всем остальным вершинам значение +¥.

2. Будем постепенно перебирать все пары смежных вершин v_x и v_y. Каждый раз проверим первенство , если оно

3.

vy

выполняется, то уменьшаем индекс , заменив его на .

vx

4. Процесс останавливаем, когда ни один индекс уже нельзя уменьшить. В этот момент вершина В имеет некий индекс m. Это и есть наименьшая сумма весов всех дуг.

5. Построим путь с такой суммой. Будем возвращаться из вершины В в А. Среди вершин, смежных с В, обязательно найдется вершина С, для которой выполняется точно равенство m_В=m_С+l_СВ.

Возвращаемся к С и повторяем процесс. Поскольку индексы все время уменьшаются, то через несколько шагов придем в вершину с индексом 0, т.е. вершину А.