Cheeger konstant (grafteori)

I matematik är Cheeger -konstanten (även Cheeger-nummer eller isoperimetriskt tal ) för en graf ett numeriskt mått på om 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 . Den grafteoretiska uppfattningen har sitt ursprung efter Cheegers isoperimetriska konstant för ett kompakt Riemann-grenrör .

Cheeger-konstanten är uppkallad efter matematikern Jeff Cheeger .

Definition

Låt $G$ vara en oriktad finit graf med vertexmängd $V (G)$ och kantmängd $E (G)$ . För en samling av hörn $A \subseteq V (G)$ , låt $\partial A$ beteckna samlingen av alla kanter som går från en vertex i $A$ till en vertex utanför $A$ (kallas ibland kantgränsen för $A$ ):

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

Observera att kanterna är oordnade, dvs. $\{x,y\}=\{y,x\}$ . Cheeger -konstanten för $G$ , betecknad $h (G)$ , definieras av

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

Cheeger-konstanten är strikt positiv om och endast om $G$ är en sammankopplad 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 vertexuppsättningen i två delmängder har "många" länkar mellan dessa två delmängder.

Exempel: datornätverk

Ring nätverkslayout

I tillämpningar till teoretisk datavetenskap vill man utforma nätverkskonfigurationer för vilka Cheeger-konstanten är hög (åtminstone avgränsad från noll) även när $| V (G)|$ (antalet datorer i nätverket) är stort.

Betrakta till exempel ett ringnätverk med $N \geq 3$ datorer, tänkt som en graf $G N$ . Numrera datorerna $1, 2, ..., N$ medurs runt ringen. Matematiskt ges vertexmängden och kantmängden av:

{\begin{aligned}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{ Justerat}}

Anta att $A$ är en samling av $\left\lfloor {\tfrac {N}{2}}\right\rfloor$ av dessa datorer i en ansluten kedja:

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

Så,

\partial A=\left\{\left\{\left\lfloor {\tfrac {N} {2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},

och

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

Det här exemplet ger en övre gräns för Cheeger-konstanten h $(GN) .,$ som också tenderar till noll som $N \to \infty$ Följaktligen skulle vi betrakta ett ringnät som mycket "flaskhalsat" för stort $N$ , och detta är högst oönskat i praktiska termer. Vi skulle bara behöva en av datorerna på ringen för att misslyckas, och nätverkets prestanda skulle minska kraftigt. Om två icke-intilliggande datorer skulle misslyckas, skulle nätverket delas upp i två frånkopplade komponenter.

Cheeger ojämlikheter

Cheeger-konstanten är särskilt viktig i samband med expandergrafer eftersom det är ett sätt att mäta kantexpansionen på en graf. De så kallade Cheeger-ojämlikheterna relaterar Egenvärdesgapet i en graf med dess Cheeger-konstant. Mer explicit

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

där $\Delta (G)$ är den maximala graden för noderna i $G$ och $\lambda$ är spektralgapet för grafens laplaciska matris . Cheeger-ojämlikheten är ett grundläggande resultat och motivation för spektralgrafteorin .

Se även

Donetti, L.; Neri, F. & Muñoz, M. (2006). "Optimala nätverkstopologier: expanders, burar, Ramanujan-grafer, intrasslade nätverk och allt det där". J. Stat. Mech . 2006 (8): P08007. arXiv : cond-mat/0605565 . Bibcode : 2006JSMTE..08..007D . doi : 10.1088/1742-5468/2006/08/P08007 . S2CID 16192273 .
Lackenby, M. (2006). "Heegaard splittings, den praktiskt taget Haken förmodan och egendom (τ)". Uppfinna. Matematik . 164 (2): 317–359. arXiv : math/0205327 . Bibcode : 2006InMat.164..317L . doi : 10.1007/s00222-005-0480-x . S2CID 12847770 .