Cheeger-állandó

Ez a szócikk a gráfelméleti Cheeger-állandót tárgyalja. Lásd még: Cheeger-állandó (Riemann-geometria)

A matematika, azon belül a gráfelmélet területén egy gráfhoz tartozó Cheeger-állandó, Cheeger-konstans, Cheeger-szám vagy izoperimetrikus szám azt számszerűsíti, hogy a gráf milyen mértékben rendelkezik szűk keresztmetszettel (bottleneck). A Cheeger-konstans, mint a „szűk keresztmetszetűség” mértéke több területen megjelenik: például jól összekötött számítógép-hálózatok tervezésénél, kártyapakli keverésekor. A gráfelméleti fogalmat a kompakt Riemann-sokaság Cheeger-állandója ihlette.

A Cheeger-konstans Jeff Cheeger matematikusról kapta a nevét.

Definíció

Legyen $G$ egy irányítatlan véges gráf $V (G)$ csúcshalmazzal és $E (G)$ élhalmazzal. Tetszőleges $A \subseteq V (G)$ csúcshalmazra jelöljük $\partial A$ -val azokat az éleket, melyek egy $A$ -beli csúcsból indulnak ki egy $A$ -n kívüli csúcsba (ezt néha az $A$ „élhatárának” nevezik):

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

(Ne felejtsük el, hogy az élek irányítatlanok, ezért az $(x, y)$ él megegyezik az $(y, x)$ éllel.) Ekkor a $G$ Cheeger-száma, melyet $h (G)$ -vel jelölünk, a következőképp határozható meg:^[1]

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

A Cheeger-állandó pontosan akkor pozitív, ha $G$ összefüggő. Intuitívan elmondható, hogy ha a Cheeger-állandó pozitív, de kicsi, akkor a gráfnak van „szűk keresztmetszete” abban az értelemben, hogy van benne két „nagy” csúcshalmaz, ami között „kevés” él húzódik. A Cheeger-konstans „nagy”, ha a gráf bármely két csúcshalmazba osztásában a két részhalmaz között „sok” kapcsolat (él) van.

Példa: számítógép-hálózatok

Számítógép-tudományi alkalmazásokban felmerül az igénye olyan hálózati elrendezések megalkotásának, melyek Cheeger-állandója magas (vagy legalábbis a korlát határozottan magasabban van nullánál), abban az esetben is, amikor $| V (G)|$ (a hálózati végpontok száma) nagy.

Tekintsük például $N \geq 3$ számítógép gyűrűtopológia-elrendezését, $G N$ gráfként reprezentálva. Számozzunk meg a gépeket a gyűrű körül az óramutató járásának megfelelően: $1, 2, ..., N$ . A csúcs- és az élhalmaz a következőképpen írhatók fel:

{\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&=\{(1,2),(2,3),\cdots ,(N-1,N),(N,1)\}\end{aligned}}

Legyen $A$ ezen számítógépek közül $\left\lfloor {\tfrac {N}{2}}\right\rfloor$ összekötött darab gyűjteménye:

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

Így,

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

és

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

Ez a példa egy felső korlátot ad a $h (G N)$ izoperimetrikus számra, ami nullához tart, ahogy $N \to \infty$ . Ebből következik, hogy a gyűrű elrendezésű hálózatot erősen „szűk keresztmetszetűnek” tekintjük nagy $N$ -re, ami gyakorlati megvalósításokban egyáltalán nem praktikus. Ha a gyűrűbe tartozó egyetlen számítógép meghibásodik, a hálózati teljesítmény jelentősen csökkenne. Ha két, nem szomszédos számítógép hibásodna meg, a hálózat két különálló komponensre esne szét.

Cheeger-egyenlőtlenségek

A Cheeger-állandó az expander gráfok kontextusában is előkerül, mint egy gráf élexpanziójának egyik mértéke. Az úgynevezett Cheeger-egyenlőtlenségek a gráf Cheeger-állandóját és a spektrális rését hozzák összefüggésbe.

Kapcsolódó szócikkek

Jegyzetek

↑ (1989. december 1.) „Isoperimetric numbers of graphs”. Journal of Combinatorial Theory, Series B 47 (3), 274–291. o. DOI:10.1016/0095-8956(89)90029-4.

(2006) „Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that”. J. Stat. Mech. 2006 (08), P08007. o. DOI:10.1088/1742-5468/2006/08/P08007.
Lackenby, M. (2006). „Heegaard splittings, the virtually Haken conjecture and property (τ)”. Invent. Math. 164 (2), 317–359. o. DOI:10.1007/s00222-005-0480-x.

[1] (1989. december 1.) „Isoperimetric numbers of graphs”. Journal of Combinatorial Theory, Series B 47 (3), 274–291. o. DOI:10.1016/0095-8956(89)90029-4.

[1]