Теоретические сведения. Граф - это двойка <V, E>, где V - непустое множество вершин

Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между «началом» и «концом» ребра.

Таблица 3.1. Примеры неориентированных графов

Граф	Вершины	Ребра
Семья	Люди	Родственные связи
Город	Перекрестки	Улицы
Домино	Костяшки	Возможность

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

Например, три графа на рисунке 3.1 совпадают, а два графа на рисунке 3.2 - различны.

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

Рисунок 3.1. Три способа изображения одного графа

Ребро е и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра е.

Рисунок 3.2. Пример двух разных графов

Рисунок 3.3. Псевдограф

Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет инцидентных ей ребер (ее степень равна 0).

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображенном на рисунке 3.1, есть два различных пути из вершины a в вершину с: adbc и abc.

Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v.

Граф называется связным, если все его вершины взаимно достижимы.

Компонента связности - это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Заметим, что любая изолированная вершина является отдельной компонентой связности. На рисунке 3.4 изображен граф, состоящий из четырех компонент связности: [abhk], [gd], [c] и [f].

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (рисунок 3.1) - 3 и 2 соответственно.

Рисунок 3.4. Несвязный граф

Говорят, что вершина v принадлежит k-му уровню относительно вершины u, если существует путь из u в v длиной ровно k ребер. Одна и та же вершина может относиться к разным уровням. Например, в графе, изображенном на рисунке 3.1, относительно вершины a существует 4 уровня:

0) a;

1) b, d;

2) b, d, c (пути adb, abd, abc);

3) c (путь adbc).

Расстояние между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рисунке 3.1 равно 2.

Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рисунке 3.1.

Эйлеров граф - это граф, в котором существует цикл, содержащий все ребра графа (вершины могут повторяться). Именно такие графы положительно решают упомянутую в начале лекции задачу о кенигсбергских мостах. Например, граф на рисунке 3.5 является Эйлеровым: искомым циклом в нем будет dbacfbcd.

Рисунок 3.5. Граф Эйлера

Гамильтонов граф - это граф, в котором существует цикл (без повторений), содержащий все вершины графа (рисунок 3.5; искомый цикл: abdfca).

Ориентированный граф (орграф) - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками (рисунок 3.6).

Рисунок 3.6. Орграф

В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Можно сказать, что любое ребро - это пара дуг, направленных навстречу друг другу.

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

Все основные понятия, определенные для неориентированных графов (инцидентность, смежность, достижимость, длина пути и т.п.), остаются в силе и для орграфов - нужно лишь заменить слово «ребро» словом «дуга». А немногие исключения связаны с различиями между ребрами и дугами.

Степень вершины в орграфе - это не одно число, а пара чисел: первое характеризует количество исходящих из вершины дуг, а второе - количество входящих дуг.

Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рисунке 3.6 нет пути, ведущего из вершины 2 в вершину 5. «Двигаться» по орграфу можно только в направлениях, заданных стрелками.

Таблица 3.2. Примеры ориентированных графов

Граф	Вершины	Дуги
Чайнворд	Слова	Совпадение последней и первой букв (возможность связать два слова в цепочку)
Стройка	Работы	Необходимое предшествование (например, стены нужно построить раньше, чем крышу, т. п.)

Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рисунке 3.7, равно 6.

Рисунок 3.7. Взвешенный граф

N-перифериявершины v - это множество вершин, расстояние до каждой из которых (от вершины v) не меньше, чем N.

Таблица 3.3. Примеры взвешенных графов

Граф	Вершины	Вес вершины	Ребра (дуги)	Вес ребра (дуги)
Таможни	Государства	Площадь территории	Наличие наземной границы	Стоимость получения визы
Супер-чайнворд	Слова	-	Совпадение конца и начала слов(возможность "сцепить" слова)	Длина пересекающихся частей

Существует довольно большое число разнообразных способов представления графов. Однако мы изложим здесь только самые полезные с точки зрения программирования.

Матрица смежности S_m - это квадратная матрица размером N×N (N - количество вершин в графе), заполненная единицами и нулями по следующему правилу: Если в графе имеется ребро e, соединяющее вершины u и v, то S_m[u,v] = 1, в противном случае S_m[u,v] = 0.

Заметим, что данное определение подходит как ориентированным, так и неориентированным графам: матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа - несимметричной.

Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:

Если в графе имеется ребро e, соединяющее вершины u и v, то S_m[u,v] = ves(e), в противном случае S_m[u,v] = 0.

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

В качестве примера приведем матрицы смежности для трех графов, изображенных на рисунке 3.5, рисунке 3.6 и рисунке 3.7.

Таблица 3.4. Примеры матриц смежности

Граф Эйлера (рисунок 3.5)

Орграф (рисунок 3.6)

Взвешенный граф (рисунок 3.7)

a

b

c

d

f

a

b

c

d

a

a

b

b

c

c

d

d

f

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много «пустых мест» (нулей). Кроме того, для «общения» с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.

Список ребер - этот способ задания графов наиболее удобен для внешнего представления входных данных. Пусть каждая строка входного файла содержит информацию об одном ребре (дуге):

<номер_начальной_вершины> <номер_конечной_вершины> [<вес_ребра>]

В качестве примера приведем списки ребер (дуг), задающие те же три графа с рисунка 3.5, рисунка 3.6 и рисунка 3.7.

Таблица 3.5. Примеры списков ребер (дуг)

a b a c b cb dc dc ff db f

1 21 43 13 23 54 3

a b 1a c 10b c 2b d 10c d 3

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

Списки смежности - этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для орграфа - список вершин, являющихся концами исходящих дуг). Конкретный формат входного файла, содержащего списки смежности, необходимо обговорить отдельно. Например, в нашем случае начальная вершина отделена от списка смежности двоеточием:

<номер_начальной_вершины>: <номера_смежных_вершин>

Наиболее естественно применять этот способ для задания орграфов, однако и для остальных вариантов он тоже подходит.

В качестве примера приведем списки смежности, задающие все те же три графа, изображенные на рисунке 3.5, рисунке 3.6 и рисунке 3.7.

Таблица 3.6. Примеры списков смежности

a: b cb: c d fc: d fd: f

1: 2 4 3: 1 2 54: 3

b: a 1 c 2 d 10c: a 10 d 3

Собственно, этот способ представления графов является всего лишь внутренней реализацией списка смежности: в одном линейном списке содержатся номера «начальных вершин», а в остальных - номера смежных вершин или указатели на эти вершины.

Дерево - это частный случай графа, наиболее широко применяемый в программировании.

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

1. Дерево - это связный граф без циклов.

2. Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

3. Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево - как орграф, в котором между любыми двумя вершинами существует не более одного пути.

Таблица 3.7. Примеры деревьев

Дерево	Вершины	Ребра (дуги)
Армия	Солдаты и офицеры	Иерархия (командир - подчиненный)
Династия (родословная по мужской4 линии)	Монархи	Отношение "отец - сын"

Рисунок 3.8. Корневое дерево высоты 3

Мы будем изучать и использовать только один частный случай ориентированных деревьев - корневые деревья (рисунок 3.8).

Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причем должны выполняться два обязательных условия:

1. из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;

2. в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья «растут» вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья - самыми нижними.

Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.

Бинарное дерево - это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.

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

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

Задания для самостоятельного выполнения:

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

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