Основные понятия и виды графов

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

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

В своей жизни мы, так или иначе, соприкасались с объектами, имеющими структуру графа. К таким объектам относятся разного рода маршруты общественного транспорта: система метрополитена, автобусные маршруту и т.п. В частности, программисту знакома компьютерная сеть, также являющаяся графом (рис. 3.1). Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точками являются отдельные серверы, а линиями – различные виды электрических сигналов. В метрополитене первое – станции, второе – туннели, проложенные между ними. В теории графов точки именуется вершинами, или узлами, а линии – ребрами, или дугами. Таким образом, граф – это совокупность вершин, соединённых ребрами.

Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На рисунке ниже в качестве примера показана полносвязная топология.

Рисунок 3.1 – Компьютерная сеть

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

Вот некоторые важные обозначения, используемые в теории графов:

· G =(V, E), здесь G – граф, V – его вершины, а E – ребра;

· | V | – порядок (число вершин);

· | E | – размер графа (число рёбер).

В нашем случае (рис. 1) | V |=5, | E |=10;

Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 3.1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 3.2). Ребра орграфа принято называть дугами.

В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Степень входа вершины – количество входящих в эту вершину ребер, степень выхода – количество исходящих ребер. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.

Рисунок 3.2 – Ориентированный граф

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

Ориентированные графы имеют следующую форму записи:

G =(V, A), где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3.3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G =(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

Рисунок 3.3 – Смешанный граф

На рисунке 3 изображен смешанный граф. Одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].

Когда у ребра оба конца совпадают, т. е. ребро выходит из некоторой вершины F и входит в нее, то такое ребро называется петлей (рис. 3.4).

Рисунок 3.4 – Петли графа

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

Рисунок 3.5 – Изоморфные графы

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

В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с соседней вершиной посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’ =(V’, E’) является подграфом графа G =(V, E), только тогда когда V’ и E’ принадлежат V, E.

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

· матрица смежности;

· матрица инцидентности;

· список смежности;

· список ребер.

Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Причем размеры этих массивов, зависят от количества вершин и/или ребер в конкретном графе. Так размер матрицы смежности n × n, где n – число вершин, а матрицы инцидентности n × m, n – число вершин, m – число ребер в графе.