Вершины, ребра (дуги), графы

Совокупность множества вершин V и множества связей Е между ними называется графом и обозначается G(V, E).

На рис. 2.1 показан пример графа G(4,6), где обозначено:

V = {x₁, x₂, x₃, x₄} – множество вершин,

n = |V| = 4 – число вершин графа G(4,6),

E = {e₁, e₂, e₃, e₄, e₅, e₆} – множество ребер,

m = |E| = 6 – число ребер графа G(4,6).

E – это отображение V в V (E: V V).

Рисунок 2.1

Иногда множество E называют семейством связей, так как в E могут входить направленные и ненаправленные связи, петли и все они могут быть кратными, тогда как в теории множеств одинаковые элементы представляются одним элементом.

В качестве другого примера на рис. 2.2 показано семейство графов на четырех вершинах.

Обратите внимание на общепринятые обозначения некоторых графов:

N₄ – нуль граф;

P₄ – цепь;

C₄ – цикл;

W₄ – звезда;

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

В общем случае эти типы графов обозначаются так:

N_n, P_n, C_n, W_n, K_n.

Обратим внимание на граф C₄. Этот граф можно представить и так, как показано на рис. 2.3. Такой граф обозначается K_2,2 и называется полным двудольным графом.

В двудольном графе множество вершин V разбито на два подмножества X и Y таких, что между вершинами внутри каждого из них нет связей. Число ребер в полном двудольном графе m = n₁n₂, где n₁ =|X|, n₂ = |Y|, n = n₁ + n₂.

Рисунок 2.2

Рисунок 2.3

Если связь имеет направление, то она называется дугой, в противном случае – ребром. (Графы с дугами и ребрами показаны на рис. 2.4.)

Рисунок 2.4

При необходимости конкретная дуга (ребро) обозначается либо собственным именем, либо парой вершин в круглых (прямых) скобках e = (v₁,v₂) – дуга e, (e = [v₁,v2] – ребро e).

Граф, у которого все связи являются ребрами, называется неориентированным графом или сокращенно неорграфом (рис. 2.4, а).

Граф с дугами называется ориентированным графом или орграфом (рис. 2.4, б).

Ребро (дуга), оба конца которого связаны с одной и той же вершиной, называется петлей (рис. 2.5).

Рисунок 2.5

Если у графа существуют кратные ребра, т.е. несколько ребер, соединяющих одну и туже пару вершин, то такой граф называется мультиграфом. Если все ребра мультиграфа имеют одинаковую кратность k, то такой граф называется k–кратным или просто k–графом. На рис. 2.6 показан мультиграф G(6,20):

а, в – две вершины графа; e₁, e₂, e₃, e₄ – кратные ребра, соединяющие вершины а и в.

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

Рисунок 2.6

Две вершины называются смежными, если они соединяются некоторым ребром (дугой), и два различные ребра (дуги) смежны, если они имеют общую вершину. На рис. 2.8 у графа G(3,3) смежные вершины a и b; a и c; b и c, а также смежные дуги e₂ и e₃, смежные ребро e₁ и дуга e₂, смежные ребро e₁ и дуга e₃.

Вершина х инцидентна ребру (дуге) е, если она является началом или концом ребра (дуги). На рис. 2.8 вершины a и b инцидентны ребру e₁, вершины b и c инцидентны дуге e₂.

Дуга (ребро) е инцидентна вершине x, если она выходит из этой вершины или входит в нее. На рис. 2.8 дуга e₂ инцидентна вершинам b и c.

Рисунок 2.7

Рисунок 2.8