Související graf

V teorii grafů se říká , že neřízený graf je spojen, pokud je v jednom kuse.

Definice

Undirected graf je řekl, aby byl připojen , pokud bez ohledu na vrcholy a ze existuje řetěz spojující se . $G = (S, A)$ $u$ $proti$ $S$ $u$ $proti$

Připojená součást tohoto grafu je maximální připojený podgraf libovolného neorientovaného grafu.

U směrovaného grafu říkáme, že je:

slabé konektivity, pokud, zapomeneme-li na orientaci hran, je graf připojen;
z jednostranné spojitosti existuje nějaká dvojice vrcholů (u, v) , existuje orientovaná cesta procházející od u do v nebo od v do u ;
ze silného připojení v případě, že existuje cestu orientovaný z nějakého vrcholu u do nějakého vrcholu V .

Vlastnosti

Připojená součást grafu je připojený podgraf tohoto grafu.
Graf, jehož všechny připojené komponenty jsou stromy, je les.
Odpojený strom je les.
Připojený vrchol má alespoň okraje. $ne$ $n-1$
Připojený vrcholný graf, který má přesně hrany, je strom . $ne$ $n-1$
Vrcholový graf s připojenými komponentami má alespoň hrany. $ne$ $k$ $nk$

Algoritmy

V hloubky algoritmus průchod umožňuje zjistit, zda je graf, připojený, nebo ne. V případě přírůstkově konstruovaného grafu můžeme použít algoritmy připojení založené na ukazatelích k určení, zda jsou dva vrcholy ve stejné připojené komponentě.

Teoretická složitost

Zajímá nás, zda je připojen neorientovaný graf. Již v roce 1979 jsme věděli, že je v pravděpodobnostní třídě v logaritmickém prostoru. Reingold v článku z roku 2008 prokázal, že problém s přístupností v neorientovaném grafu je v prostředí LOGSPACE, takže znalost, zda je graf připojen, je také v prostředí LOGSPACE. Když graf prezentujeme jako unii cyklů, problém je NC 1 - kompletní.

Poznámky a odkazy

Romas Aleliunas , Richard M. Karp , Richard J. Lipton a Laszlo Lovasz , „ Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems “, Proceedings of the 20. Annual Symposium on Foundations of Computer Science , IEEE Computer Society, sFCS '79,1979, str. 218–223 ( DOI 10.1109 / SFCS.1979.34 , číst online , přistupováno 30. května 2019 )
Omer Reingold , „ Neusměrněná konektivita v logovém prostoru, “ Journal of the ACM , vol. 55, n O 4,2008, str. 1–24 ( číst online )
Stephen A Cook a Pierre McKenzie , „ Kompletní problémy deterministického logaritmického prostoru, “ Journal of Algorithms , sv. 8, n o 3,1 st 09. 1987, str. 385–394 ( ISSN 0196-6774 , DOI 10.1016 / 0196-6774 (87) 90018-6 , číst online , přistupováno 30. května 2019 )