Cheeger-állandó

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.

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

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 ⊆ V(G) csúcshalmazra jelöljük ∂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):

${\displaystyle \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]

${\displaystyle 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

Gyűrű topológiájú hálózat

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 ≥ 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:

${\displaystyle {\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 ${\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }$ összekötött darab gyűjteménye:

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

Így,

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

és

${\displaystyle {\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 → ∞. 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

• Algebrai összefüggőség
• Cheeger-korlát
• Konduktancia
• Összefüggőség (gráfelmélet)
• Expander gráf

Jegyzetek

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.

• (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.