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

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

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

Пример.

Рис. 3.1. а) – н–граф; b) – орграф.

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

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

Граф без петель и кратных ребер называется полным, если каждая пара вершин соединена ребром.

Пример.

Рис. 3.2. а) полный граф, b) нуль–граф, c) мультиграф

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

Пример.

Рис. 3.3. а) граф G, b) дополнение графа G.

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

Локальной степенью (или просто степенью) вершины н–графа называется количество ребер , инцидентных вершине . В н–графе сумма степеней всех вершин равна удвоенному числу ребер графа, т.е. четна, если считать, что петля дает вклад 2 в степень вершины:

.

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

Пример. Н–граф на рис. 3.1а имеет две вершины нечетной степени (вершины и ). Степени остальных вершин четны.

Для вершин орграфа определяются две локальные степени:

– количество дуг исходящих из вершины ;

– количество дуг входящих в вершину .

Петля дает вклад 1 в обе эти степени.

В орграфе суммы степеней всех вершин и равны количеству дуг этого графа и равны между собой:

.

Пример. Для орграфа на рис. 3.1b локальные степени вершин равны: