Закон исключенного третьего 12 страница

Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

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

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

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

Пример.На рис. 18.7: в графе – ребро – мост; в графе – вершина – точка сочленения; в графе – множество вершин – разделяющее множество.

Рисунок 18.7

Определение. Граф называется:

- связным, если для любых вершин u, v есть путь из u в v.

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

- деревом, если он связный и не содержит простых циклов (рис 18.8).

Рисунок 18.8 – Граф – дерево

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

Рисунок 18.9 – Полные графы

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

Рисунок 18.10 – Полные двудольные графы

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

- планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер (рис. 18.11).

Рисунок 18.11 – Планарный граф и его плоское изображение

- взвешенным или нагруженным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра (рис. 18.12).

Рисунок 18.12 – Нагруженный граф

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

Рисунок 18.13 – Граф Петерсена – регулярный граф 3-й степени

18.4 Способы задания графов

18.4.1 Геометрическая реализация графа

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

Рисунок 18.14 – Геометрический способ задания графа

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

18.4.2 Матрица инциденций (инцидентности)

При задании графа таблицейсоставляется таблица,состоящей из строк (вершины) и столбцов (ребра). На пересечении строк и столбцов пишутся соответствующие знаки, которые показывают отношение (инцидентность) вершины и ребра. Это может быть знаки “+” и “ – ”, числа 0,1, – 1 и др.

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

Определение. Матрицей инциденций Вданного графа будет таблица, состоящая из строк (вершины) и столбцов (ребра). При рассмотрении неориентированного графа на пересечении строк и столбцов ставится число 1, если соответствующие вершина и ребро инцидентны ( ) и ставится число 0, если они не инцидентны. Элементы матрицы инциденций неориентированного графа определяются следующим образом:

При рассмотрении ориентированного графа на пересечении строк и столбцов ставится число 1, если из вершины выходит соответствующее ее ребро. Если в вершину входит ребро, то ставят число (– 1). Если вершина не инцидентна ребру, то ставится число 0. Элементы матрицы инциденций неориентированного графа определяются следующим образом:

Очевидно, что в каждом столбце матрицы инцидентности должно быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки – степень соответствующей вершины.

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

Пример.Построим матрицы инциденций для графов на рис. 18.15.

Рисунок 18.15 – Ориентированный и соответствующий ему неориентированный графы

Таблица 18.1 – Матрица инциденций ориентированного графа (рис. 18.15а)

	a	b	c	d	e	f	g	h
					-1
	-1	-1	-1
							-1
				-1
						-1
								-1

Таблица 18.2 – Матрица инциденций неориентированного графа (рис. 18.15б)

	a	b	c	d	e	f	g	h

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

18.4.3 Матрица смежности

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

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

Матрица смежностинеориентированного графа является симметричной и не меняется при транспонировании. Хотя формально каждая вершина всегда смежная сама с собой, в матрице смежности мы будем ставить 0, если у нее нет петли, и 1, если есть одна петля. Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули. Элементы матрицы смежности определяются следующим образом:

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

Пример.Построим матрицы смежности для графов на рисунке 18.15.

Таблица 18.3 – Матрица смежности ориентированного графа (рис. 18.15а)

Сумма элементов по строке равна степени полуисхода вершины, сумма элементов по столбцу – степени полузахода вершины.

Таблица 18.4 – Матрица смежности неориентированного графа (рис. 18.15б)

Сумма элементов по строке (и по столбцу) равна степени вершины.

18.4.4 Список ребер

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

Более абстрактно, граф можно задать как тройку , где и – некоторые множества (вершин и рёбер, соответственно), а – функция инцидентности, сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов).

На основе рассмотренных понятий можно дать окончательные определения неориентированного и ориентированного графов.

Определение. Назовем абстрактным неориентированным графом совокупность непустого множества , произвольного множества , причем , и произвольного отображения . Элементы множеств и – соответственно вершины и ребра графа, а – отображение инцидентности (отношение смежности).

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

18.4.5 Число вершин и ребер графа

Теорема 18.1. Сумма степеней вершин неориентированного графа равна удвоенному числу его ребер, т.е. если , то .

Это утверждение почти очевидно и следует из того, что каждое ребро графа инцидентно ровно двум вершинами, и поэтому вклад каждого ребра в сумму степеней вершин равен двум.

Теорема 18.2. В неориентированном графе число вершин нечетной степени четно.

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

.

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

Для ориентированного графа сумма полустепеней исхода равна сумме полустепеней захода и равна количеству ребер графа:

.

18.5 Контрольные вопросы и задания

1. Дайте определения графа.

2. Какой граф называется неориентированным? Приведите примеры.

3. Какой граф называется ориентированным? Приведите примеры.

4. Какой граф называется пустым?

5. Дайте определение полного графа. Приведите примеры.

6. Какие вершины являются смежными в графе?

7. Какие вершины и ребра инцидентны в графе. Приведите примеры.

8. Дайте определение абстрактного ориентированного графа.

9. Перечислите способы задания графов.

10. Как составляется матрица смежности? Приведите пример.

11. Что такое матрица инциденций? Приведите пример.

12. Поясните геометрический способ задания графа.

13. Чему для ориентированного графа равна сумма полустепеней исхода?

14. Какой граф называется взвешенным или нагруженным?

15. Дайте определение пути в графе.

16. Дайте определения цикла в графе.

17. Поясните понятие маршрута в графе.

18. Приведите пример изоморфных графов.

19. Какой граф называется связным?

20. Дайте определение компоненты связности.

21. Как определить степень вершины графа?

22. Какой граф называется деревом?

Лекция 19. Операции над графами. Изоморфизм графов. Плоские и планарные графы

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

19.1.1 Операции удаления ребер и вершин

Удаление ребра. Пусть – ребро графа . Граф получается из графа в результате удаления ребра , т.е. .

Рисунок 19.1 –Удаление ребра

Удаление вершины. Пусть – вершина графа . Граф получается из графа G в результате удаления вершины и всех инцидентных ей ребер, т.е. .

Рисунок 19.2 –Удаление вершины .

19.1.2 Операция введения вершины в ребро и операция введения ребра в граф

Операция введения вершины в ребро. Пусть и Операция введения вершины в ребро преобразует это ребро в два ребра и .

Рисунок 19.3 – Введение вершины

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

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

.

Рисунок 19.4 – Введение ребра

19.1.3 Дополнение графа

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

Пример. На рис. 19.5 изображен граф и его дополнение.

Рисунок 19.5 – Граф и его дополнение

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

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