3. Путь в ориентированном графе

Определение: Путем , соединяющим вершины v₁ и v_k+1 , называется последовательность v₁x₁v₂x₂…v_kx_kv_k+1 , где k 1, v_i  V, x_i X, дуга x_i соединяет вершины v_i с вершиной v_i+1 . Вершина v₁ (v _нач)– начало пути (начальная вершина), v_k+1 (v _кон)– конец пути (конечная вершина). Остальные вершины называются внутренними вершинами пути.

Найдем какой-либо путь из v₁ в v₃ : v₁x₁v₂x₃v₂x₄v₃ .

Допускается краткая запись пути. В том случае, если в пути нет кратных дуг, то составляют последовательность только из вершин.

Если в пути есть кратные дуги, то в последовательность включают начальную вершину, дуги и конечную вершину. Или пользуются комбинированной записью: в последовательность включают все вершины и только кратные ребра.

Перепишем наш путь, использую комбинированную запись: v₁x₁v₂v₂v₃. В последовательность включено только кратное ребро x₁ .

Длиной пути l называется количество дуг в нем.

В нашем пути 3 дуги, значит его длина l =3.

Познакомимся с видами путей.

Если v_нач = v_кон , то путь называется замкнутым.

Если v_нач  v_кон , то путь называется незамкнутым.

Виды незамкнутых путей:

Незамкнутый путь, в котором все дуги попарно различны называется цепью.

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

Виды замкнутых путей:

Замкнутый путь, в котором все дуги попарно различны называется контуром.

Контур, в котором все вершины попарно различны называется простым контуром.

Заметим, что петля являются простым контуром.

Составим различные пути для приведенного выше орграфа :

v₁x₁v₂x₃v₂x₄v₃ – незамкнутый путь, являющийся цепью (в нем все дуги попарно различны);

v₂x₃v₂ – простой контур;

v₁x₂v₂x₄v₃ – простая цепь (все вершины и дуги попарно различны).

Для графа D(V,X) справедливы утверждения:

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

Из любого незамкнутого пути можно выделить простую цепь с теми же начальной и конечной вершинами.

4. Связность. Компоненты связности в орграфе

Вершина w орграфа D достижима из вершины v, если:

а) v = w ;

б) существует путь из v в w.

Орграф называется сильно связным, если для любых его вершин v, w существует путь из v в w, и из w в v.

Орграф называется односторонне связным, если для любых двух вершин хотя бы одна достижима из другой.

Пример:

u₂

u₁ сильно связный граф

u₃

u₂

u₁ односторонне связный граф

u₃

Псевдографом, ассоциированным с ориентированным псевдографом D(V, X), называется псевдограф G(V, X₀), в котором Х₀ получается заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w}.

Пример: Дан орграф D(V, X):

Для него G (V, X₀):

Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

В рассмотренном выше примере граф G (V, X₀) связный, значит орграф D(V, X) – слабо связный.

Если орграф не является слабо связным, то он называется несвязым.

Пример:

Представленный на этом рисунке граф D(V , X) – несвязный, т.к. ассоциированный ему граф G(V, X₀) – несвязный, т.к. р(G) = 2.

Компонентой сильной связности графа D называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа орграфа D.

Пример:

Этот орграф имеет две компоненты сильной связности:

D₁ D₂

Значит Р (D) = 2.

Замечание: Вершина достижима сама для себя, поэтому является сильно связным подграфом.

Орграф D(V , X) Компоненты сильной связности орграфа D(V , X)

Этот граф имеет три компоненты сильной связности.

Из определения компоненты сильной связности следует справедливость утверждений:

Пусть D₁(V₁, X₁) – компонента сильной связности орграфа D(V, X), тогда D₁ – подграф орграфа D(V, X) , порожденный множеством V₁.

Пусть D(V, X) – орграф с р компонентами сильной связности: D₁(V₁, X₁) ,…, D_р(V_р, X_р) . Тогда:

1. V = V₁ …V_p , X  X₁ … X_p ;

2. V_i V_j = , X_i X_j = , если i  j ;

3. n(D₁) +…+ n(D_p) = n(D), m(D₁) +…+ m(D_p)  m(D).