_113. Достижимость и связность

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

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

Определение. Псевдографом D(V, X), Ассоциированным с ориентированным псевдографом, называется псевдограф G(V, X0) в котором Х0 получается из Х заменой всех упорядоченных пар (V, W) на неупорядоченные пары (V, W).

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

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