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

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

В этом случае говорят, что для ребра g(x_i, x_j) x_i – начальная, а x_j – конечная верши­ны ребра. Ориентированное ребро называют также дугой графа (рис.2.2).

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

Для каждого графа G(x) существует об­ратный граф.G^-1(x), полученный изменением ориентации каждого из ре­бер графа G(x) на противоположную.

Полным неориентированным графом называется граф U(x), реб­рами которого являются всевозможные пары g(x_i, x_j,) для двух возможных x_i, x_j X, ij (рис.2.3).

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

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

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

Дополнением графа G(x) является такой граф G_k(x), ребра которого совместно с графом G(x) образуют полный U(x) граф.

2.1.3 Цепи, циклы, пути и контуры графов

Для неориентированных графов справедливы следующие понятия.

Цепь– конечная или бесконечная последовательность ребер

S = (…,g₁, g₂,…), в которой у каждого ребра g_k одна из вершин является вершиной ребра g_k-1, а другая – вершиной ребра g_k+1. При этом одно и то же ребро или вершина может встречаться несколько раз (рис.2.6):

{g₀, g₁, g₂, g₃, g₄, g₅, g₂, g₆} = {(x₀, x₁), (x₁, x₂), (x₂, x₃), (x₃, x₁), (x₁, x₄), (x₄, x₃), (x₃, x₂), (x₂, x₅)}.

Цепь называется простой, если все ребра в ней различны, и состав­ной или сложной – в противном случае. Величины (вершины)в простой цепи могут повторяться. Цепь называется элементарной, если в ней ни одна из вершин не повторяется.

Циклом называется конечная цепь, начинающаяся на некоторой вершине x_i и оканчивающаяся на той же вершине.

Простые, составные или сложные, элементарные циклы – по анало­гии с цепями.

Для ориентированных графов введены следующие дополнительные понятия.

Путемв графе G(x) называется такая последовательность дуг

(g₁, g₂ ,…), что конец каждой предыдущей дуги является началом следую­щей. Существуют простые, составные (сложные), элементарные пути.

Контурграфа – это конечный путь, у которого начальная вершина совпадает с конечной. Существуют простые, составные (сложные), эле­ментарные контуры.

Длина пути есть число дуг L(s) в последовательности дуг пути s. В случае бесконечного пути L(s) = .

Граф называетсясимметри­ческим, если  x_i, x_j из того, что x_i  G(x_j)  x_j  G(x_i), то есть две смежные вершины x_i, x_j всегда соединены противоположно ори­ентированными дугами (рис.2.7).

Граф называется антисим­метрическим, если  x_i, x_j; x_i  G(x_j)  x_j  G(x_i), то есть каждая пара смежных вершин соединена только в одном направлении.