Anslutningar (grafteori) - Connectivity (graph theory)

Den här grafen kopplas bort när noden längst till höger i det grå området till vänster tas bort

Denna graf kopplas bort när den streckade kanten tas bort.

Inom matematik och datavetenskap är anslutning ett av de grundläggande begreppen för grafteori : den ber om det minsta antalet element (noder eller kanter) som måste tas bort för att separera de återstående noderna i två eller flera isolerade subgrafer . Det är nära besläktat med teorin om nätverksflödesproblem . Anslutningen av en graf är ett viktigt mått på dess motståndskraft som ett nätverk.

Anslutna hörn och diagram

Med toppunkt 0 kopplas denna graf bort. Resten av grafen är ansluten.

I en oriktad graf $G$ kallas två hörn $u$ och $v$ anslutna om $G$ innehåller en väg från $u$ till $v$ . Annars kallas de bortkopplade . Om de två hörnen dessutom är förbundna med en bana med längd $1$ , dvs med en enda kant, kallas hörnen intill .

Det sägs att en graf är ansluten om varje hörnpar i grafen är anslutna. Det betyder att det finns en väg mellan varje hörnpar. En oriktad graf som inte är ansluten kallas frånkopplad . En oriktad graf G kopplas därför bort om det finns två hörn i G så att ingen väg i G har dessa hörn som slutpunkter. En graf med bara en toppunkt är ansluten. En kantlös graf med två eller flera hörn kopplas bort.

En riktad graf kallas svagt ansluten om alla riktade kanter ersätts med oriktade kanter ger en ansluten (oriktad) graf. Det är ensidigt anslutet eller ensidigt (även kallat halvkopplat ) om det innehåller en riktad väg från $u$ till $v$ eller en riktad väg från $v$ till $u$ för varje par hörn $u, v$ . Den är starkt ansluten , eller helt enkelt stark, om den innehåller en riktad väg från $u$ till $v$ och en riktad väg från $v$ till $u$ för varje par hörn $u, v$ .

Komponenter och snitt

En ansluten komponent är en maximalt ansluten subgraf för en oriktad graf. Varje hörn hör till exakt en ansluten komponent, liksom varje kant. En graf är ansluten om och bara om den har exakt en ansluten komponent.

De starka komponenterna är de maximalt starkt sammankopplade delgraferna av en riktad graf.

En hörnskärning eller separationsuppsättning av en ansluten graf $G$ är en uppsättning hörn vars avlägsnande gör $G$ urkopplad. Den vertex anslutning $κ (G)$ (där $G$ är inte en fullständig graf ) är storleken på en minimal vertex snitt. En graf kallas $k$ -vertex -ansluten eller $k$ -kopplad om dess toppunktsanslutning är $k$ eller större.

Mer exakt, varje graf $G$ är (komplett eller inte) sägs vara $k$ -vertex kopplade om den innehåller åtminstone $k +1$ vertex, men innehåller inte en uppsättning av $k - 1$ vertex vars avlägsnande kopplar grafen; och $κ (G)$ definieras som den största $k$ så att $G$ är $k$ -ansluten. I synnerhet har en fullständig graf med $n$ hörn, betecknade $K n$ , inga hörnsnitt alls, men $κ (K n) = n - 1$ .

En vertex skuren för två hörn $u$ och $v$ är en uppsättning av vertex vars avlägsnande från grafen kopplar $u$ och $v$ . Den lokala anslutningen $κ (u, v)$ är storleken på ett minsta hörnsnitt som skiljer $u$ och $v$ . Lokal anslutning är symmetrisk för ostyrda grafer; det vill säga $κ (u, v) = κ (v, u)$ . Förutom fullständiga grafer är $κ (G) dessutom$ lika med minimum $κ (u, v)$ över alla icke -närliggande hörnpar $u, v$ .

$2$ -connectivity kallas också biconnectivity och $3$ -connectivity kallas också triconnectivity . En graf $G$ som är ansluten men inte $2$ -ansluten kallas ibland separerbar .

Analoga begrepp kan definieras för kanter. I det enkla fallet där skärning av en enda, specifik kant skulle koppla bort grafen, kallas den kanten för en bro . Mer allmänt är en kantskärning av $G$ en uppsättning kanter vars avlägsnande gör grafen frånkopplad. Den kant-konnektivitet $λ (G)$ är storleken på en minsta kant snitt, och den lokala kantanslutnings $λ (u, v)$ av två hörn $u, v$ är storleken på en minsta kant skuren bortkoppling $u$ från $v$ . Återigen är lokal kantanslutning symmetrisk. En graf kallas $k$ -kant -ansluten om dess kantanslutning är $k$ eller större.

En graf sägs vara maximalt ansluten om dess anslutning är lika med minsta grad. En graf sägs vara maximalt kantansluten om dess kantanslutning är lika med minsta grad.

Super- och hyper-anslutning

En graf sägs vara superansluten eller super-κ om varje minsta hörnskärning isolerar en hörn. En graf sägs vara hyperkopplad eller hyper-κ om radering av varje minsta hörnskärning skapar exakt två komponenter, varav en är en isolerad topp. Ett diagram är halvhyper-anslutet eller halvhyper-κ om någon minsta toppunktsskärning separerar grafen i exakt två komponenter.

Mer exakt: en $G-$ ansluten graf sägs vara superansluten eller super-κ om alla minsta vertex-snitt består av hörnen intill en (minsta grad) toppunkt. En $G-$ ansluten graf sägs vara superkant-ansluten eller super-λ om alla minsta kantskärningar består av kanterna som infaller på någon (minsta grad) toppunkt.

En cutset $X$ av $G$ kallas en icke-trivial cutset om $X$ inte innehåller det område i $N (u)$ av något av hörnen $u \notin X$ . Då superconnectivity κ1 G är:

κ1 (G) = min {| X | : X är en icke-trivial skärning}.

En icke-trivial kantskärning och kant- superanslutning λ1 (G) definieras analogt.

Mengers sats

En av de viktigaste fakta om anslutning i grafer är Mengers sats , som kännetecknar anslutning och kantanslutning för en graf när det gäller antalet oberoende vägar mellan hörn.

Om $u$ och $v$ är hörn av en graf $G$ , kallas en samling vägar mellan $u$ och $v$ oberoende om ingen av dem delar en toppunkt (andra än $u$ och $v$ själva). På samma sätt är samlingen kantoberoende om inga två vägar i den delar en kant. Antalet ömsesidigt oberoende vägar mellan $u$ och $v$ skrivs som $κ ' (u, v)$ , och antalet ömsesidigt oberoende vägar mellan $u$ och $v$ skrivs som $λ ' (u, v)$ .

Mengers sats säger att för olika hörn är u , v , $λ (u, v)$ lika med $λ ' (u, v)$ , och om u inte heller ligger intill v då är $κ (u, v)$ lika med $κ ' (u, v)$ . Detta faktum är faktiskt ett specialfall av maxflödet min-cut sats .

Beräkningsaspekter

Problemet med att avgöra om två hörn i en graf är ansluten kan lösas effektivt med hjälp av en sökalgoritm , till exempel bredd-första sökning . Mer allmänt är det lätt att beräkna beräkningsvis om en graf är ansluten (till exempel genom att använda en osammanhängande datastruktur ) eller att räkna antalet anslutna komponenter. En enkel algoritm kan skrivas i pseudokod enligt följande:

Börja vid valfri godtycklig nod i grafen, $G$
Fortsätt från den noden med antingen djup-först eller bredd-första sökning och räknar alla noder som nås.
När grafen har gått igenom helt och hållet, om antalet räknade noder är lika med antalet noder för $G$ , är grafen ansluten; annars är den bortkopplad.

Med Mengers sats, för två hörn $u$ och $v$ i en ansluten graf $G$ , kan siffrorna $κ (u, v)$ och $λ (u, v)$ bestämmas effektivt med hjälp av maxflödesminskningsalgoritmen . Anslutningen och kantanslutningen för $G$ kan sedan beräknas som minimivärdena $κ (u, v)$ respektive $λ (u, v)$ .

I beräkningskomplexitetsteorin är SL klassen av problem, log-utrymme som kan reduceras till problemet att avgöra om två hörn i en graf är anslutna, vilket visade sig vara lika med L av Omer Reingold 2004. Därför kan oreglerad grafanslutning vara löst i $O (log n)$ -utrymme.

Problemet med att beräkna sannolikheten för att en slumpmässig Bernoulli- graf är ansluten kallas nätverkssäkerhet och problemet med att beräkna om två givna hörn är anslutna ST-tillförlitlighetsproblemet. Båda dessa är #P -hårda.

Antal anslutna grafer

Antalet distinkta anslutna märkta grafer med n noder tabuleras i Nätuppslagsverket över heltalsföljder som sekvens A001187 . De första få icke-triviala termerna är

n	grafer
2	1
3	4
4	38
5	728
6	26704
7	1866256
8	251548592

Exempel

Spets- och kantanslutningarna för en frånkopplad graf är båda $0$ .
$1$ -anslutning motsvarar anslutning för grafer med minst 2 hörn.
Den kompletta grafen på $n$ hörn har kantanslutning lika med $n- 1$ . Varannan enkel graf på $n$ hörn har strikt mindre kantanslutning.
I ett träd är den lokala kantanslutningen mellan varje hörnpar $1$ .

Gränser för anslutning

Vertex-anslutningen för en graf är mindre än eller lika med dess kantanslutning. Det vill säga $κ (G) \leq λ (G)$ . Båda är mindre än eller lika med grafens minsta grad , eftersom radering av alla grannar till en toppunkt med minsta grad kommer att koppla bort den punkten från resten av grafen.
För en toppunkt-transitiv graf med grad $d$ har vi: $2 (d + 1)/3 \leq κ (G) \leq λ (G) = d$ .
För en vertex-transitiv graf med grad $d \leq 4$ , eller för någon (oriktad) minimal Cayley-graf av grad $d$ , eller för någon symmetrisk graf för grad $d$ , är båda typerna av anslutningar lika: $κ (G) = λ (G) = d$ .

Övriga fastigheter

Anslutningen bevaras av grafhomomorfismer .
Om $G$ är ansluten är dess linjediagram $L (G)$ också ansluten.
En graf $G$ är $2$ -kantad ansluten om och bara om den har en orientering som är starkt ansluten.
Balinski teorem anger att polytopal graf ( $1$ - skelett ) av en $k$ -dimensionell konvex polytope är en $k$ -vertex-ansluten graf. Steinitz tidigare sats om att alla 3-vertex-anslutna plana diagram är en polytopal graf ( Steinitz sats ) ger en partiell omvänd.
Enligt en sats i GA Dirac , om en graf är $k$ -kopplad för $k \geq 2$ , så finns det för varje uppsättning $k$ -hörn i grafen en cykel som passerar genom alla hörn i uppsättningen. Det omvända är sant när $k = 2$ .

Languages

In other projects