пользователей: 21212
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


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

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

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

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

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

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

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

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

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


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