Задачи по теории графов. Основные понятия и решения задач

Глава 8.Задачи по теории графов

8.1.Основные понятия

1.Граф – это фигура, состоящая из точек (вершин) и соединяющих их линий (ребер) (рис. 1).

2.Орграф – это граф, у которого ориентированы ребра (дуги), т.е. указаны начало и конец каждого из них (рис. 2).

3.Длина ребра или дуги – это некое число, поставленное в соответствие каждому ребру или дуге.

Рис. 1                                  Рис. 2

4.Путь (маршрут) в графе или орграфе – это последовательность ребер, ведущая от некоторой начальной вершины в конечную вершину, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.

Например, путями от точки А до точки D (рис. 1) могут быть AD, или AED, или ABED и т.д.

5.Длина пути – это число ребер или дуг в нем.

6.Цикл – это путь, который начинается и кончается в одной и той же вершине.

7.Граф или орграф называется связанным, если две любые его вершины можно соединить, по крайней мере, одним путем.

8.Дерево – это путь без циклов.

Задача 1.Найти кратчайший путь между всеми вершинами графа (см. рис. 1).

                               таблица. Т_1,2                                     таблица. Т_3,4

Решение. 1).Заполним табл. Т_1,2 следующим образом.

Обозначим через d (x, y) длину пути от x до y, очевидно, что

d (x, y) = d (y, x). Диагональю будут являться точки А, В, С, D, E.

Для них d (A, A) = d (B, B) = d (C, C) = d (D, D) = d (E, E) = ∞.

Над диагональю запишем длины кратчайших путей, но не более чем из одного ребра (в противном случае поставим ∞). Таким образом,

d (A, В) = 5, d (А, С) = ∞, d (А, D) = 9, d (A, E) = 1, d (B, C) = 2,

d (B, D) = ∞, d (B, E) = 3, d (C, D) = 4, d (C, E) = ∞, d (D, E) = 3.

Под диагональю запишем длины кратчайших путей, состоящих не более чем из двух ребер (иначе поставим ∞):

d₁ (A, В) = 5, d₂ (A, B) = d (A, E) + d (E, B) = 1 + 3 = 4_E ,

d (A, В) = min {d₁ (A, В); d₂ (A, В)} = min {5; 4_E } = 4_E.

d₁ (A, C) = d (A, B) + d (B, C) = 5 + 2 = 7_B,

d₂ (A, C) = d (A, D) + d (D, C) = 9 + 4 = 13_D,

d (A, C) = min {d₁ (A, C); d₂ (A, C)} = min {7_B; 13_D } = 7_B.

Аналогично находим:

d (A, D) = 4_E, d (А, E) = 1, d (B, C) = 2, d (B, D) = 6_C или d (B, D) = 6_Е,

d (B, Е) = 3, d (С, D) = 4, d (С, E) = 5_В, d (D, E) = 3.

2).Заполним табл. Т_3,4 следующим образом.

Над диагональю запишем длины кратчайших путей, но не более чем из трех ребер, а под диагональю - длины кратчайших путей, но не более чем из четырех ребер. Таким образом, под диагональю записаны кратчайшие пути между всеми вершинами графа.

Задача 2.Найти кратчайшие пути между всеми вершинами графа

(рис. 1) через транзитные вершины.

Решение. 1).Построим таблицу (Т_*,А) следующим образом:

запишем в диагональные клетки обозначения вершин A, B, C, D, E.

Для них d (A, A) = d (B, B) = d (C, C) = d (D, D) = d (E, E) = ∞.

Над диагональю запишем длины кратчайших путей, но не более чем из одного ребра (в противном случае поставим ∞).

Под диагональю запишем длину кратчайшего пути, но не более чем из двух ребер (через транзитную вершину А). Например, длина пути DЕ равна 3, а через вершину А – 10_A.

Запишем в клетке (D, E), min {3, 10_A} = 3. Длина пути ВВ через вершину А равна 10_A, т.е. d (B, B) = d (В, А) + d (А, В) = 5 + 5 = 10_A.

Длина пути DВ через вершину А равна 14_А, т.е.

d (D, B) = d (B, D) = d (D, A) + d (А, В) = 14_А.

2).Построим таблицу (Т_{в, с}  )

Над диагональю запишем длину кратчайшего пути, но не более чем из трех ребер (через А, или В, или АВ). Например,

d (С, Е)= min {d₁ (С, Е);d₂ (С, Е)} = min {8_AB; 5_B} = 5_B; где d₁ (С, Е) = d₁ (С, В) + d₁ (В, А) + d (A, E) = 2 + 5 + 1 = 8_AB;

d₂ (С, Е) = d (С, В) + d (В, E) = 2 + 3 = 5_B;

d (Е, B) = min {d₁ (Е, B); d₂ (Е, B)} = min {3; 6_А } = 3;

таблица (Т_*,А)                                     таблица (Т_{в, с}  )

                                      таблица (Т_D.,E )

где d₁ (Е, B) = 3, d₂ (Е, B) = d₂ (Е, А) + d₂ (А, В) = 6_А,

d (D, B) = d (B, D) = d (D, A) + d (А, В) = 9 + 5 = 14_А.

Под диагональю запишем длину кратчайшего пути,   но не более чем из четырех  ребер (через А, или В, или С, или АВ, или ВС, или АВС).

Например, d₁ (Е, D) = d₁ (D, Е) = 3, d₂ (Е, D) = d₂ (D, Е) =d₂ (E, А) + d₂ (A, B) +

+ d₂ (B, C) +d₂ (C, D) =1+5 +2 + 4 = 12_ABC;

d₃ (Е, D) = d₃ (D, Е) = d₃ (E, А) + d₃ (A, D) = 1 + 9 =10_A;

d₄ (Е, D) = d₄ (D, Е) = d₄ (E, B) +d₄ (B, C) + d₄ (C, D) = 3 + 2 + 4 = 9_BC;

d₅ (Е, D) = d₅ (D, Е) = d₅ (D, A) + d₅ (A, B) + d₅ (B, E) = 9 + 5 + 3 = 17_AB;

d (Е, D) = d (D, E) = min {3; 12_ABC; 10_A; 9_BC; 17_AB } = 3.

3). Построим таблицу (Т_D.,E )

Над диагональю запишем длину кратчайшего пути, но не более чем из пяти ребер (через А, или В, или С, или D, или АВ, или ВD, или …, или АВСD).

Над диагональю запишем длину кратчайшего пути, но не более чем из пяти ребер (через А, или В, или С, или D, или АВ, или ВD, или …, или АВСD).

Под диагональю запишем длину кратчайшего пути между всеми вершинами данного графа через транзитные вершины.

Задача 3

Найти кратчайшие пути между всеми вершинами графа (см. рис. 2).

таблица (Т_1,2 )                                    таблица (Т₃)

Решение. 1).Построим табл. (Т_1,2 ).

Запишем в клетки диагонали метки вершин A, B, C, D. Для них

d (A,A) = d (B, B) = d (C, C) = d (D, D) = d (E, E)= ∞.