Тема 7. Графы

Тема 7. Графы

Введение о графах

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

Представление графов в ЭВМ

Конструирование структур данных для представления в программе объектов математической модели – это основа искусства практического программирования. Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Например, представление графов с помощью диаграмм, матриц смежности и матриц инциденций и других.

Основные понятия:

Неупорядоченная пара вершин называется ребром, упорядоченная пара – дугой.

Представим все элементы в виде множества вершин и множества ребер, отображающих отношение .

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

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

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

Пример 1.

Порядок графа - число вершин конечного графа. В примере 1 .

Размерность графа - общее число вершин и ребер конечного графа.

В примере 1 .

Смежные вершины – пара вершин , соединенные хотя бы одним ребром.

Пример 2.

Вершины - не соединены ребром, следовательно, они несмежные.

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

Ребро, инцидентное вершине - ребро , соединенное с указанной вершиной . В примере 2 ребро инцидентно вершине , а ребра - вершинам ,

Пусть - множество всех ребер, инцидентных вершине .

В примере 2: , , .

Кратные ребра – различные ребра, имеющие одинаковые смежные вершины.

В примере 2: - кратные ребра.

Петля – ребро , для которого смежными вершинами является одна и та же вершина .

Пример 3.

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

Замечание. Петли - кратные ребра.

Смежные ребра – различные ребра, имеющие общую одну и ту же вершину, которая им коинцидентна. В примере 3 - смежные ребра, так как имеют общую вершину .

Степень (валентность) вершин: - число смежных ребер, связанных с вершиной .

В примере 2: .

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

В примере 3: .

Типы графовых моделей сложных систем

Считаем, что между двумя вершинами графа можно провести одно ребро. Если между двумя вершинами можно провести несколько ребер – мультиграф.

Пример.

Мультиграф с разрешенными петлями – псевдограф (пример 3).

Граф без кратных ребер и петель – простой граф.

Пример.

– класс графов простых;

– класс мультиграфов;

– псевдограф, то .

Простой граф – полный, если любые две вершины соединены ребром. - обозначение такого графа, - количество вершин. Всякий граф , содержит ребер.

Пример 4. - безреберный граф.

Пример 5 (полные графы).

Пример 6.

(неполный граф или цепь)

Цепью называется последовательность ребер вида , .

Пример 7.

Число ребер цепи, соединяющей вершины и , называется ее длиной .

В примере 7 длина цепи .

Циклом называется цепь, начальная и конечная вершины которой совпадают. В примере 7 цикл выделен пунктирной линией.

Путем называется последовательность дуг вида , .

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

Пример 8 (графы изоморфны).

Пример 9 (графы изоморфны).

Пример 10 (графы неизоморфны).

Общее число неполных простых графов c -вершинами равно .

Рассмотрим простой, полный граф с -вершинами. Напомним, что количество ребер - . Теперь докажем, что общее число неполных простых графов c -вершинами равно . Рассмотрим, например, когда . Тогда количество ребер при равно а общее число неполных простых графов при равно Представим графически все простые графы при , в частности

-  безреберный граф, , количество простых графов (количество сочетаний т. к. );

-  граф с одним ребром, , количество простых графов (количество сочетаний );

-  граф с двумя ребрами, , количество простых графов (количество сочетаний );

-  граф с шестью ребрами, - полный.

И всего таких неполных простых графов будет .

Класс матриц инциденций и класс матриц смежности

Класс матриц инциденций. Если граф содержит вершин и дуг, то матрица инциденций определяется как

Иногда граф содержит петли, т. е. дуги вида . В этом случае некоторые элементы матрицы одновременно равны и 1, и –1, что приводит к неоднозначности элементов матрицы .

Дополнительный материал.

Понятие взвешенного графа.

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

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

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

Пример. Рассмотрим взвешенный граф, вершины которого , взвешены переменными . Тогда граф (рис. 1) задается матрицами рассмотренного класса как

, .

В матрице столбцам соответствует мощность носителя - ; строкам – мощность сигнатуры - .

Класс матриц смежности. Матрица смежности графа определяется следующим образом:

Для взвешенного графа

Дополнительный материал.

Матрицы полностью описывают взвешенный граф. Например, граф (рис.1) задается матрицами этого класса как

, .

При задании графа отсутствует матрица , так как дуги этого графа не взвешены.

Если бы дуги графа (рис. 1) были взвешены, то вместо единиц в матрице записывались веса .

Операции над графами

1)  Изъятие вершины (подмножества вершин)

: .

!Пояснение. : - обозначает изъятие вершины; - вершины, которые удаляются.

Пример.

изъятие одной вершины изъятие двух вершин изъятие трех вершин

2)  Изъятие ребра (подмножества ребер)

: .

!Пояснение. : - обозначает изъятие ребер; - ребра, которые удаляются.

изъятие одного ребра изъятие трех ребер

3)  Отождествление (стягивание) вершин

Вершины заменяются вершиной . Все ребра, имеющие концами переходят в , а вершины - исчезают.

Пример 1 Пример 2 Пример 3

4)  Стягивание ребер (ребра)

Стягиваем ребро (дугу) в одну вершину: (две вершины соединяются в одну).

Пример 1 Пример 2 Пример 3

5)  Расщепление вершины – операция обратная стягиванию.

Вершину расщепляем на . Часть ребер адресуется , а другая адресуется к . Обязательно между проводится ребро.

6) 

Объединение графов

Объединением графов и называется граф , носитель и сигнатура которого являются соответственно теоретико-множественным объединением носителей и сигнатур графов (рис. 2, a).

7)  Сумма графов

Суммой графов и называется граф , представляющий собой объединение графов и каждая вершина соединяется со всеми вершинами и наоборот (рис. 2, б).

8)  Произведение (декартово произведение)

Произведением графов и называется граф , , (рис. 2, в), где

!Пояснение. ; ; - получили вершины графа .

; ; ;

; ; .

где

Рис. 2

Связность для неориентированных графов

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

Пример.

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

Пример.

Рассмотрим алгоритм определения связности графа и числа его компонент.

Теорема 1. Элемент матрицы , - матрица смежности,

представляет собой множество цепей длины , соединяющих вершины .

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

Определение. Минимальная длина цепи (число ребер цепи), соединяющей вершины , называется расстоянием между вершинами :

.

Определение. Максимальное расстояние между вершинами графа называется диаметром графа :

.

Определение. Матрица называется -клеточной, если в результате перестановки строк и столбцов она приводится к виду

А – квадратная матрица

,

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

Теорема 2. Граф состоит из компонент связности тогда и только тогда, когда его матрица достижимости

является -клеточной, где - матрица смежности, - диаметр графа .

Пример. Рассмотрим распределение цепей в неориентированном графе (рис. 3).

Рис. 3

Определим матрицу смежности. Она имеет следующий вид.

.

Матрица смежности является симметричной.

Далее определим диаметр графа: .

Определим матрицу достижимости . Так как диаметр графа , то из теоремы 2 следует, что.

,

Определим матрицу :

,

тогда

.

Матрица достижимости является двух клеточной (), следовательно, граф состоит из двух компонент связности с носителями соответственно , что видно и из рисунка 3.

В матрице смежности - существует цепи длиной 1, в матрице - существует цепи длиной 2, в матрице достижимости - существует цепи длиной 1 и 2.

Сильная связность для ориентированных графов

Определение. Граф называется сильно связным, если любая пара вершин соединена путем.

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

Пример. Определим сильную связность ориентированного графа (рис. 4), матрица смежности которого имеет следующий вид:

Далее определим диаметр графа: Диаметр графа .

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

Определим матрицу :

,

,

тогда

.

В матрице достижимости элементы показывают связь между подматрицами размерами и

Компоненте сильной связности в матрице достижимости соответствует подматрица максимального размера, каждый элемент которой не равен 0. Элементы, показывающие связь между этими подматрицами, могут быть не равны 0.

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

Возникает вопрос: Зачем необходимо находить связность графа?

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

Цикломатика

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

Определение. Разрезом называется такое разделяющее множество, которое не имеет собственного разделяющего подмножества. Множество не является разрезом, поскольку оно содержит разделяющее подмножество

. Это подмножество не имеет собственных разделяющих подмножеств и поэтому является разрезом.

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

Каждый элемент вектор-строки данной матрицы определяется следующим образом:

Пример. Рассмотрим граф, изображенный на рис. 6, а.

1) Для исследования циклов в графе построим цикломатическую матрицу. Цикломатическая матрица этого графа имеет вид:

Определение. Множество всех векторов-строк, каждый из которых соответствует одному циклу графа , образует векторное пространство, называемое пространством циклов графа .

Например, множество, состоящее из строк является векторным пространством графа .

При этом выполняются следующие условия:

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

2.  Сложение по модулю два обладает свойством коммутативности, т. е. для любых двух ,

.

3.  Сложение по модулю два ассоциативно, т. е. для любых ,

.

Определение. Базис циклов графа - это базис пространства циклов графа , состоящий из простых циклов.

Вектор зависит от простых циклов , если он представим в виде линейной комбинации векторов

.

2) Определение цикломатического числа графа .

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

Пример. Цикломатическое число ( рис.6, а), следовательно, количество базисных циклов в графе равно 3.

Если связный граф имеет вершин и ребер, то

.

На рис. 6, a .

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

. (1)

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

(2)

Пример.

.

3) Определение базисной системы циклов.

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

, , , ().

!Пояснение.

Определение. Деревом называется связный граф, не содержащий ни одного цикла (рис. 6,б).

Определение. Остовный подграф графа – это подграф, содержащий все вершины графа.

Определение. Остовом называется остовный подграф, являющийся деревом.

Остов - это остовный подграф с ребрами (рис. 6, б).

Определение. Хордой остова в связном графе называется всякое ребро графа, не принадлежащее (рис. 6, б).

Хордой остова будут ребра (рис. 6, б).

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

4) Построение базисной цикломатической матрицы относительно остова . Т. к. , то 3 ребра будут хордами, каждое только одному циклу их трех.

Теорема Эйлера. Число базисных циклов графа постоянно и равно его цикломатическому числу.

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

Полученная матрица является базисной цикломатической матрицей относительно остова .

5. Построение базисной матрицы разрезов или базисной коцикломатической матрицы.

Базисная система разрезов для графа и остовного дерева (рис. 6,б): .

Данная система получается следующим образом. Удаляется ребро остова . Множество вершин при этом распадается на два непересекающихся подмножества и . Множество всех ребер в , каждое из которых соединяет вершину из с вершиной из , является разрезом графа .

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

6) Построение коцикломатической матрицы разрезов.

Коцикломатический ранг (ранг разреза) графа – это число ребер в его остовном лесе:

Выполняя раз операцию сложения по модулю два над коциклами, порождаем все множество коциклов (разрезов) графа разрезов.

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

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

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

Сопоставим каждой дуге положительное число, определяющее ее пропускную способность.

Теперь сформулируем теорему для такого взвешенного по дугам ориентированного графа.

Теорема Менчера. Максимальный поток через сеть равен минимальной пропускной способности ее разреза.

Пример.

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