1.4. Связность. Компоненты связности

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

Подграф называется Собственным, если он отличен от самого графа.

Говорят, что Вершина W ориентированного графа D (графа G) Достижима Из вершины V, если либо W=V, либо существует путь (маршрут) из V в W.

Граф (ориентированный граф) называется Связным (Сильно связным), если для любых двух его вершин V, W существует маршрут (путь), соединяющий V и W.

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

< Предыдущая		Следующая >