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 Sablon:Mvar egy irányítatlan véges gráf Sablon:Math csúcshalmazzal és Sablon:Math élhalmazzal. Tetszőleges Sablon:Math csúcshalmazra jelöljük Sablon:Math-val azokat az éleket, melyek egy Sablon:Mvar-beli csúcsból indulnak ki egy Sablon:Mvar-n kívüli csúcsba (ezt néha az Sablon:Mvar „é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 Sablon:Math él megegyezik az Sablon:Math éllel.) Ekkor a Sablon:Mvar Cheeger-száma, melyet Sablon:Math-vel jelölünk, a következőképp határozható meg:

$h(G):=\min \{\frac{|\partial A|}{|A|}:A\subseteq V(G),0<|A|\le \frac{1}{2}|V(G)|\}.$

A Cheeger-állandó pontosan akkor pozitív, ha Sablon:Mvar ö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 Sablon:Math (a hálózati végpontok száma) nagy.

Tekintsük például Sablon:Math számítógép gyűrűtopológia-elrendezését, Sablon:Mvar 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: Sablon:Math. A csúcs- és az élhalmaz a következőképpen írhatók fel:

$\begin{array}{cc}V(G_N)& =\{1,2,\cdots ,N-1,N\}\\ E(G_N)& =\{(1,2),(2,3),\cdots ,(N-1,N),(N,1)\}\end{array}$

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

$A=\{1,2,\cdots ,\lfloor \frac{N}{2}\rfloor \}.$

Így,

$\partial A=\{(\lfloor \frac{N}{2}\rfloor ,\lfloor \frac{N}{2}\rfloor +1),(N,1)\},$

és

$\frac{|\partial A|}{|A|}=\frac{2}{\lfloor \frac{N}{2}\rfloor }\to 0\text{ ahogy }N\to \mathrm{\infty }.$

Ez a példa egy felső korlátot ad a Sablon:Math izoperimetrikus számra, ami nullához tart, ahogy Sablon:Math. Ebből következik, hogy a gyűrű elrendezésű hálózatot erősen „szűk keresztmetszetűnek” tekintjük nagy Sablon:Mvar-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

• Sablon:Cite journal
• Sablon:Cite journal