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

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

В этом случае говорят, что для ребра 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) граф.