Свързана графика изключен графиката свързан свойства съставни
Ненасочена графика се счита свързан ако всеки връх е пътят към друга възлова точка (пътека може да се състои от всякакъв брой ръбове). Пример: на фигурата по-долу графика е свързан. Въпреки това, да речем, ако изтриете ръб между върховете 4 и 5, а след това няма да има връзка - от топ 5 няма да може да стигне до всеки друг връх.
Ако свързан имотът не се извършва, графика се нарича свързан.
Освен това, ние не смятаме, че мултиграф, т.е. графики, в които два върха са свързани с два или повече ребра. Ние ограничават графиките за анализ, в който всяка двойка върхове или не са свързани или е свързан с един ръб.
Графика с п върховете е свързан, трябва да има най-малко (п-1) краища.
Ако графиката има най-малко (п * п - 3N + 4) / 2 ръбове, е гарантирано да бъдат съгласувани.
Ако графиката е свързан, е необходимо да има връх поне 2 градуса, т.е. върхове, всяка от които има най-малко два съседни върха.
Ако графиката е свързан и без цикли (т.е., дърво), отстраняването на който и да е край ще доведе до загуба на свързаност.
Disconnected графика се състои от свързани компоненти. Connected компонент - снимачната площадка на върха, така че всеки връх на този комплект е начинът на друг връх от този набор, но нито един от които в началото на тази серия не могат да влязат в връх извън този набор. Очевидно е, че сумата от броя на върховете на свързани компоненти е равен на броя на върховете.
Фигура показва графиката с две свързани компоненти.
Имайте предвид, че свързан компонент може да се състои от един връх. Ако броят на н върховете на, тя може да се състои от повече от п свързани компоненти. В свързан графика свързан компонент само.
Във всеки изключен графика свързан компонент не е повече от п -1 възли. Ако знаете, че граф к свързани компоненти, след това дава още по-строга оценка: всеки свързан компонент се състои от не повече от н-к +1 върхове.
Ако изключен графика к свързани компоненти, за да се получи свързания графика за увеличаване на графиката на поне к -1 ребро.
Как да се определи дали даден свързан граф?
Изберете връх А и да го маркирате като посети (1), съответно, а останалите разчитат все още не е посетил (0):
А, че текущата връх. След това се процедира, както следва. Маркиране непосетени съседни върха: за текущата върха търси в непосредствена близост до него, все още не е непосещавани, и ги маркира като посещаваната.
Да предположим, че се обърна novopomechennyh к върхове (показва точно над тяхната 3). От своя страна избира един от тях ток и рекурсивно Извършваме маркирани непосещавани връх в непосредствена близост до него. За текущия възел не извършва рекурсия, ако това не е връх съседните върхове, които все още не са маркирани като посещаваната.
Ако след тези действия всички върховете ще бъдат маркирани като посещаваният, графиката е свързан, или изключен.
Нека разгледаме един малък пример:
Тук в горната част на естествено число е това, което го ред е маркиран като посети, броят на зелен цвят означава, че рекурсивни обаждането е направено за тази среща на високо равнище.
Изберете връх (1). Освен отбелязани три върха, съседни на него (2, 3, 4). Сега тя се превръща в текущия възел (2). Рекурсия: етикет двата а не са посетили съседни върха (цифри 5 и 6). Да (5), рекурсия не е необходима - тя няма непосетени съседни върха, за е необходима (6) рекурсия: отбелязваме на номер 7. 7 числа все още не са посетени от "съсед" - броят 8, и тук, в номер 8 не непосетени съседни върха. Всички рекурсивни повиквания, генерирани от върха (2) е завършено. Сега на върха на опашката (3), но не е необходимо рекурсия. Ляв връх (4). Един от нейните съседни върхове (9) не е маркирано, ние го оправя. Общо:
Заключение: не всички от върха посети Ърл появи непоследователен.
Свързани статии