Konektivita (teorie grafů) - Connectivity (graph theory)

Tento graf se odpojí, když je odstraněn nejvíce pravý uzel v šedé oblasti vlevo

Po odstranění přerušované hrany se tento graf odpojí.

V matematice a informatice je konektivita jedním ze základních konceptů teorie grafů : požaduje minimální počet prvků (uzlů nebo hran), které je třeba odstranit, aby se zbývající uzly rozdělily na dva nebo více izolovaných podgrafů . Úzce souvisí s teorií problémů toku sítě . Konektivita grafu je důležitým měřítkem jeho odolnosti jako sítě.

Propojené vrcholy a grafy

S vrcholem 0 je tento graf odpojen. Zbytek grafu je propojen.

V neorientovaném grafu $G$ se dva vrcholy $u$ a $v$ nazývají spojené, pokud $G$ obsahuje cestu od $u$ do $v$ . Jinak se jim říká odpojení . Pokud jsou dva vrcholy navíc spojeny dráhou o délce $1$ , tj. O jedinou hranu, nazývají se vrcholy přilehlé .

O grafu se říká, že je připojen, pokud je připojen každý pár vrcholů v grafu. To znamená, že mezi každou dvojicí vrcholů existuje cesta . Neorientovaný graf, který není připojen, se nazývá odpojený . Neorientovaný graf G je tedy odpojen, pokud existují dva vrcholy v G tak, že žádná cesta v G nemá tyto vrcholy jako koncové body. Je připojen graf pouze s jedním vrcholem. Tupý graf s dvěma nebo více vrcholů je odpojen.

Orientovaný graf se nazývá slabě spojeny při výměně všech svých směřujících hran s neorientovanými hranami vytváří souvislý (neřízený) graf. Je jednostranně propojený nebo jednostranný (také nazývaný semiconnected ), pokud obsahuje směrovanou cestu od $u$ do $v$ nebo směrovanou cestu od $v$ do $u$ pro každou dvojici vrcholů $u, v$ . Je silně propojený nebo jednoduše silný, pokud obsahuje směrovanou cestu od $u$ do $v$ a směrovanou cestu od $v$ do $u$ pro každou dvojici vrcholů $u, v$ .

Komponenty a řezy

Připojené zařízení je maximální připojený podgrafem undirected grafu. Každý vrchol patří přesně jedné připojené komponentě, stejně jako každý okraj. Graf je připojen právě tehdy, pokud má právě jednu připojenou komponentu.

Tyto silné komponenty jsou maximální pevně připojen subgraphs z orientovaný graf.

Vrchol řez nebo oddělování sada z připojeného grafu $G$ je sada vrcholů, jejichž odstranění činí $G$ odpojen. Připojení vrchol $κ (G),$ (kde $G$ není úplný graf ) je velikost minimální vrcholu řezu. Grafu se říká $k$ -připojený $k$ vrcholu nebo $k$ -připojený, pokud je jeho vrcholová konektivita $k$ nebo větší.

Přesněji řečeno, jakýkoli graf $G$ (úplný nebo ne) se říká, že je $k$ -propojen vrcholem, pokud obsahuje alespoň $k +1$ vrcholů, ale neobsahuje sadu $k -1$ vrcholů, jejichž odebráním se graf odpojí; a $κ (G)$ je definován jako největší $k$ , takže $G$ je $k$ -připojeno. Zejména kompletní graf s $n$ vrcholy, označený $K n$ , nemá vůbec žádné škrty vrcholů, ale $κ (K n) = n - 1$ .

Vrchol střih pro dva vrcholy $ve tvaru písmene U$ a $V$ je sada vrcholů, jehož odstranění z grafu odpojí $u$ a $v$ . Místní připojení $κ (u, v),$ je velikost nejmenší vrcholu řezu dělicí $U$ a $V$ . Místní konektivita je pro neorientované grafy symetrická; tj. $κ (u, v) = κ (v, u)$ . Kromě toho, s výjimkou úplných grafů, $κ (G) se$ rovná minimu $κ (u, v)$ na všech nesousedících párech vrcholů $u, v$ .

$2$ -konektivita se také nazývá bikonektivita a $3$ -konektivita se také nazývá trikonektivita . Graf $G,$ který je připojen, ale není připojen $2,$ se někdy nazývá oddělitelný .

Pro hrany lze definovat analogické koncepty. V jednoduchém případě, kdy by řezání jedné konkrétní hrany odpojilo graf, se tato hrana nazývá můstek . Obecněji řečeno, řez hrany $G$ je sada hran, jejichž odstranění způsobí odpojení grafu. Okrajového připojení $λ (G)$ je velikost nejmenší hrany řezu a místní okraj-připojení $λ (u, v)$ dvou vrcholů $u, v$ je velikost nejmenší hrany řezu odpojení $u$ z $V$ . Opět platí, že místní okrajová konektivita je symetrická. Grafu se říká $k$ -edge -connected, pokud je jeho okrajová konektivita $k$ nebo větší.

O grafu se říká, že je maximálně propojený, pokud se jeho konektivita rovná jeho minimálnímu stupni. O grafu se říká, že je maximálně připojen k hraně, pokud se jeho okrajová konektivita rovná jeho minimálnímu stupni.

Super a hyperkonektivita

O grafu se říká, že je super propojený nebo super-κ, pokud každý minimální řez vrcholu izoluje vrchol. O grafu se říká, že je hyperspojený nebo hyper-κ, pokud vymazání každého minimálního řezu vrcholu vytvoří přesně dvě složky, z nichž jedna je izolovaný vrchol. Graf je napůl hyper-spojený nebo semi-hyper-κ, pokud jakýkoli řez minimálního vrcholu rozděluje graf na přesně dvě složky.

Přesněji: graf spojený s $G$ se říká, že je superpojený 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$ souvislý graf se říká, že super-okraj připojené nebo super-λ -li všechny minimální okrajové řezy se skládají z hran dopadajícího na nějakém (minimální-stupeň) vrcholu.

Cutset $X$ z $G$ se nazývá netriviální cutset, pokud $X$ neobsahuje sousedství $N (u)$ z nějakého vrcholu $u \notin X$ . Pak superkonektivita κ1 G je:

κ1 (G) = min {| X | : X je netriviální sestava}.

Netriviální okrajový řez a superkonektivita hran λ1 (G) jsou definovány analogicky.

Mengerova věta

Jedním z nejdůležitějších faktů o konektivitě v grafech je Mengerova věta , která charakterizuje konektivitu a okrajovou konektivitu grafu z hlediska počtu nezávislých cest mezi vrcholy.

Pokud $u$ a $v$ jsou vrcholy grafu $G$ , pak se kolekce cest mezi $u$ a $v$ nazývá nezávislá, pokud žádné z nich nesdílí vrchol (kromě samotných $u$ a $v$ ). Podobně je kolekce nezávislá na hraně, pokud v ní žádné dvě cesty nesdílejí hranu. Počet vzájemně nezávislých cest mezi $u$ a $v$ se zapisuje jako $κ ' (u, v)$ a počet cest nezávislých na hraně mezi $u$ a $v$ se zapisuje jako $λ ' (u, v)$ .

Mengerova věta tvrdí, že pro různé vrcholy se u , v , $λ (u, v)$ rovná $λ ' (u, v)$ , a pokud u také sousedí s v, pak $κ (u, v) se$ rovná $κ ' (u, v)$ . Tato skutečnost je ve skutečnosti zvláštním případem min-cut věty o maximálním toku .

Výpočtové aspekty

Problém určení, zda jsou dva vrcholy v grafu propojeny, lze efektivně vyřešit pomocí vyhledávacího algoritmu , jako je například vyhledávání do šířky . Obecněji řečeno, je snadné výpočetně určit, zda je graf připojen (například pomocí datové struktury nesouvislé sady ), nebo spočítat počet připojených komponent. Jednoduchý algoritmus může být zapsán v pseudokódu následujícím způsobem:

Začněte v libovolném uzlu grafu, $G$
Pokračujte z tohoto uzlu buď pomocí vyhledávání hloubky, nebo šířky, počítáním všech dosažených uzlů.
Jakmile je graf zcela procházen a je -li počet počítaných uzlů stejný jako počet uzlů $G$ , graf je připojen; jinak je odpojen.

Podle Mengerovy věty lze pro libovolné dva vrcholy $u$ a $v$ v připojeném grafu $G$ efektivně určit čísla $κ (u, v)$ a $λ (u, v)$ pomocí algoritmu minimálního řezu max . Průtoku. Konektivitu a okrajovou konektivitu $G$ lze pak vypočítat jako minimální hodnoty $κ (u, v)$ a $λ (u, v)$ .

Ve výpočetní složitosti teorie, SL je třída problémů přihlásíte prostor redukovatelný na problém určení, zda dva vrcholy v grafu jsou připojeny, která se ukázala být rovna L od Omer Reingold v roce 2004. Z tohoto důvodu, neorientovaný připojení graf může být řešeno v prostoru $O (log n)$ .

Problém výpočtu pravděpodobnosti, že je připojen náhodný graf Bernoulliho, se nazývá spolehlivost sítě a problém výpočtu, zda jsou spojeny dva dané vrcholy, problém spolehlivosti ST. Oba jsou #P -tvrdé .

Počet připojených grafů

Počet odlišných spojených označených grafů s n uzly je uveden v on-line encyklopedii celočíselných sekvencí jako sekvence A001187 . 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

Konektivita vrcholů a okrajů odpojeného grafu je $0$ .
$1$ -připojitelnost je ekvivalentní propojenosti pro grafy alespoň 2 vrcholů.
Úplný graf na $n$ vrcholech má hranu připojení rovná $n - 1$ . Každý další jednoduchý graf na $n$ vrcholech má striktně menší okrajovou konektivitu.
Ve stromu je místní okrajová konektivita mezi každou dvojicí vrcholů $1$ .

Hranice připojení

Vrcholná konektivita grafu je menší nebo rovna jeho okrajové konektivitě. To znamená $κ (G) \leq λ (G)$ . Oba jsou menší nebo rovny minimálnímu stupni grafu, protože odstraněním všech sousedů vrcholu minimálního stupně se tento vrchol odpojí od zbytku grafu.
U vrcholu-transitivní graf ze studia $d$ , máme: $2 (d + 1) / 3 \leq mítk (G) \leq lambda (G) = d$ .
U vrcholu-transitivní graf ze studia $d \leq 4$ , nebo pro (neřízený) minimální Cayley grafu ze studia $d$ , nebo pro symetrické graf ze studia $d$ , oba druhy připojení jsou stejné: $κ (G) = λ (G) = d$ .

Další vlastnosti

Propojení je zachováno grafickými homomorfismy .
Pokud je připojeno $G,$ pak je připojen také jeho spojnicový graf $L (G)$ .
Graf $G$ je spojen se $2$ hranami právě tehdy, pokud má orientaci, která je silně spojena.
Baliński teorém uvádí, že polytopal graf ( $1$ - kostra ) o $K$ rozměrné konvexní mnohostěn je $k$ -vertex-připojeného grafu. Steinitzova předchozí věta, že jakýkoli 3-vrcholem spojený planární graf je polytopní graf ( Steinitzova věta ), poskytuje částečný opak.
Podle věty GA Diraca , pokud je graf $k$ -připojen pro $k \geq 2$ , pak pro každou sadu $k$ vrcholů v grafu existuje cyklus, který prochází všemi vrcholy v sadě. Opak je pravdivý, když $k = 2$ .

Languages

In other projects