Графична свързаност - Studiopedia
Концепцията за път в графика генерирарелация на достижимост : връхuе достижим от връхv, ако има път отvдоu. Обозначение:v#u. Отношението на достижимост е рефлексивното и транзитивно затваряне на релацията на съседство на върховете. Лесно е да се провери, че за графите достижимостта е релация на еквивалентност (но не и за диграфите!). Следователно релацията # разделя множеството от върхове на графа на класове на еквивалентност – взаимно достъпни върхове, които се наричат свързани компоненти на графа. Граф с един свързан компонент се наричаедносвързан.
За диграфите релацията на достижимост # е най-общо казано нерефлексивна и несиметрична, така че няма единно понятие за свързаност за диграфи.
Свързана графа (с диграф) е графика, получена от даден диграф чрез замяна на стрелки върху линия.
1.Disconnected е диграф, чиято свързана графа е несвързана.
2.Слабо свързан е диграф, чиято свързана графа е свързана.
3.Еднопосочно свързан (или полусвързан) орграф е орграф, в който за всички върхове u, v, u # v или v #u е изпълнено.
4.Силно свързан е орграф, в който u # v и v #u са валидни за всякакви върхове u, v.
Очевидно, 4.U 3. U2.U1.
Максимално силно свързан подграф се нарича силно свързан компонент. Всеки връх принадлежи само на един силно свързан компонент - следователно силната връзка е релация на еквивалентност. Фактор-множеството от върхове по тази връзка е множеството от силно свързани компоненти. Всеки такъв компонент може да бъде свързан с друг чрез стрелки,непременно сочещи в същата посока. Представянето на свързани компоненти под формата на върхове и стрелки, които ги свързват, се наричакондензационен граф на дадения орграф (в този случай множество стрелки могат да бъдат премахнати, оставяйки само по една).
Примери
Не намерихте това, което търсихте? Използвайте търсачката:
Деактивирайте adBlock! и обновете страницата (F5)наистина е необходимо