Типы связности графа

Вершина v графа G достижима из вершины u, если существует (u, v)- маршрут в G, соответственно вершина u – контрдостижима для вершины v. Любая вершина считается достижима для самой себя.

Вершины v и u графа G – взаимнодостижимы, если вершина v достижима для вершины u, и вершина u достижима для вершины v.

Орграф G – сильносвязный (сильный), еслилюбые две вершины в нём взаимнодостижимы.

Орграф G – одностороннесвязный (односторонний), если для каждой пары его вершин, по крайней мере, одна достижима из другой.

Орграф G – слабосвязный (слабый), если любые две его вершины соединены полумаршрутом (полупутем).

Орграф G – несвязен, если несвязно его основание.

Сильная компонента – максимальный относительно включения сильный подграф исходного орграфа.

Односторонняя компонента – максимальный относительно включения односторонний подграф исходного орграфа.

Слабая компонента – максимальный относительно включения слабый подграф исходного орграфа.

Например:

			Слабый орграф

Остовный маршрут – маршрут, содержащий все вершины исходного графа.