Лекция 5.1. Основные определения

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

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

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

Если заданы

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

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

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

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

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

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

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

Рис. 1

Рис. 2

,

.

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

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

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

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

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

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

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

Рис. 3

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

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

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

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

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

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

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

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

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