Знайте, Intuit, лекция, презентация на графики, достижимост и свързаност

достъпност графика

Един от първите въпроси, които възникват при изучаването на графики. това е въпрос на съществуването на определените маршрути между някои или всички двойки върхове. Отговорът на въпросите на - съотношението достъпност въведени по-горе по върховете на графиката G = (V, E). w връх е достъпен от връх V. ако V = W или G е път от V до вата С други думи, съотношението на постижимост е възвратен и преходен затваряне на връзката Е. За неориентирани графа, това съотношение е симетрична, и следователно е връзка еквивалентност на връх набор V. в ненасочена графика относителна постижимост на класове еквивалентност се наричат ​​свързаните компоненти. За ориентирани графики постижимо. най-общо казано, това не трябва да бъде симетричен връзка. Symmetrical е взаимно достъпни.

Определение 9.8. Върхове V и W насочено графика G = (V, E), наречена взаимно постижима, ако има път в G от V до w и w по пътя от с.

Ясно е, че отношението на взаимна достижимост е рефлексивен. преходен и симетричен, а оттам и за еквивалентността набор от върховете. Класовете на еквивалентността по отношение на взаимното достижимост нарича силно свързани компоненти или двойно-свързани компоненти на графиката.

Нека първо да разгледаме въпроса за изграждане на връзка достъпност. Определяне на всяка графика си достъпност графика (също понякога се нарича графика затваряне преходен), краищата на които съответстват на пътеки на оригиналния графиката.

Определение 9.9. Нека G = (V, E) - целеви графика. Достъпност графика G * = (V, E *) за G има същия набор от върховете V и следващия набор от ръбове E * =<(u, v) | в графе G вершина v достижима из вершины u> .

Пример 9.3. Разглеждане на графика Г от Пример 9.2.