Связность в орграфах

Вершинная и реберная связность

ТЕОРЕМА Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

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

Вершинной связностью графа G (обозначается c (G))называется наименьшее чи­сло вершин, удаление которых приводит к несвязному или тривиальному графу.

Граф G называется k-связным, если c (G)= k.

Реберной связностью графа G (обозначается l(G)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

ТЕОРЕМА c(G) £ l(G) £ d(G).

Сильная, односторонняя и слабая связность

В неориентированном графе две вершины либо связаны (если существует со­единяющая их цепь), либо не связаны. В ориентированном графе отношение связанности вершин несимметрично, а потому определение связности отличает­ся.

Пусть G (V, Е) — орграф, v ₁и v ₂ — его вершины. Говорят, что две вершины v ₁и v ₂ сильно связаны в орграфе G, если существует путь (ориентированная цепь) из v ₁в v ₂и из v₂ в v ₁. Говорят, что две вершины v₁ и v ₂ односторонне связаны в орграфе G, если существует путь либо из v ₁в v₂, либо из v₂ в v ₁. Говорят, что две вершины v ₁и v ₂ слабо связаны в орграфе G, если они связаны в графе G', полученном из G отменой ориентации ребер. Если все вершины в орграфе силь­но (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабо) связным. Сильная связность влечет одностороннюю связность, которая влечет слабую связность. Обратное неверно.

Компоненты сильной связности

Компоненты сильной связности (КСС) орграфа G — это его максимальные сильно связные подграфы.

Каждая вершина орграфа принадлежит только одной КСС. Если вершина не связана с другими, то считаем, что она сама образует КСС. Конденсацией G* орграфа G (или графом Герца, или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой КСС орграфа G.

Пример

На рис. 6.3 показаны диаграммы орграфа и его конденсации.

Рис. 6.3 Орграф (слева) и его фактор-граф (справа)

Дата добавления: 2014-12-27