Задание:

1. Рассмотреть графы и деревья

2. Изучить неориентированные и ориентированные графы, стратегии обхода графов

3. Привести примеры графов и деревьев

4. Оформить отчет

Теоретические сведения

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

Примеры неориентированных графов

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

Например, три графа на рисунке 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. «Двигаться» по орграфу можно только в направлениях, заданных стрелками.

Примеры ориентированных графов

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

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

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

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

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

Примеры взвешенных графов

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

Матрица смежности 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.

Примеры матриц смежности