Артикулационни върхове и ребра

Тези понятия възникват единствено в неориентираните графи.

Определение: Артикулационно ребро е такова ребро на графа, при чието премахване графът увеличава броя на свързаните си компоненти.

Наричат се още мостове, поради житейската аналогия. Най-често в тази ситуация разглеждаме свързани графи, при които премахването на мост, прави графа несвързан (...). Графът от примера има само едно артикулационно ребро - $(3,4)$. По аналогичен начин се дефинира артикулационен връх.

Определение: Артикулационен връх е такъв връх на графа, при чието премахване (заедно с неговите ребра) графът увеличава броя на свързаните си компоненти.

Наричат се още артикулационни точки.

Двете понятия имат някаква връзка помежду си. Нека имаме артикулационното ребро $(u,v)$. В повечето случаи поне един от краищата му $u$ и/или $v$ ще е артикулационен връх. Това означава, че от мостовете по принцип получаваме артикулационни върхове. Обратната посока - от артикулационна точка да следва мост, се случва по-рядко. Показан е пример, където връх 3 е артикулационна точка, но никое ребро не е мост - при премахването на което и да е ребро, графът остава свързан.

Оказва се, че тези специални компоненти на графа са полезни за изучаване. За самата свързаност на графа също е важно да се знае наличието на артикулационните върхове и ребра. В следващата точка ще разгледаме най-популярният и бърз алгоритъм за намирането им, а последно ще покажем едно тяхно приложение.

Първо ще опишем алгоритъма за намиране на мостове, а от там лесно се получава и алгоритъм за намиране на артикулационните точки. Понятието, което разгледахме, беше общо - дори и за несвързани графи. Ясно е, че за намиране на всички мостове трябва да разглеждаме всяка компонента на свързаност по отделно, така че нека БОО (...) приемем, че графът е свързан. Често, когато сме в неориентирани графи е полезно да разгледаме покриващо дърво на графа. Такъв е и случаят сега. Както знаем от темата за дървета, при намиране на покриващо дърво, ребрата на оригиналния неориентиран граф се разделят на две групи - дървесни ребра и обратни ребра. Нека първо разгледаме обратните ребра. Лесно се вижда, че те няма как да са мостове - при премахването на кое и да е от тях, графът остава свързан, защото все още разпологаме с цялото покриващо дърво. Така получаваме, че единствено дървесните ребра са кандидати за мостове. От това следва, че мостовете на един свързан граф са най-много $n-1$, като при граф, който е дърво, се достига точно тази бройка.

Сега остава да намерим хубаво условие за определяне дали дадено дървесно ребро $(x,y)$ е мост (да кажем, че $x$ е баща на $y$ в дървото). Нека си представим какво се случва, когато се премахне това ребро. Графът се разпада на потенциално две свързани компоненти - поддървото на връх $y$ и останалата част (всичко от връх $x$ нагоре и настрани). Ясно е, че поддървото си остава свързано, както и другата част остава свързана, заради наличието на останалите ребра от покриващото дърво. Така единствено трябва да установим дали двете части не остават свързани. Но тази свързаност може да се получи единствено от обратно ребро, насочено от поддървото на връх $y$ към горната част над $y$. Наистина, ако няма такова ребро, то няма как от поддървото да стигнем някъде по-нагоре от $y$. Така получаваме следното условие. Едно ребро $(x,y)$ е мост $\iff$ всички обратни ребра в поддървото на $y$ остават в това поддърво (не достигат връх $x$ и нагоре).

Лесно можем за поддървото на връх $y$ да разберем дали обратните ребра остават в поддървото. Нека разгледаме $in$-времената на краищата на обратните ребра. Ако няма обратно ребро, така че края му да има $in$-време, по-малко от това на връх $y$, то всички обратни ребра остават в поддървото. Така ако намерим минималното $in$-време от краищата на обратните ребра, то реброто ще е мост ако тази стойност е $\ge$ от $in$-времето на $y$. В противен случай, имаме ребро, което се качва над $y$ и така със сигурност фиксираното ребро $(x,y)$ не е мост. По този начин можем да формулираме лесен линеен алгоритъм по графа за намиране на мостовете, който всъщност е открит за първи път от Таржан. Цялото намиране се осъществява с един DFS, в който едновременно строим покриващо дърво и извършваме малко допълнителна работа за откриване на мостовете. Поддържаме два допълнителни масива - $in$ и $up$, съответно за $in$-времената на върховете и за минималното $in$-време на връх в поддървото. За всеки връх $x$, стойността на $up[x]$ намираме като минимума от $in[x]$ и следните стойности от последователното обхождане на съседите на връх $x$:

за необходен съсед $y$ (т.е. край на дървесно ребро) гледаме $in[y]$
за обходен съсед $y$, който не е бащата на върха (т.е. e начало или край на обратно ребро), гледаме $up[y]$

От вече казаното, дървесното ребро $(x,y)$ е мост $\iff$ $up[y] \ge in[y]$. Следва реализация на описания алгоритъм:

Тук е показан интерактивeн пример на алгоритъма. Анимацията се пуска с бутона "Старт", като може да зададете от кой връх да започва обхождането (и съответно да е корен на покриващото дървото). Преди да започне анимацията, графът се пренарежда, така че да съответства на покриващото дърво, като съответно обратните ребра са изобразени с пунктир. Също така, преди натискане на "Старт", може да задавате ускорение от 1 до 9, а по време на анимацията да превъртате на предишна или следваща стъпка.

Начален връх:

Описаният алгоритъм има един пропуск единствено, когато имаме мултиграф. Нека например разглеждаме граф, който се състои само от две мултиребра $(1,2)$ и коренът на покриващото дърво е връх 1. В този граф е ясно, че няма нито един мост, но алгоритъмът ще каже, че едно от двете ребра е мост. Това се получава, защото той приема, че когато види ребро на връх, което сочи баща му, то това ребро е дървесно, а при мултиграф това не е винаги вярно. Затова, когато приключим с връх 2, ще имаме $up[2]=in[2]$, а правилното е $up[2]=in[1]$ (...). Най-добрият начин да отстраним този проблем е параметърът на DFS, който отразява бащата, да е всъщност номерът на дървесното ребро и така, като сме на връх 2 ще отчетем едното ребро, че е обратно, а другото, че е дървесно.

Последно ще коментираме как намираме артикулационните върхове на граф, което е до голяма степен аналогично на мостовете. Отново това става с модификация на обхождането в дълбочина. Сега трябва да си представим какво става с графа, когато премахнем един връх $x$. Отново всичко, което е нагоре и настрани от $x$ е потенциална нова свързана компонента, като сега и всички поддървета на децата на $x$ са потенциални нови свързани компоненти. Заради свойствата на покриващото дърво, което се получава от DFS, то тези поддървета имат обратни ребра, които сочат нагоре, т.е. няма как да свързват поддърветата. Затова единственият шанс всичко да остане свързано е всяко поддърво да има обратно ребро, което да сочи нагоре от връх $x$. Ако приемем, че отново смятаме същите масиви $in$ и $up$ за всеки връх, то един връх $x$ е артикулационна точка $\iff$ има дете $y$, за което $up[y] \ge in[x]$. Ето код за този алгоритъм:

Може да бъде забелязан един частен случай - когато сме на корена. Проблемът с корена е, че досега логиката ни търсеше обратни ребра, които да отиват над текущия връх, за да са свързани с горната част, но при махането на коренът няма такава част. Лесно може да се види, че коренът е артикулационна точка, тогава и само тогава, когато има повече от едно дете. Това в програмата се проверява с $flag$ - за всяко дете на корена, нашата проверка за артикулационност е в сила (...) и така реално се броят децата. Двата показани алгоритъма са със сложност $O(n+m)$.

Първоначално говорихме, че един граф е свързан, ако всеки два върха в него са свързани. Това определение естествено може да се продължи, за да характеризира "по-силна" свързаност. Единият начин е да искаме върховете да останат свързани дори и точно един от върховете да бъдат изтрити.

Определение: Граф наричаме двусвързан $\iff$ при премахването, на който и да е връх, всеки два от останалите върхове остават свързани.

Очевидно, за да може един граф да е двусвързан, той първо трябва да е (едно)свързан. В контекста на свързаност говорим за свързани компоненти. Тук аналогично можем да говорим за двусвързани компоненти, макар и да нямаме точно разпадане на компоненти.

Определение: Двусвързани компоненти на граф наричаме максималните по включване подграфи на началния граф, така че всеки подграф да е двусвързан.

Проблемът е, че за разлика от свързаните компоненти, които нямат общо помежду си, то двусвързаните могат да имат по един общ връх. Лесно може да се покаже, че всъщност общите върхове са точно артикулационните точки на графа. Показан е началният пример, в който са оцветени компонентите в пурпурен и жълт цвят, а общият връх (артикулационна точка) е в смесения цвят на двата - червен. Самото разбиване има хубави свойства. По аналогия на ССК (...) можем да направим кондензиран граф с върхове тези компоненти, както и по един връх за всяка артикулационна точка, а ребрата са между връх на кондензирана двусвързана компонента и връх за артикулационна точка от тази компонента. Полученият кондензиран граф всъщност винаги е дърво. За нашето разглеждане, по-важни са друг вид подобни на двусвързаните компоненти, които ще разглеждаме в малко по-големи детайли в следващите абзаци.

Започнахме разглеждането с това, че единият начин да усилим свързаността, е като искаме свързаност при премахването на един връх. Вторият начин е ако искаме свързаност при махането, на което и да е ребро. Така имаме аналогични понятия на предните:

Определения:

Граф наричаме двойно свързан $\iff$ при премахването, на което и да е ребро, всеки два от върховете остават свързани.
Двойно свързани компоненти на граф наричаме максималните по включване подграфи на началния граф, така че всеки подграф да е двойно свързан.

Отново, за да може един граф да е двойно свързан, трябва да е поне свързан. По аналогия със съкращението ССК, тези компоненти ще наричаме ДСК (Двойно Свързани Компоненти) (...). При тези компоненти имаме хубавото разпадане, при което те нямат общи върхове и ребра. Всъщност ДСК се получават и много по-лесно. Достатъчно е първо да намерим всички мостове на графа, след което да премахнем намерените мостове. Така получените свързани компоненти са всъщност двойно свързаните на оригиналния граф. Лесно се вижда, че това е така - ако премахнем някое ребро от тези компоненти, то те остават свързани, защото иначе махнатото ребро би било мост, а ние махнахме всички мостове, за да ги образуваме. Показан е интерактивен пример, за който двойно свързаните компоненти се поддържат оцветени, както и мостовете.

Самите двойно свързани компенти са свързани чрез мостовете на графа. Тук директно можем да кондензираме компонентите и отново кондензирания граф се получава дърво, който факт лесно може да се докаже. Последно, ще кажем един полезен факт за двойно свързаните компоненти - за всеки два върха в една двойно свързана компонента има поне два прости пътя между тях без общи ребра. Понеже графът е неориентиран, това означава, че и всеки два върха в ДСК участват в прост цикъл. Това свойство е много силно, защото лесно се вижда, че то е и достатъчно условие дадена компонента да е двойно свързана.