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 ⊆ 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):
(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]
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/NetworkTopology-Ring.png/220px-NetworkTopology-Ring.png)
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, GN 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:
Legyen A ezen számítógépek közül összekötött darab gyűjteménye:
Így,
és
Ez a példa egy felső korlátot ad a h(GN) 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
- ↑ (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.