Cheegerova konstanta (teorie grafů) - Cheeger constant (graph theory)

v matematika, Cheegerova konstanta (taky Cheegerovo číslo nebo izoperimetrické číslo) a graf je číselná míra toho, zda má graf „úzké místo“. Cheegerova konstanta jako měřítko „úzkého profilu“ má velký zájem v mnoha oblastech: například budování dobře propojených počítačové sítě, míchání karet. Teoretická představa grafu vznikla po Cheegerova izoperimetrická konstanta a kompaktní Riemannovo potrubí.

Cheegerova konstanta je pojmenována po matematik Jeff Cheeger.

Definice

Nechat $G$ být nepřímým konečným grafem se sadou vrcholů $PROTI (G)$ a okrajová sada $E (G)$ . Pro sbírku vrcholů $A \subseteq PROTI (G)$ , nechť $\partial A$ označuje souhrn všech hran vycházejících z vrcholu dovnitř $A$ na vrchol mimo $A$ (někdy nazývaný hraniční hranice z $A$ ):

{ displaystyle částečné A: = { {x, y } v E (G) : x v A, y ve V (G) setminus A }.}

Všimněte si, že okraje jsou neuspořádané, tj. ${ displaystyle {x, y } = {y, x }}$ . The Cheegerova konstanta z $G$ , označeno $h (G)$ , je definováno^[1]

{ displaystyle h (G): = min vlevo {{ frac {| částečné A |} {| A |}} : A subseteq V (G), 0 <| A | leq { tfrac {1} {2}} | V (G) | vpravo }.}

Cheegerova konstanta je přísně pozitivní kdyby a jen kdyby $G$ je připojený graf. Pokud je intuitivně Cheegerova konstanta malá, ale pozitivní, existuje „úzké místo“ v tom smyslu, že existují dvě „velké“ sady vrcholů s „několika“ odkazy (hranami) mezi nimi. Cheegerova konstanta je „velká“, pokud jakékoli možné rozdělení sady vrcholů do dvou podmnožin má „mnoho“ vazeb mezi těmito dvěma podmnožinami.

Příklad: počítačové sítě

Rozvinout rozložení sítě

V aplikacích pro teoretickou informatiku si přejeme navrhnout síťové konfigurace, pro které je Cheegerova konstanta vysoká (alespoň ohraničená od nuly), i když $| PROTI (G)|$ (počet počítačů v síti) je velký.

Zvažte například a kruhová síť z $N \geq 3$ počítače, považovány za graf $G N$ . Počet počítačů $1, 2, ..., N$ ve směru hodinových ručiček kolem kruhu. Matematicky je množina vrcholů a množina hran dána vztahem:

{ displaystyle { begin {zarovnáno} V (G_ {N}) & = {1,2, cdots, N-1, N } E (G_ {N}) & = { big { } {1,2 }, {2,3 }, cdots, {N-1, N }, {N, 1 } { big }} end {zarovnáno}}}

Vzít $A$ být sbírkou ${ displaystyle left lfloor { tfrac {N} {2}} right rfloor}$ z těchto počítačů v připojeném řetězci:

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

Tak,

{ displaystyle částečné A = levý { levý { levý lfloor { tfrac {N} {2}} pravý rfloor, levý lfloor { tfrac {N} {2}} pravý rfloor +1 right }, {N, 1 } right },}

a

{ displaystyle { frac {| částečné A |} {| A |}} = { frac {2} { left lfloor { tfrac {N} {2}} right rfloor}} na 0 { mbox {as}} N do infty.}

Tento příklad poskytuje horní mez pro Cheegerovu konstantu $h (G N)$ , který také inklinuje k nule jako $N \to \infty$ . Následně bychom kruhovou síť považovali za vysoce „zúženou“ pro velkou síť $N$ , a to je z praktického hlediska vysoce nežádoucí. Potřebovali bychom, aby selhal pouze jeden z počítačů v kruhu, a výkon sítě by se výrazně snížil. Pokud by selhaly dva nesousedící počítače, síť by se rozdělila na dvě odpojené komponenty.

Cheegerovy nerovnosti

Cheegerova konstanta je zvláště důležitá v kontextu expandérové grafy protože jde o způsob měření okrajové expanze grafu. Takzvaný Cheegerovy nerovnosti spojit mezeru vlastních čísel grafu s jeho Cheegerovou konstantou. Přesněji řečeno

{ displaystyle 2h (G) geq lambda geq { frac {h ^ {2} (G)} {2d_ {MAX} (G)}}}

ve kterém ${ displaystyle d_ {MAX} (G)}$ je maximální stupeň pro uzly v ${ displaystyle G}$ a ${ displaystyle lambda}$ je spektrální mezera z Laplaciánská matice grafu.^[2]

Viz také

Reference

^ Mohar, Bojan (Prosinec 1989). Msgstr "Izoperimetrický počet grafů". Journal of Combinatorial Theory, Series B. 47 (3): 274–291. doi:10.1016/0095-8956(89)90029-4. hdl:10338.dmlcz / 128408.
^ Černá Hora, Ravi; Tetali, Prasad (2006). "Matematické aspekty směšovacích časů v markovských řetězcích". Nalezeno. Teorie trendů. Comput. Sci: 90–94. Citovat deník vyžaduje | deník = (Pomoc)

Donetti, L .; Neri, F. a Muñoz, M. (2006). „Optimální topologie sítě: expandéry, klece, grafy Ramanujan, zapletené sítě a vše ostatní“. J. Stat. Mech. 2006 (08): P08007. arXiv:cond-mat / 0605565. Bibcode:2006JSMTE..08..007D. doi:10.1088 / 1742-5468 / 2006/08 / P08007.
Lackenby, M. (2006). „Heegaardova štěpení, prakticky Hakenova domněnka a vlastnost (τ)“. Vymyslet. Matematika. 164 (2): 317–359. arXiv:matematika / 0205327. Bibcode:2006InMat.164..317L. doi:10.1007 / s00222-005-0480-x.

[1] Mohar, Bojan (Prosinec 1989). Msgstr "Izoperimetrický počet grafů". Journal of Combinatorial Theory, Series B. 47 (3): 274–291. doi:10.1016/0095-8956(89)90029-4. hdl:10338.dmlcz / 128408.

[2] Černá Hora, Ravi; Tetali, Prasad (2006). "Matematické aspekty směšovacích časů v markovských řetězcích". Nalezeno. Teorie trendů. Comput. Sci: 90–94. Citovat deník vyžaduje | deník = (Pomoc)

[1]

[2]