Теория графов

2. ПРЕДСТАВЛЕНИЯ ГРАФОВ В ЭВМ И ОПЕРАЦИИ НАД НИМИ.

2.1. Матричные способы задания графов.

Матрицей смежности графа G=(V,E) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

а) в случае неориентированного графа

матрица смежности имеет вид

Свойства матрицы смежности: Матрица смежности неориентированного графа является симметричной относительно главной диагонали. Диагональные элементы этой матрицы указывают на наличие петель в соответствующем графе.

Сумма элементов матрицы А неориентированного графа по i-ой строке (или i-му столбцу) равна d(vi). Для ориентированного графа сумма элементов матрицы А по i-ой строке рав-

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

Объём памяти для матрицы смежности – О(n2) Матрицей инцидентности графа G=(V, E) с n вершина-

ми и m ребрами называется матрица В размера n×m, элементы которой определяются следующим образом:

а) для неориентированного графа

б) для ориентированного графа

Например, для графа предыдущего примера:

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

Объём памяти для матрицы инцидентности – О(nm)

11

2.2. Список ребер (дуг) и структура смежности графа.

Если граф является разреженным, то есть когда число

сообразно представлять граф посредством списка рёбер (дуг).

Пример. Для графа, приведенного ранее, имеем:

v (1,1,2,2,3,4,1,2,4) и u (2,5,5,3,4,5,6,6,6) . Здесь для упроще-

ния записи мы пишем 1 вместо a1 , 2 - вместо a2 и т.д.

Объём памяти для списка рёбер (дуг) – О(2m) Представлением графа, удобным при операциях с гра-

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

Объём памяти для структуры смежности – О(n+m)

2.3. Части графов.

Полный подграф некоторого графа называется кликой этого графа.

12

стве вершин Vp называется граф Gp=(Vp, Ep), причем Vp V ,а Ep – множество ребер или дуг графа G, оба конца которых принадлежат множеству Vp.

Пример. На следующем рисунке изображены:

2.4. Основные операции над графами.

Объединением графов G1=(V1, E1) и G2=(V2, E2) называется граф G3=(V1 V2, E1 E2). Объединение называется дизъюнктным , если V1 V2=0.

Пересечение графов G1=(V1, E1) и G2=(V2, E2) называется

граф G3=(V1 V2, E1 E2).

Аналогично определяются объединение, дизъюнктное объединение и пересечение любого количества графов. Операции объединения и пересечения являются коммутативными,

т.е. G1 G2= G2 G1, а также G1 G2= G2 G1

Пример. На ниже приведённом рисунке показаны: а) – граф G1, б) – граф G2, в) – их объединение, г) – пересечение.

13

Удаление вершины. При удалении вершины из графа удаляются и все инцидентные ей рёбра (дуги).

Удаление ребра (дуги). При удалении ребра (дуги) его концевые вершины не удаляются. Операцией обратной к операции удаления ребра является операция добавления ребра.

Слияние (отождествление) вершин. Говорят, что вершины vi и vj в графе G отождествляются (сливаются) если они заменяются новой вершиной vk такой, что все ребра (дуги) графа инцидентные vi и vj становятся инцидентными к вершине

vk .

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

Подразбиение ребра. При выполнении этой операции из графа удаляется ребро (vi, vj) и добавляются два новых (vi, vk) и (vk, vi), где vk – новая вершина графа.

Пример:

На следующем рисунке представлены: а) - исходный граф, б) – граф после удаления вершины v3, в) - результат удаления ребра e2, г) –отождествления вершин v3 и v4, д) – стягивание ребра e1, е) – подразбиение ребра e2.

14

3. МАРШРУТЫ В ГРАФАХ.

3.1. Понятие маршрута.

Маршрутом в графе G=(V,E) называется чередующаяся последовательность вершин и ребер (дуг) – v1, e1, v2, e2, …., vn, en,vn+1, в которой любые два соседних элемента инциденты.

Маршрут, соединяющий вершины v1 и vn+1 можно также задать последовательностью из одних вершин v1, v2, v3,…,vn, vn+1 или последовательностью ребер e1, e2,…,en. Число n ребер (или дуг) в маршруте называется его длиной. Маршрут называется циклическим, если v1=vn+1.

Маршруты в неориентированных графах.

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

Неорграф без циклов называется ациклическим графом. Минимальная из длин циклов неорграфа называется его обхватом.

Пример 1: Рассмотрим неорграф

1 2

7 8

В данном примере наборы вершин: (1,2) ; (1,2,4,7) являются простыми цепями,: (1,2,4,7,8,4) - непростая цепь, (1,2,4,7,8,4,2) – маршрут, который не является цепью, (1,2,4,8,7,4,1) – непростой цикл, (1,2,4,1) – простой цикл. Об-

хват графа равен 3.

16

Маршруты в ориентированных графах.

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

Путь называется контуром, если v1=vn+1. Граф не имеющий контуров называется безконтурным. Вершина v называется достижимой из вершины u, если существует путь из u в v.

Пример 2: Рассмотрим ориентированный граф

2

4 5

13

Вданном примере наборы вершин (1,2,3,1) образуют контур. Заметим, что здесь вершина 5 – достигается из любой другой вершины, а из вершины 5 не достигается ни одна из остальных вершин.

3.2. Связность в графах.

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

Отметим, что граф в примере 1 является сильно связным, а в приме2 – не сильно связный граф.

Пример 3. На следующем рисунке показан несвязный

граф.

17

2

6

3 4

5 7

1

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

В примере 3 граф имеет две сильно связных компонен-

ты.

3.3. Связность и матрица смежности графа.

Теорема 1. Любой граф представляется в виде объединения непересекающихся (сильно) связных компонент. Разложение графа на (сильно) связные компоненты определяется однозначно.

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

Теорема 2. Если A матрица смежности графа G, то (i, j) элемент матрицы Ak=A·A·A··…·A (k раз), есть число (vi, vj) маршрутов длины k.

Следствие 1. В графе G мощности n тогда и только тогда существует маршрут (vi, vj) , причем vi ≠vj , когда (i, j) – элемент матрицы A+A2+ A3+ A4+…+ An-1 не равен нулю.

Следствие 2. В графе G мощности n тогда и только тогда существует цикл, содержащий вершину vi когда (i, i) – элемент матрицы A+A2+ A3+ A4+…+ An-1+An не равен нулю.

Пример. При помощи матрицы смежности определим существование всевозможных (1, 3) - маршрутов в графе, изображенном на рисунке.

18

4

По графу находим матрицу смежности A:

Её элемент (1,3)=0, следовательно. (1, 3) маршрутов длины 1 в графе нет. Затем находим:

Eё элемент (1, 3)=1, т.е. существует ровно один (1, 3) - маршрут длины 3. Этот маршрут определяется набором вершин (1,

4, 2, 3)

Эту последовательность вершин можно найти на основе перемножения матрицы смежности: Элемент (1, 3) матрицы A3 получается при перемножении элемента (1, 2) матрицы A2 на элемент (2, 3) матрицы A. В свою очередь элемент (1, 2) мат-

19