Цитирую свою любимую книжку по алгоритмам( "Алгоритмы: построение и анализ" ) :
Цитата:
|
Пусть G = (V,E) -- связный неориентированный граф. Точка раздела ( articulation point ) графа G -- это вершина, при удалении которой граф G перестаёт быть связанным. Мост ( bridge ) -- это ребро с аналогичным свойством. Двусвязная компонента ( biconnected component ) -- это максимальный набор рёбр, любые два ребра которого принадлежат общему простому циклу( см. картинку ). Точки раздела, мосты и двусвязные компоненты можно найти с помощью поиска в глубину.
|
Так как у меня нет сканнера я нарисовал картинку в Paint`е --
http://ivank.hut.ru/pictures/biconnected_component.gif.
Точки раздела и мосты изображены тёмно серым. Двусвязные компоненты -- наборы рёбер в пределах одной серой области ( внутри которой указан номер двусвязной компоненты ).
