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 egy irányítatlan véges gráf csúcshalmazzal és élhalmazzal. Tetszőleges csúcshalmazra jelöljük -val azokat az éleket, melyek egy -beli csúcsból indulnak ki egy -n kívüli csúcsba (ezt néha az „élhatárának” nevezik):
(Ne felejtsük el, hogy az élek irányítatlanok, ezért az él megegyezik az éllel.) Ekkor a Cheeger-száma, melyet -vel jelölünk, a következőképp határozható meg:
A Cheeger-állandó pontosan akkor pozitív, ha ö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 (a hálózati végpontok száma) nagy.
Tekintsük például számítógép gyűrűtopológia-elrendezését, 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: . A csúcs- és az élhalmaz a következőképpen írhatók fel:
Legyen 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 izoperimetrikus számra, ami nullához tart, ahogy . Ebből következik, hogy a gyűrű elrendezésű hálózatot erősen „szűk keresztmetszetűnek” tekintjük nagy -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
Kategória:Számítógép-hálózatok Kategória:Gráfinvariánsok