K-szorosan összefüggő gráf

A matematika, azon belül a gráfelmélet területén G összefüggő gráfot akkor nevezünk k-szorosan összefüggő, k-összefüggő (vagy k-szorosan csúcsösszefüggő) gráfnak, ha több mint k csúcsa van, és kevesebb mint k csúcs eltávolítása után minden esetben összefüggő marad (minimális elvágó csúcshalmazának mérete k).

Egy gráf összefüggősége vagy csúcsösszefüggősége (jelölése: κ(G)) az a legnagyobb k szám, amire igaz, hogy a gráf k-szorosan csúcsösszefüggő. Konvenció szerint a K_n teljes gráf összefüggősége n − 1, az üres gráf összefüggősége pedig 0. Adott gráfban a csúcsösszefüggőség, az élösszefüggőség és a minimális fokszám között fennáll, hogy κ(G) ≤ κ’(G) ≤ δ(G).

Definíciók

Egy 4-összefüggő gráf.

Egy gráf, ha nem teljes gráf, összefüggősége akkor k, ha k a legkisebb olyan részhalmazának a mérete, amit letörölve a gráf szétesik.^[1] A teljes gráfok nem szerepelnek ebben a definícióban, hiszen azok összefüggősége nem szüntethető meg csúcsok eltávolításával. Az n csúcsú teljes gráf n − 1-összefüggősége az első definícióból következtethető.

Ezzel ekvivalens meghatározás, hogy egy legalább két csúcsból álló gráf k-szorosan csúcsösszefüggő, ha bármely csúcspárjához található k db, a két csúcsot összekötő, csúcsfüggetlen (csúcsdiszjunkt) út; lásd Menger-tétel (Diestel 2005, p. 55). Ez a definíció szintén n − 1-et ad a K_n teljes gráf csúcsösszefüggőségére.^[1]

Az 1-összefüggő gráf neve egyszerűen összefüggő gráf. A 2-összefüggő gráfok fontos szerepet játszanak a hálózati redundancia biztosításában.

Alkalmazásai

Poliéder-kombinatorika

Bármely k dimenziós konvex politóp 1-váza (politópgráfja) k-összefüggő gráfot alkot (Balinski-tétel, Balinski 1961). Ennek részleges megfordítottja, a Steinitz-tétel szerint bármely 3-összefüggő egyszerű síkgráf egy konvex poliéder vázát alkotja.

Általánosabban, a 3-sphere regular cellulation conjecture (3-gömb reguláris csempézési sejtés) állítása szerint minden 2-összefüggő gráf a háromdimenziós gömbön található reguláris CW-komplexus 1-váza.^[2]

Számítási bonyolultság

Egy bemeneti G gráf összefüggősége a következő módon számítható polinom időben:^[3] vegyük az összes lehetséges nem szomszédos eltávolítandó ${\displaystyle (s,t)}$ csúcspárokat, felhasználva Menger tételét tudjuk, hogy az ${\displaystyle (s,t)}$-hez tartozó minimális elvágó halmaz megegyezik a köztük lévő páronként csúcsdiszjunkt utakkal, kódoljuk a bemeneti gráfot oly módon, hogy minden csúcsot duplázzunk meg élként, hogy a problémát a páronként élfüggetlen utak kiszámítására redukáljuk, majd számítsuk ki az ilyen utak maximális számát az ${\displaystyle s}$ és ${\displaystyle t}$ közötti maximális folyam számításával, ha minden él kapacitása 1; vegyük észre, hogy a gráfban a ${\displaystyle k}$ értékű folyam az egészértékűség elve miatt ${\displaystyle k}$ db, ${\displaystyle s}$ és ${\displaystyle t}$ között húzódó, páronként éldiszjunkt útnak felel meg.

Kapcsolódó szócikkek

• k-szorosan élösszefüggő gráf
• Elvágó csúcshalmaz
• Menger-tétel
• Összefüggőség (gráfelmélet)
• Tutte-beágyazás

Fordítás

• Ez a szócikk részben vagy egészben a k-vertex-connected graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

2. Sergio de Agostino (2016. augusztus 18.). „The 3-Sphere Regular Cellulation Conjecture”. International Workshop on Combinatorial Algorithms. [2017. január 9-i dátummal az eredetiből archiválva]. Hozzáférés: 2023. december 7.
3. The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291

Források

• Balinski, M. L. (1961). „On the graph structure of convex polyhedra in n-space”. Pacific Journal of Mathematics 11 (2), 431–434. o. [2012. szeptember 11-i dátummal az eredetiből archiválva]. DOI:10.2140/pjm.1961.11.431. (Hozzáférés: 2017. február 28.)
• Diestel, Reinhard. Graph Theory, 3rd, Berlin, New York: Springer-Verlag (2005). ISBN 978-3-540-26183-4