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

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

Пример: схема автомобильных дорог, связывающих города некоторой области, является характерным примером графа.

Ориентированный граф (орграф) – это граф, у которого пары в наборе X являются упорядоченными.

Пример: пусть , .

Тогда – ориентированный граф.

Дуга – это направленное ребро в орграфе.

Пример: в приведенном выше примере для орграфа дугами являются ребра , , _.

Начальная вершина – вершина орграфа, которой инцидентны только исходящие дуги.

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

Конечная вершина – вершина орграфа, которой инцидентны только заходящие дуги.

Пример: пусть – ориентированный граф, , , тогда – конечная вершина.

Петля – ребро графа, инцидентное единственной вершине.

Пример: пусть – ориентированный граф, ,

, тогда , , – петли.

Изолированная вершина – вершина, которая не имеет инцидентных ребер.

Пример: пусть – ориентированный граф, , , тогда , – изолированные вершины.

Степень вершины – число инцидентных ребер, .

Пример: пусть – граф, изображенный на рисунке. Тогда , , – соответственно степени вершин , , .

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

Пример: пусть – ориентированный граф, , .

Тогда – ориентированный псевдограф.

Пустой граф – граф , в котором .

Пример: пусть – граф, изображенный на рисунке. Он является пустым, т.к. ,

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

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

Мультиграф – граф, в котором имеются кратные (параллельные) ребра.

Мультиграф – это псевдограф без петель.

Пример: пусть – ориентированный граф, , . Тогда – ориентированный мультиграф.

Однородный граф – граф, все вершины которого имеют одну и ту же степень.

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

Матрица смежности – квадратная матрица является матрицей смежности графа , если при в графе вершины и соединены ребрами, при вершины и в несмежны.

Пример: для орграфа , изображенного на рисунке, приведем матрицу смежности:

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

Пример: для орграфа, приведенного в примере для матрицы смежности, составим матрицу инцидентности:

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

Пример: следующие графы, приведенные на рисунке, изоморфны:

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

Пример: последовательность – маршрут длины 3, соединяющий вершины и в графе, приведенном на рисунке.

Замкнутый маршрут – маршрут, у которого начальная вершина совпадает с конечной.

Пример: пусть – граф, показанный на рисунке, тогда – замкнутый маршрут длины 4.

Цепь – маршрут, в котором все ребра различны.

Пример: пусть – ориентированный граф, приведенный на рисунке. Тогда – цепь из в длины 3.

Простая цепь – цепь, в которой все вершины различны.

Пример: для ориентированного графа , приведенного выше в примере с цепью, и – простые цепи из в длины 2.

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

Пример: пусть – граф, показанный на рисунке, тогда – цикл.

Простой цикл – простая цепь, у которой концевые вершины совпадают.

Пример: пусть – граф, показанный на рисунке, тогда – простой цикл.

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

Пример: пусть – граф, показанный на рисунке, тогда существует Эйлеров цикл – .

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

Пример: приведенный на рисунке граф имеет Гамильтонов цикл: .

Путь (ориентированная цепь) – цепь орграфа . в которой ориентация дуг (ребер) совпадает.

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

Простой путь – путь, не содержащий повторяющихся вершин.

Пример: для ориентированного графа, приведенного на рисунке, имеем простой путь из в : .

Контур – путь, у которого начальная и конечная вершины совпадают.

Пример: для ориентированного графа, приведенного на рисунке, имеем контур:

Простой контур – контур, не содержащий повторяющихся вершин.

Пример: для ориентированного графа, изображенного на

рисунке, имеем простой контур: _.

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

Пример: пусть – исходный граф, показанный на рисунке (а), тогда – некоторый подграф графа (рисунок (б)).

Суграф графа – граф содержит то же множество вершин, что и сам граф и .

Пример: пусть – некоторый исходный граф, показанный на рисунке (а), тогда – некоторый суграф графа (б).

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

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

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

Пример: следующие два ориентированных графа, показанных на рисунке, являются сильносвязанными орграфами.

Компонента связности графа – максимальный подграф графа , в котором все вершины попарно достижимы.

Пример: у графа, показанного на рисунке, три компоненты связности.

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

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

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

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

Минимальная длина простой цепи с началом в и концом в называется расстоянием между этими вершинами.

Пример: в графе, изображенном на рисунке, расстояние между вершинами и равно трем.

Смешанный граф – это граф, содержащий как дуги, так и ненаправленные ребра.

Пример: граф, показанный на рисунке, является смешанным.

Вершина инцидентна дуге тогда и только тогда, когда является либо началом, либо концом дуги .

Пример: на рисунке вершины и инцидентны дуге .

Отношение смежности:

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

Пример: вершины и смежны, т.к. существует ребро x, инцидентное им обоим (рис (а)). Ребра и смежны, т.к. существует вершина , инцидентная им обоим (рис (б)).

Обыкновенный граф – неориентированный граф, который не содержит параллельных ребер и петель; орграф, который не содержит строго параллельных дуг и петель.

Пример: на рисунке изображен обыкновенный граф .

Обозначим через k-ю степень матрицы смежности орграфа . Тогда элемент матрицы ориентированного псевдографа , где , равен числу всех путей длины из в .