A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
- 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
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
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.
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Épületirányító rendszer
Útválasztás
Útválasztó
Ütközési tartomány
100Base-FX
100Base-T4
100Base-TX
Arcnet hálózatok
ARPANET
Avaya
Az adatáteresztő képesség mérése
C3 Kulturális és Kommunikációs Központ
CAN-busz
ChatFlow
Cheeger-állandó
Cisco IOS
Common Object Request Broker Architecture
Csomagtovábbítás
Csomag (informatika)
Dataizmus
Dinamikus DNS
Ethernet
Fordított proxy
Forgalomgeneráló modell
Gazdagép
Gyűrűs kocka
Gyors Ethernet
Hálózati címfordítás
Hálózati híd
Hálózati szegmens
Helyi hálózat
Hub (hálózat)
IEEE 802
Intranet
Iperf
Kábelmodem
Kliens
Kvantumhálózat
Localhost
LogMeIn Hamachi
MAC-cím
Magánhálózat
Manchesteri kódolás
Megjelenítési réteg
Modem
Munkamenet
Nagy kiterjedésű hálózat
OSI-modell
Pleziokron digitális hierarchia
Porttovábbítás
Repeater
Squid
Switch (informatika)
System Fault Tolerant
Számítógép-hálózat
Számítógépfürt
Szórási tartomány
Személyi hálózat
Szerver
Szinkron digitális hierarchia
Tűzfal (számítástechnika)
Time to Live
Token-Ring
Tokenbusz
Token busz
Unicast
UTP
Válogatás nélküli üzemmód
Városi hálózat
Varnish
Virtuális helyi hálózat
Virtuális magánhálózat
Windows Internet Name Service
X.25
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.