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

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

Определение. Неориентированный граф G связен, если существует хотя бы один маршрут в G между каждой парой вершин i и j.

Определение. Подграфом графа G(V,E) называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат E(G).

Определение. Максимальный связный подграф графа G называется связной компонентой графа G. Замечание: Максимальный не в смысле количества ребер, а в смысле нерасширяемости.

Например, на рисунке 19 изображен несвязный граф с тремя компонентами связности.

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

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

Определение. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один путь из i в j и по крайней мере один путь из j в i.

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

На рисунках 20 – 222 изображены несвязный, связный, но не сильно и сильносвязный графы соответственно.

Циклы

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