Намиране на двойно свързани компоненти (блокове) на графика
Ако свързаната графика съдържа два върха u1 и u2 такива, че всяка пътека между тях ще премине през върха v, след това отгоре v ще бъде извикан артикулационна точка.
Може да се даде еквивалентна дефиниция на артикулационната точка.
Върх v броя G = извикан артикулационна точка, ако премахването на този връх и всички изходящи от него ръбове води до увеличаване на свързаните компоненти на графиката.
Ако в свързана (състояща се от един свързан компонент) графика няма артикулационни точки, тя е двойно свързана.
Всякакви максимум двойно свързан подграф на графика G Наречен двойно свързан компонентили блок тази графика (фиг. 8.17).
Фигура: 8.17. Блокове на графика G
Въпрос 1. Какво ще бъде пресечната точка на два различни блока на графиката?
Въпрос 2. Какво се случва с блок, ако към него прикачите ръб на графика, който има обща точка с блока и не принадлежи на блока?
Двойно свързаната графика е много полезно свойство за някои приложни проблеми.
Нека си представим, че върховете на графиката са телеграфни станции; ребрата са далекопроводи. Да предположим, че една от станциите не работи. Ако графиката е свързана двойно, тогава останалите две станции ще останат свързани.
За много задачи е важно да знаете блоковете на графиката. Например, намерете всички елементарни цикли на графика G може да бъде отделно за всеки блок на графиката G.
Намирането на артикулационни точки и блокове на графика е класически проблем. Ще търсим артикулационни точки, като обхождаме всички върхове на графиката, като използваме метода за първо търсене в дълбочина. Ние не само ще заобиколим върховете на графиката, но и ще изградим нейния скелет.
Когато се конструира телена рамка с първо търсене на дълбочина за два върха u и v, свързан с ръб, винаги е известен със сигурност: или u - потомък v, или обратно. Как да разпознаем артикулационната точка с, ако рамката вече е изградена д броя G?
Тук критерий за артикулация:
- или това е корен, в който има поне двама сина д;
- или в горната част с има поне един син u такъв, че нито той, нито неговите потомци са свързани чрез акорди с предци с.
Помислете за фиг. 8.18. Числа на върховете - числа, които се получават от върховете на графиката по време на изграждането на каркаса. Нека покажем, че върхът с удовлетворява второто условие на критерия.
Чрез изграждане на рамката с има син 3 и потомък 4. Предшественик с - връх к. Син 3 и неговият потомък 4 не са свързани чрез акорди с к. така, с - артикулационна точка и графика G има първи блок = s–3, 3-4, с–4>.
Фигура: 8.18. Артикулационни точки
Въпрос 3. С кой връх трябва да се свърже връх 4, така че графиката G стана двойно свързан?
Върх к - точката на артикулация, тъй като това е корен, който има двама синове: с и 5. Следователно графиката G има втори блок = и трети блок = .
Познавайки критерия на артикулационната точка, ние описваме алгоритъма за намиране на тези точки.
Нека алгоритъмът за първо търсене в дълбочина изгради каркаса д броя G. За всеки връх v ще изчислим две стойности: GLN[v] и МИН[v].
GLN[v] - само числото, което връхът получава при изграждането на каркаса. Например за корена GLN[к] = 1.