Konektivita (teorie grafů) - Connectivity (graph theory)
 | Bylo navrženo, že Hra Meshulam být sloučeny do tohoto článku. (Diskutujte) Navrhováno od července 2020. |
v matematika a počítačová věda, připojení je jedním ze základních konceptů teorie grafů: žádá o minimální počet prvků (uzly nebo hrany), které je třeba odstranit, aby se zbývající uzly oddělily izolované podgrafy.[1] Úzce to souvisí s teorií tok sítě problémy. Konektivita grafu je důležitým měřítkem jeho odolnosti jako sítě.
Propojené vrcholy a grafy
V neorientovaný graf G, dva vrcholy u a proti jsou nazývány připojeno -li G obsahuje a cesta z u na proti. Jinak se jim říká odpojen. Pokud jsou dva vrcholy navíc spojeny cestou délky 1, tj. jedinou hranou, se vrcholy nazývají přilehlý.
A graf se říká, že je připojeno pokud je každá dvojice vrcholů v grafu spojena. To znamená, že existuje cesta mezi každou dvojicí vrcholů. Volá se neorientovaný graf, který není připojen odpojen. Neorientovaný graf G je proto odpojen, pokud v něm existují dva vrcholy G tak, že žádná cesta dovnitř G má tyto vrcholy jako koncové body. Je připojen graf s pouze jedním vrcholem. An bez hran graf se dvěma nebo více vrcholy je odpojen.
A řízený graf je nazýván slabě připojen pokud nahradíte všechny jeho směrované hrany neorientovanými hranami, vytvoří se propojený (neorientovaný) graf. to je jednostranně připojeno nebo jednostranný (také nazývaný částečně propojený) pokud obsahuje směrovanou cestu z u na proti nebo směrovaná cesta z proti na u pro každý pár vrcholů u, v.[2] to je silně propojený, nebo jednoduše silný, pokud obsahuje směrovanou cestu z u na proti a směrovaná cesta z proti na u pro každý pár vrcholů u, v.
Součásti a řezy
A připojená součást je maximální připojený podgraf neorientovaného grafu. Každý vrchol patří přesně jedné připojené součásti, stejně jako každá hrana. Graf je připojen, právě když má právě jednu připojenou komponentu.
The silné komponenty jsou maximální silně spojené podgrafy směrovaného grafu.
A vrchol řez nebo oddělovací sada připojeného grafu G je sada vrcholů, jejichž odstranění se vykreslí G odpojen. The konektivita vrcholů κ(G) (kde G není kompletní graf ) je velikost minimálního řezu vrcholů. Nazývá se graf k-vertex-connected nebo k-připojeno pokud je jeho vrcholní konektivita k nebo vyšší.
Přesněji řečeno, jakýkoli graf G (úplné nebo ne) se říká, že je k-vertex-connected pokud obsahuje alespoň k+1 vrcholy, ale neobsahuje sadu k − 1 vrcholy, jejichž odstranění odpojí graf; a κ(G) je definována jako největší k takhle G je k-připojeno. Zejména a kompletní graf s n vrcholy, označené K.n, nemá vůbec žádné řezy vrcholů, ale κ(K.n) = n − 1.
A vrchol řez pro dva vrcholy u a proti je sada vrcholů, jejichž odstranění z grafu se odpojí u a proti. The místní připojení κ(u, proti) je velikost nejmenšího řezu oddělujícího vrchol u a proti. Místní připojení je u neorientovaných grafů symetrické; to je κ(u, proti) = κ(proti, u). Kromě kompletních grafů κ(G) se rovná minimu κ(u, proti) přes všechny nesousedící páry vrcholů u, v.
2-konektivita se také nazývá biconnectivity a 3-konektivita se také nazývá trikonektivita. Graf G který je připojen, ale ne 2-connected se někdy nazývá oddělitelný.
Analogické koncepty lze definovat pro hrany. V jednoduchém případě, kdy řezání jedné konkrétní hrany by odpojilo graf, se tato hrana nazývá a most. Obecněji řečeno, řez hrany G je sada hran, jejichž odstranění způsobí odpojení grafu. The okrajová konektivita λ(G) je velikost nejmenšího řezu hrany a místní konektivita hran λ(u, proti) dvou vrcholů u, v je velikost nejmenšího rozpojeného okraje u z proti. Lokální konektivita hran je opět symetrická. Nazývá se graf k- připojený k okraji pokud je jeho okrajová konektivita k nebo vyšší.
Říká se, že je graf maximálně propojený pokud se jeho konektivita rovná jeho minimálnímu stupni. Říká se, že je graf maximálně spojené s hranou pokud se jeho okrajová konektivita rovná jeho minimálnímu stupni.[3]
Super- a hyperkonektivita
Říká se, že je graf super propojený nebo super-κ pokud každý minimální řez vrcholem izoluje vrchol. Říká se, že je graf velmi propojený nebo hyper-κ pokud odstranění každého minimálního řezu vrcholu vytvoří přesně dvě složky, z nichž jedna je izolovaný vrchol. Graf je částečně hyper propojený nebo semi-hyper-κ pokud je minimální řez vrcholem, rozděluje graf přesně na dvě složky.[4]
Přesněji: a G připojený graf se říká, že je super propojený nebo super-κ pokud všechny minimální řezy vrcholů sestávají z vrcholů sousedících s jedním vrcholem (minimálního stupně) G připojený graf se říká, že je připojeno super-hranou nebo super-λ pokud se všechny minimální řezy hran skládají z hran dopadajících na nějaký vrchol (minimálního stupně).[5]
Cutset X z G se nazývá netriviální cutset, pokud X neobsahuje sousedství N (u) jakéhokoli vrcholu u ∉ X. Pak superkonektivita κ1 z G je:
- κ1 (G) = min {| X | : X je netriviální sada}.
Netriviální řez hrany a okrajová superkonektivita λ1 (G) jsou definovány analogicky.[6]
Mengerova věta
Jedním z nejdůležitějších faktů o konektivitě v grafech je Mengerova věta, který charakterizuje konektivitu a konektivitu hrany grafu z hlediska počtu nezávislých cest mezi vrcholy.
Li u a proti jsou vrcholy grafu G, pak sbírka cest mezi u a proti se nazývá nezávislý, pokud žádný z nich nesdílí vrchol (jiný než u a proti oni sami). Podobně je kolekce nezávislá na okraji, pokud žádné dvě cesty v ní nesdílejí hranu. Počet vzájemně nezávislých cest mezi u a proti je psán jako κ ′(u, proti)a počet vzájemně nezávislých cest na hraně u a proti je psán jako λ ′(u, proti).
Mengerova věta tvrdí, že pro odlišné vrcholy u,proti, λ(u, proti) rovná se λ ′(u, proti), a pokud u také nesousedí s proti pak κ(u, proti) rovná se κ ′(u, proti).[7][8] Tato skutečnost je ve skutečnosti zvláštním případem věta o maximálním toku o minimálním řezu.
Výpočtové aspekty
Problém určení, zda jsou dva vrcholy v grafu spojeny, lze efektivně vyřešit pomocí a vyhledávací algoritmus, jako vyhledávání na šířku. Obecněji je snadné výpočetně určit, zda je graf připojen (například pomocí a disjunktně nastavená datová struktura ), nebo spočítat počet připojených komponent. Může být napsán jednoduchý algoritmus pseudo kód jak následuje:
- Začněte v libovolném uzlu grafu, G
- Pokračujte z tohoto uzlu pomocí vyhledávání do hloubky nebo do šířky, přičemž se počítají všechny dosažené uzly.
- Jakmile je graf zcela překročen, je-li počet počítaných uzlů roven počtu uzlů G, graf je spojen; jinak je odpojen.
Podle Mengerovy věty pro libovolné dva vrcholy u a proti v připojeném grafu G, čísla κ(u, proti) a λ(u, proti) lze efektivně určit pomocí maximální průtok min. řez algoritmus. Konektivita a konektivita hranic G pak lze vypočítat jako minimální hodnoty κ(u, proti) a λ(u, proti), resp.
V teorii výpočetní složitosti SL je třída problémů log-space redukovatelné k problému určení, zda jsou dva vrcholy v grafu spojeny, což se ukázalo jako rovné L podle Omer Reingold v roce 2004.[9] Proto může být neorientovaná grafická konektivita vyřešena v O (log n) prostor.
Problém výpočtu pravděpodobnosti, že a Bernoulli náhodný graf je spojen se nazývá spolehlivost sítě a problém výpočtu, zda jsou dva dané vrcholy spojeny, problém spolehlivosti ST. Oba jsou #P -tvrdý.[10]
Počet připojených grafů
Počet odlišných spojených označených grafů s n uzly je uveden v tabulce v On-line encyklopedie celočíselných sekvencí jako sekvence A001187, přes n = 16. Prvních pár netriviálních výrazů je
| n | grafy |
|---|---|
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
Příklady
- Spojení vrcholů a hran odpojeného grafu jsou obě 0.
- 1-konektivita je ekvivalentní konektivitě pro grafy s minimálně 2 vrcholy.
- The kompletní graf na n vrcholy má konektivitu hran rovnou n − 1. Každý další jednoduchý graf n vertices má přísně menší konektivitu hran.
- V strom, místní konektivita hran mezi každou dvojicí vrcholů je 1.
Hranice připojení
- Konektivita vrcholů grafu je menší nebo rovna jeho konektivitě hran. To znamená, κ(G) ≤ λ(G). Oba jsou menší nebo rovny minimální stupeň grafu, protože smazáním všech sousedů vrcholu minimálního stupně se tento vrchol odpojí od zbytku grafu.[1]
- Pro vrchol-tranzitivní graf z stupeň d, my máme: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.[11]
- Pro vrchol-tranzitivní graf z stupeň d ≤ 4, nebo pro jakýkoli (neřízený) minimální Cayleyův graf z stupeň d, nebo pro kohokoli symetrický graf z stupeň d, oba druhy připojení jsou stejné: κ(G) = λ(G) = d.[12]
Další vlastnosti
- Propojenost je zachována homomorfismy grafů.
- Li G je připojen pak jeho hranový graf L(G) je také připojen.
- Graf G je 2- připojený k okraji kdyby a jen kdyby má silně propojenou orientaci.
- Balinskiho věta uvádí, že polytopální graf (1-kostra ) a k-dimenzionální konvexní polytop je kgraf spojený s vrcholem.[13] Steinitz předchozí věta, kterou spojil jakýkoli 3-vrchol rovinný graf je polytopální graf (Steinitzova věta ) dává částečnou konverzaci.
- Podle věty o G. A. Dirac, pokud je graf k-připojeno pro k ≥ 2, pak pro každou sadu k vrcholy v grafu existuje cyklus, který prochází všemi vrcholy v množině.[14][15] Opak je pravdivý, když k = 2.
Viz také
- Algebraická konektivita
- Cheegerova konstanta (teorie grafů)
- Dynamické připojení, Disjunktně nastavená datová struktura
- Expander graf
- Síla grafu
Reference
- ^ A b Diestel, R. (2005). „Teorie grafů, elektronické vydání“. str. 12.
- ^ Kapitola 11: Digrafy: Princip duality pro digrafy: Definice
- ^ Gross, Jonathan L .; Yellen, Jay (2004). Příručka teorie grafů. CRC Press. str.335. ISBN 978-1-58488-090-5.
- ^ Liu, Qinghai; Zhang, Zhao (01.03.2010). „Existence a horní hranice pro dva typy omezeného připojení“. Diskrétní aplikovaná matematika. 158 (5): 516–521. doi:10.1016 / j.dam.2009.10.017.
- ^ Gross, Jonathan L .; Yellen, Jay (2004). Příručka teorie grafů. CRC Press. str.338. ISBN 978-1-58488-090-5.
- ^ Balbuena, Camino; Carmona, Angeles (01.10.2001). "O konektivitě a superkonektivitě bipartitních digrafů a grafů". Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458.
- ^ Gibbons, A. (1985). Algoritmická teorie grafů. Cambridge University Press.
- ^ Nagamochi, H .; Ibaraki, T. (2008). Algoritmické aspekty konektivity grafů. Cambridge University Press.
- ^ Reingold, Omer (2008). Msgstr "Neusměrněné připojení v logovém prostoru". Deník ACM. 55 (4): 1–24. doi:10.1145/1391289.1391291. S2CID 207168478.
- ^ Provan, J. Scott; Ball, Michael O. (1983). "Složitost počítání řezů a výpočtu pravděpodobnosti připojení grafu". SIAM Journal on Computing. 12 (4): 777–788. doi:10.1137/0212053. PAN 0721012..
- ^ Godsil, C.; Royle, G. (2001). Algebraická teorie grafů. Springer Verlag.
- ^ Babai, L. (1996). Automorfické skupiny, izomorfismus, rekonstrukce. Technická zpráva TR-94-10. University of Chicago. Archivovány od originál dne 06.06.2010. Kapitola 27 z Příručka kombinatoriky.
- ^ Balinski, M. L. (1961). "Na struktuře grafu konvexních mnohostěnů v n-prostor". Pacific Journal of Mathematics. 11 (2): 431–434. doi:10.2140 / pjm.1961.11.431.[trvalý mrtvý odkaz ]
- ^ Dirac, Gabriel Andrew (1960). „In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen“. Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002 / mana.19600220107. PAN 0121311..
- ^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). „Zobecnění Diracova věty na cyklech k vrcholy v kpropojené grafy ". Diskrétní matematika. 307 (7–8): 878–884. doi:10.1016 / j.disc.2005.11.052. PAN 2297171..