Ориентированные и неориентированные графы

Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не прини­мается во внимание.

Ребро графа называется ориентированным, если этот порядок существенен. В этом случае говорят, что для ребра g = (x_i, x_j): x_i – начальная, a x_j – конечная вершины ребра.

Ориентирован­ное ребро называют дугой графа (рис. 3.2).

 

 

Рис. 3.2. Дуга ориентированного графа

Граф называется неориентиро­ванным или неорграфом, если каждое ребро его не ориентированно, и ориентирован­ным или орграфом, если каждое ребро его ориенти­рованно. Если граф содержит ори­ентированные и неориентирован­ные ребра, он называется смешанным.

Полным неориентированным графом называется граф U(X), ребрами которого являются всевозможные пары (x_i, x_j) для всех возможных вершин x_i, x_j Î X, i ¹ j.
В таком графе все вершины являются смежными (рис. 3.3).

Рис. 3.3. Полные неориентированный и

ориентированный графы

Полным ориентированным графомU₀(X) называ­ется граф, у которого любые две вершины соединены хотя бы в одном направле­нии.

Петлей называется ребро g = (x_i, x_i), у которого начальная и конечная вершины совпадают (рис. 3.4) Петля обычно считается неориентиро­ванной.

Рис. 3.4. Петля

Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными ребра­ми или дугами (рис.3.5).

 

 

Рис. 3.5. Неориентированный и ориентированный мультиграфы

Дополнением графа G(X) является такой граф G_d(X), ко­торый совместно с графом G(X) образуют полный граф: U(X) = G(X) È G_d(X).