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]