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

Граф G=(V, Е) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами. Каждое ребро определяется парой вершин. Если ребра графа определяются упорядоченными парами вершин, то G называется направленным или Ориентированным графом. В противном случае G называется ненаправленным или Неориентированным графом. Для обозначения вершин графа будем использовать символы v1, v2, v3,…, а для обозначения ребер - е1, е2, е3, . . . . Вершины vi и vj, определяющие ребро ei, называются концевыми вершинами ребра еi. В этом случае ребро еi обозначается как ei=(vi, vj). Заметим, что в множестве Е допускается более чем одно ребро с одинаковыми концевыми вершинами. Все ребра с одинаковыми концевыми вершинами называются параллельными. Кроме того, концевые вершины ребра не обязательно различны. Если еi= (vi, vi), то ребро ei называется петлей. Граф называется простым, если он не содержит петель и параллельных ребер. Граф G является графом порядка n, если множество его вершин состоит из n элементов.

Граф, не имеющий ребер, называется Пустым. Граф, не имеющий вершин (и, следовательно, ребер), называется Нуль-графом.

Графически граф может быть представлен диаграммой, в которой вершина изображена точкой или кружком, а ребро — отрезком линии, соединяющим точки или кружки, соответствующие концевым вершинам ребра. Например, если V={v1 v2, v3, v4, v5, v6} и E= {e1, e2, e3, e4, e5}, такие, что e1=(v1, v2), e2=(v1, v4), e3= (v5, v6), e4= (v1, v2), e5=(v5,v5), тогда граф G=(V, E) представляется так, как изображено на рис. 1. В этом графе е1 и e4 - параллельные ребра, е5 - петля. Говорят, что ребро Инцидентно своим концевым вершинам. Две вершины Смежны, если они являются концевыми вершинами некоторого ребра. Если два ребра имеют общую концевую вершину, они называются Смежными.

Рисунок 1

Например, в графе на рис. 1 ребро е1 инцидентно вершинам v1 и v2; v1 и v4 являются смежными вершинами, а е1 и е2 - смежными ребрами.

Число инцидентных вершине vi ребер называется степенью вершины и обозначается d(vi). Иногда степень вершины называется также ее валентностью. Вершина степени 1 называется Висячей вершиной. Единственное ребро, инцидентное висячей вершине, называется висячим. Вершина степени 0 называется Изолированной. По определению петля при вершине vi добавляет 2 в степень соответствующей вершины. Величины δ(G) и ∆(G) обозначают минимальную и максимальную степени вершины в G соответственно.

В графе G на рис. 1 d(v1) = 3, d(v2) = 2, d(v3) = 0, d (v4) = 1, d (v5) = 3, d(v6) = 1.

Заметим, что v3- изолированная вершина, v4 и v6- висячие вершины, е2 — висячее ребро. Легко проверить, что сумма степеней вершин в данном графе G равна 10, тогда как число ребер равно 5. Таким образом, сумма степеней вершин графа G равна удвоенному числу ребер графа G и, следовательно, является четным числом. Более того, можно показать, что число вершин графа G нечетной степени также четно. Эти результаты свойственны не только графу на рис. 1.

< Предыдущая		Следующая >