Cheeger konstant (grafteori) - Cheeger constant (graph theory)

I matematik är Cheegerkonstanten (även Cheegertal eller isoperimetriskt tal ) för ett diagram ett numeriskt mått på huruvida en graf har en "flaskhals" eller inte. Cheeger-konstanten som ett mått på "flaskhals" är av stort intresse på många områden: till exempel att bygga välanslutna nätverk av datorer , kortblandning . Grafteoretiska begreppet härstammar från Cheegers isoperimetriska konstant för en kompakt Riemannian-grenrör .

Cheegerkonstanten är uppkallad efter matematikern Jeff Cheeger .

Definition

Låt G vara en oriktad ändlig graf med toppuppsättning V ( G ) och kantuppsättning E ( G ) . För en samling hörn A ⊆ V ( G ) , låt ∂ A beteckna samlingen av alla kanter som går från en topp i A till en topp utanför A (kallas ibland kantgränsen för A ):

${\ displaystyle \ partial A: = \ {\ {x, y \} \ i E (G) \: \ x \ i A, y \ i V (G) \ setminus A \}.}$

Observera att kanterna är oordnade, dvs . Den Cheeger konstant av G , betecknat h ( G ) , är definierad av ${\ displaystyle \ {x, y \} = \ {y, x \}}$

${\ displaystyle h (G): = \ min \ left \ {{\ frac {| \ partial A |} {| A |}} \: \ A \ subseteq V (G), 0 <| A | \ leq { \ tfrac {1} {2}} | V (G) | \ höger \}.}$

Cheegerkonstanten är strikt positiv om och endast om G är en ansluten graf . Intuitivt, om Cheeger-konstanten är liten men positiv, så finns det en "flaskhals", i den meningen att det finns två "stora" uppsättningar av hörn med "få" länkar (kanter) mellan dem. Cheeger-konstanten är "stor" om någon möjlig uppdelning av toppunkten i två underuppsättningar har "många" länkar mellan dessa två underuppsättningar.

Exempel: datornätverk

Ring nätverkslayout

I applikationer till teoretisk datavetenskap vill man ta fram nätverkskonfigurationer för vilka Cheegerkonstanten är hög (åtminstone begränsad från noll) även när | V ( G ) | (antalet datorer i nätverket) är stort.

Betrakta exempelvis ett ringnät av N ≥ 3 datorer, tänkt som en graf G _N . Numrer datorerna 1, 2, ..., N medurs runt ringen. Matematiskt ges topp- och kantuppsättningen av:

${\ displaystyle {\ begin {align} V (G_ {N}) & = \ {1,2, \ cdots, N-1, N \} \\ E (G_ {N}) & = {\ big \ { } \ {1,2 \}, \ {2,3 \}, \ cdots, \ {N-1, N \}, \ {N, 1 \} {\ big \}} \ end {align}}}$

Ta A för att vara en samling av dessa datorer i en ansluten kedja: ${\ displaystyle \ left \ lfloor {\ tfrac {N} {2}} \ right \ rfloor}$

${\ displaystyle A = \ left \ {1,2, \ cdots, \ left \ lfloor {\ tfrac {N} {2}} \ right \ rfloor \ right \}.}$

Så,

${\ displaystyle \ partial A = \ left \ {\ left \ {\ left \ lfloor {\ tfrac {N} {2}} \ right \ rfloor, \ left \ lfloor {\ tfrac {N} {2}} \ right \ rgolv +1 \ höger \}, \ {N, 1 \} \ höger \},}$

och

${\ displaystyle {\ frac {| \ partial A |} {| A |}} = {\ frac {2} {\ left \ lfloor {\ tfrac {N} {2}} \ right \ rfloor}} \ till 0 {\ mbox {as}} N \ till \ infty.}$

Detta exempel ger en övre gräns för Cheegerkonstanten h ( G _N ) , som också tenderar att vara noll som N → ∞ . Följaktligen skulle vi betrakta ett ringnätverk som mycket "flaskhalsat" för stora N , och detta är mycket oönskat i praktiken. Vi skulle bara behöva en av datorerna på ringen för att misslyckas, och nätverksprestanda skulle minskas kraftigt. Om två icke-intilliggande datorer skulle misslyckas skulle nätverket delas upp i två frånkopplade komponenter.

Ojämlikheter i Cheeger

Cheegerkonstanten är särskilt viktig i samband med expanderdiagram eftersom det är ett sätt att mäta kantutvidgningen av en graf. De så kallade Cheeger-ojämlikheterna relaterar Eigenvalue-klyftan i en graf med dess Cheeger-konstant. Mer tydligt

${\ displaystyle 2h (G) \ geq \ lambda \ geq {\ frac {h ^ {2} (G)} {2 \ Delta (G)}}}$

i vilken är den maximala graden för noder i och är spektralgapet i Laplacian-matrisen i diagrammet. ${\ displaystyle \ Delta (G)}$${\ displaystyle G}$${\ displaystyle \ lambda}$

Se även

• Algebraisk anslutning
• Cheeger bunden
• Konduktans (diagram)
• Anslutning (grafteori)
• Expandera graf

Referenser

• Donetti, L .; Neri, F. & Muñoz, M. (2006). "Optimala nätverkstopologier: expanderare, burar, Ramanujan-grafer, intrasslade nätverk och allt detta". J. Stat. Mech . 2006 (08): P08007. arXiv : cond-mat / 0605565 . Bibcode : 2006JSMTE..08..007D . doi : 10.1088 / 1742-5468 / 2006/08 / P08007 .
• Lackenby, M. (2006). "Heegaard splittringar, den praktiskt taget Haken gissningen och egenskapen (τ)". Uppfinna. Matematik . 164 (2): 317–359. arXiv : matematik / 0205327 . Bibcode : 2006InMat.164..317L . doi : 10.1007 / s00222-005-0480-x .