Краткий перечень основных понятий теории графов

Общие понятия

Графы помогают описывать и исследовать различные системы объектов и их связи. Например, в графе, изображенном на рис. 1, точки (вершины графа) можно интерпретировать как города, а линии, соединяющие вершины (ребра), как дороги, соединяющие эти города.

 

Рис. 1.

 

Формальное определение графа таково [1-8]. Графом Г=(V, X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами. Если v, w Î V, x=(v,w)ÎX, то говорят, что ребро x соединяет вершины v и w или x инцидентно v и w. Таким образом, {v,w} – обозначение ребра. Если Х представляет собой упорядоченные пары (т. Е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары {v,w} называют дугами. Если множеству X принадлежат пары v = w, то такие ребра (v, v) называют петлями. Существование одинаковых пар {v,w} соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар.

Например, кратность ребра { v ₁,v₂} в графе, изображенном на рис. 2, равна двум, кратность ребра { v ₃,v₄} − трем.

Рис.2.

 

Псевдограф − граф, в котором есть петли и/или кратные ребра.

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

 

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

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или v_i)– вершина или номер вершины;

G, G ₀ – неориентированный граф;

D, D ₀ – ориентированный;

{ v, w } − ребра неориентированного графа;

{ v, v } – обозначение петли;

(v, w) − дуги в ориентированном графе;

v, w – вершины, x, y, z – дуги и ребра;

n (G), n (D) количество вершин графа;

m (G) – количество ребер, m (D) – количество дуг.

Примеры

1) Ориентированный граф D =(V, X), V ={ v ₁, v ₂, v ₃, v ₄},

X ={ x ₁=(v ₁, v ₂), x ₂=(v ₁, v ₂), x ₃=(v ₂, v ₂), x ₄=(v ₂, v ₃)}.

 

Рис. 3.

 

2) Неориентированный граф, изображенный на рис. 4:

G =(V, X), V ={ v ₁, v ₂, v ₃, v ₄, v ₅},

X ={ x ₁={ v ₁, v ₂}, x ₂={ v ₂, v ₃}, x ₃={ v ₂, v ₄}, x ₄={ v ₃, v ₄}}.

 

Рис. 4.

 

 

Понятия смежности, инцидентности, степени

Если x ={ v, w } - ребро, то v и w − концы ребра x.

Если x =(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).

Вершины v, w называются смежными, если { v, w }Î X.

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d⁺(v) (d^-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d⁺(v), так и в d^-(v).

 

Маршруты и пути

Последовательность v ₁ x ₁ v ₂ x ₂ v ₃… x _k v _k+1, (где k ³1, v _iÎ V, i =1,…, k +1, x _iÎ X, j =1,…, k), в которой чередуются вершины и ребра (дуги) и для каждого j =1,…, k ребро (дуга) x _j имеет вид { v_j, v_{j +1}} (для ориентированного графа (v_j, v_{j +1})), называется маршрутом, соединяющим вершины v ₁ и v_{k +1} (путем из v ₁ в v_{k +1}).

 

Пример

В графе, изображенном на рис.4, v ₁ x ₁ v ₂ x ₂ v ₃ x ₄ v ₄ x ₃ v ₂ – маршрут, v ₂ x ₂ v ₃ x ₄ v ₄ – подмаршрут;

маршрут можно восстановить и по такой записи x ₁ x ₂ x ₄ x ₃;

если кратности ребер (дуг) равны 1, можно записать и так v ₁ v ₂ v ₃ v ₄ v ₂.

 

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

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