3-связность - Большая Энциклопедия Нефти и Газа, статья, страница 1
Когда к тебе обращаются с просьбой "Скажи мне, только честно...", с ужасом понимаешь, что сейчас, скорее всего, тебе придется много врать. Законы Мерфи (еще...)

3-связность

Cтраница 1


В силу 3-связности компонента определяется единственным образом. Алгоритм, описанный в разд. О ( V - log V), используется далее для нахождения классов эквивалентности изоморфных 3-лепестков.  [1]

Алгоритм определения 3-связности графа G требует 0 ( F, E) действий.  [2]

Опишем в этом разделе алгоритм определения 3-связности графа G, который требует 0 ( V, E) действий. Ранее известные алгоритмы требуют большего количества действий, например алгоритм, предложенный в работе ( Ариеси, Си-ракано, Хироси [1971]), характеризуется 0 ( У4) действиями. Если использовать определение 3-связной компоненты, которое дано Таттом ( см. Татт J1966 ]), или другое аналогичное определение, то предлагаемый здесь алгоритм позволяет разбить граф на 3-связные компоненты за 0 ( V, E) действий. Определение Татта обладает тем преимуществом, что разбиение графа на 3-связные компоненты единственно; единственность разбиения существенным образом используется для решения задачи об изоморфизме нланарных графов.  [3]



Страницы:      1