пользователей: 25056
предметов: 11209
вопросов: 199415
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Связность графа. Компоненты связности графа и число связности. Компоненты сильной связности и число сильной связности орграфа.

Вершины v1 и v2 связны, если в граф существует путь из v1 в v2

Неориентированный граф связный, когда любые две его вершины связны

Ориентированный граф связный, если связен соответствующий ему неориентированный граф

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Число связности графа - колличество компонентов связности

Граф сильно связный, если между каждой парой вершин есть направленный путь

Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. (Орграф называется сильно связным , если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.)

Число сильной связности орграфа - колличество компонентов  сильной связности связности


08.06.2014; 12:56
хиты: 311
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2017. All Rights Reserved. помощь