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

Основные определения

ЛЕКЦИЯ 5.1.

Свойства матрицы инцидентности орграфа.

Матрица инцидентности ориентированного графа.

Если в орграфе G р вершин и q дуг, то элементы его матрицы инцидентности определяются правилом

i = 1, …, p; j = 1, …, q.

Пример орграфа и его матрицы инцидентности показан на рис. 12.

	-1	-1	-1
				-1	-1
						-1	-1	-1
									-1
										-1
											-1	-1

Рис. 12

· Число единиц в i- й строке равно степени входа i- ой вершины, i = 1, 2, …, р.

· Число единиц с минусом в i- ой строке равно степени выхода i- ой вершины, i = 1, 2, …, р.

· Число единиц в матрице равно числу единиц с минусом и равно числу дуг в графе.

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

Неформально граф – это диаграмма, состоящая из кружков и линий, соединяющих кружки (рис.1). Кружки называются вершинами графа, а линии – ребрами. Такой граф называется неориентированным. Граф называется ориентированным (рис.2), если каждая линия снабжена стрелкой, показывающей допустимое направление движения от вершины к вершине. Ребро со стрелкой называется дугой. Дадим строгие определения.

Определение. Говорят, что задан неориентированный граф ,

Если заданы

· Конечное множество , называемое множеством вершин графа

· Конечное множество , называемое множеством ребер графа

· Антисимметричное бинарное отношение

· Тотальная сюръекция , ставящая в соответствие каждому ребру пару вершин .

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

Мощность множества V – число вершин графа – обозначим буквой . Число ребер графа обозначим буквой .

Проще всего вершины перенумеровать и обозначать каждую вершину её номером. Граф можно нарисовать, если вершины изображать кружками, а ребра – линиями, соединяющими соответствующие пары вершин. На рис. 1 показан простой граф с 4 вершинами и 5 ребрами.

Рис. 2

,

.

Говорят, что ребро инцидентно вершинам и и v, а вершины и и v инцидентны ребру . По-другому говорят, что ребро соединяет вершины и и v, авершины и и v являются концами ребра е.

Вершины, инцидентные одному и тому же ребру, называются смежными. Так же смежными называются ребра, инцидентные одной и той же вершине. Ясно, что бинарное отношение смежности – это симметричное бинарное отношение.

Множество вершин графа, смежных данной вершине v, обозначим ,

Если у ребра выделяются первая вершина – вершина и вторая вершина – вершина , ребро становится ориентированным и называется дугой. Граф G с дугами вместо ребер называют ориентированным графом или орграфом. Тогда бинарное отношение уже не обязано быть антисимметричным, и – разные дуги.

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

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

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

Рис. 3

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

Определение. Степенью вершины v неориентированного графа называется число ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной; вершина степени 1 – висячей.

Множество вершин графа, смежных с данной вершиной , обозначим .

Утверждение. (Теорема Эйлера). Сумма степеней всех вершин данного графа равна удвоенному числу ребер графа

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

Следствие. Во всяком графе число вершин нечетной степени четно.

Доказательство. Если бы это было не так, то сумма степеней вершин графа оказалось бы нечетным числом, что невозможно.

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

Определение. Степенью входа вершины v ориентированного графа называют число дуг, входящих в эту вершину. Если = 0, то вершина v называется источником.

Дата добавления: 2014-12-07