Техники за програмиране
Задача 8. Търсене на двойно свързани компоненти и артикулационни точки
Главна информация
Задачата е задължителна за желаещите да получат оценка „отличен“.
Компонентна свързаност на неориентирана графика имаме предвид всеки максимално свързан подграф на тази графика. Тази дефиниция може да бъде преформулирана, както следва: свързан компонент е такъв подграф, че за всеки връх u от този подграф всички върхове, към които има път от u в оригиналната графика, принадлежат към същия подграф. Фигурата показва графика с два свързани компонента.
Ще извикаме някакъв връх на неориентиран граф артикулационна точка, ако след отстраняването му и всички падащи към него ръбове броят на свързаните компоненти се увеличи в графиката. Еквивалентна дефиниция е следната: връх u е точка на артикулация, ако и само ако графиката съдържа два върха v и w, различни от u и принадлежащи към един и същ свързан компонент, така че всеки път от v до w преминава през u .
Ще извикаме графиката двойно свързани, ако не съдържа артикулационни точки. Ще бъде извикан всеки максимален двойно свързан подграф на графика двойно свързан компонент. С други думи, двойно свързан компонент на графика е всеки от нейните подграфи, при който премахването на произволен връх и ръбове, падащи на него, не води до загуба на свързаност на този подграф и към този подграф не може да се добави връх като запазва това свойство. На фигурата графиката подчертава артикулационните точки (върхове 2 и 4) и показва двойно свързани компоненти (,).
Имайте предвид, че всеки два различни двойно свързани компонента или нямат общи върхове, или имат един общ връх, който е точката на артикулация.
Формулираме без доказателство следната теорема.
Теорема. Нека D е обхващащо дърво (скелет) на неориентирана свързана графика G, конструирана чрез първоначално търсене в дълбочина от върха r. Върхът v е точка на свързване на графика G тогава и само ако:
- или v = r и r има поне двама синове в дървото D,
- или v не е равно на r и върхът v има син w в дървото D, така че нито w, нито който и да е от неговите потомци в дървото D са свързани чрез ръб с който и да е предшественик на върха v в D .
Нека променим процедурата за обхождане на графиката в дълбочина, като добавим към нея изчислението на два масива: int номер [N] и int L [N], където N е броят на върховете на графиката. За всеки връх v, в число [v] ще съхраним номера на този връх в реда на преминаване на графиката в дълбочина, а в L [v] ще напишем числото номер [w], където w е върхът, който е свързан чрез заден ръб към v или някои от потомците на v в обхващащото дърво и има минимално възможното числово число или число [v], ако не може да бъде намерен такъв връх w. Спомнете си, че назад ръбове имаме предвид ръбове, които не са включени в скелета на графиката, конструирани чрез ходене в дълбочина.