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

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

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

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), то есть каждая пара смежных вершин соединена только в одном направлении.