Основы теории графов.

Впервые понятие графа возникло в середине XIXвека в применении к химическим молекулам и электрическим цепям. ( Кирхгоф, Кэли )

•

• ориентированный граф

( орграф)

• • • •

•

неориентированный граф

у

х

Х

Элементы х  Х называют вершинами орграфа, а пары ( x,y), где у  f (x), называют дугами орграфа.

Вершина х – начало дуги, у – конец дуги.

Вершины х и у, соединенные дугой, называют смежными.

Определение: Если в орграфе отождествить пары ( х,у) и ( у,х) ( «стереть стрелки »), то возникает неориентированный граф ( граф).

П ри этом дуга переименовывается в ребро • •

§ 1. Составляющие графов и орграфов.

Определение : Путь в орграфе – это последовательность дуг такая, что конец каждой дуги есть начало следующей дуги.

а b

Путь из а в b.

Замкнутый путь называется контуром.

Для графа путь переименовывают в цепь, а контур в цикл.

Путь называется простым, если ни одна вершина в нем не повторяется ( для контура допускается а = b )

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

Если в пути все дуги встречаются ровно один раз, то путь называется эйлеровый.

Для графов – эйлерова цепь, эйлеров цикл.

Определение: Если в графе любые две вершины можно соединить цепью, то он называется связным.



связный несвязный

Несвязный граф распадается на непересекающиеся максимальные связные подграфы ( связные компоненты).

§ 2. Задачи о кратчайшем пути в графе.

Исторически сложились 3 задачи про поиск путей в графике.

Задача 1. Найти любой путь из а в b.

_{• •}

А _{• •} В

Одно из основных применений в теории игр. Позиции игры обозначают вершинами графа, а ходы дугами или ребрами.

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

• •

А _{• •} В

_•

Разработан эффективный алгоритм:

Алгоритм решения задачи 2.

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

1.Вершине А припишем индекс 0.

2. Всем вершинам, смежным с А припишем индекс 1.

3. Всем вершинам смежным с вершинами индекса 1 и не помеченным индексами, припишем индекс 2 и т.д.

4. Как только вершина В получит некоторый индекс, процесс останавливаем ( даже если остались не помеченные вершины).

Число n - это и есть длина кратчайшего пути.

Построим этот путь.

5. Среди вершин смежных с В, обязательно найдется вершина С с индексом n-1

(одна или несколько), возвращаемся в вершину С и продолжаем процесс.

6. Через n шагов придем в вершину с индексом 0, т.е. в А.

Один или несколько путей построены.

Задача 3. Если к каждой дуге ( ребру) графа поставить в соответствие некоторое

число λ_k ≥ 0 ( вес дуги), то граф называется взвешенным ( или нагруженным).

4

3 • • 5

А _{• •} В

7 6

_•

Итак, требуется найти кратчайший путь из А в В в смысле суммы весов

( т.е. ∑ λ _к – минимальна )

Разработан эффективный алгоритм

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

Будем постепенно приписывать всем вершинам графа индексы μ _к ≥ 0:

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

Замечание. В реальных задачах в роли + ∞ выступает любое выбранное пользователем число, намного превосходящее сумму всех весов λ _к графа_.

2. Перебираем последовательно все пары смежных вершин x и y

μ _x λ _xy μ _y

• •

x y

μ _y > μ _{x +} λ _xy

Каждый раз проверяем неравенство

Если оно выполнено, то уменьшим индекс μ _{y ,} заменив его на μ _x + λ _{xy .}

3. Процесс останавливаем, когда ни один индекс уже нельзя уменьшить. В этот момент вершина В имеет некоторый индекс μ _В - это и есть наименьшая сумма весов.

Построим путь с такой суммой.

4. Среди вершин смежных с В обязательно найдется вершина С , для которой выполняется точное равенство μ_В= μ_С+ λ_СВ

Возвращаемся в С и повторяем процесс.

Т.к. индексы все время уменьшаются, рано или поздно придем в вершину индекса в 0, т.е. вершину А.

Один или несколько путей построены.