Stała Cheegera (teoria grafów)

Ten artykuł dotyczy stałej Cheegera w teorii grafów. Aby zapoznać się z innym zastosowaniem w geometrii Riemanna, zobacz Stała Cheegera .

W matematyce stała Cheegera ( również liczba Cheegera lub liczba izoperymetryczna ) wykresu jest liczbową miarą tego , czy wykres ma „wąskie gardło”. Stała Cheegera jako miara „wąskich gardeł” jest bardzo interesująca w wielu dziedzinach: na przykład przy konstruowaniu dobrze połączonych sieci komputerów , tasowaniu kart . Pojęcie teoretyczne grafów wywodzi się ze stałej izoperymetrycznej Cheegera zwartej rozmaitości Riemanna .

Stała Cheegera nosi imię matematyka Jeffa Cheegera .

Definicja

Niech G będzie nieskierowanym grafem skończonym ze zbiorem wierzchołków V ( G ) i zbiorem krawędzi E ( G ) . Dla zbioru wierzchołków A ⊆ V ( G ) niech ∂ A oznacza zbiór wszystkich krawędzi przechodzących od wierzchołka w A do wierzchołka na zewnątrz A (czasami nazywanego granicą krawędzi A ) :

${\ Displaystyle \ częściowe A: = \ {\ {x, y \} \ w E (G) \: \ x \ w A, y \ w V (G) \ setminus A \}.}$

Zauważ, że krawędzie są nieuporządkowane, tj. ${\ Displaystyle \ {x, y \} = \ {y, x \}}$ . Stała Cheegera G , oznaczona h ( G ) , jest zdefiniowana przez

${\ Displaystyle h (G): = \ min \ lewo \ {{\ Frac {|\ częściowe A|}{|A|}} \: \ A \ subseteq V (G), 0 <| A |\ równoważnik { \tfrac {1}{2}}|V(G)|\prawo\}.}$

Stała Cheegera jest ściśle dodatnia wtedy i tylko wtedy, gdy G jest grafem spójnym . Intuicyjnie, jeśli stała Cheegera jest mała, ale dodatnia, istnieje „wąskie gardło” w tym sensie, że istnieją dwa „duże” zestawy wierzchołków z „niewieloma” połączeniami (krawędziami) między nimi. Stała Cheegera jest „duża”, jeśli jakikolwiek możliwy podział zbioru wierzchołków na dwa podzbiory ma „wiele” powiązań między tymi dwoma podzbiorami.

Przykład: sieć komputerowa

Układ sieci pierścieniowej

W zastosowaniach do informatyki teoretycznej chce się opracować konfiguracje sieci, dla których stała Cheegera jest wysoka (przynajmniej ograniczona od zera), nawet gdy | V ( G )| (liczba komputerów w sieci) jest duża.

Rozważmy na przykład sieć pierścieniową N ≥ 3 komputerów, uważaną za _graf GN . Ponumeruj komputery 1, 2, ..., N zgodnie z ruchem wskazówek zegara wokół pierścienia. Matematycznie zestaw wierzchołków i zestaw krawędzi są określone przez:

${\ Displaystyle {\ rozpocząć {wyrównane} 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{ wyrównany}}}$

Weź A za zbiór tych komputerów w połączonym łańcuchu ${\ Displaystyle \ lewo \ lfloor {\ tfrac {N} {2}} \ right \ rfloor}$

${\ Displaystyle A = \ lewo \ {1,2, \ cdots, \ lewo \ lfloor {\ tfrac {N} {2}} \ prawo \ rfloor \ prawo \}.}$

Więc,

${\ Displaystyle \ częściowe A = \ lewo \ {\ lewo \ {\ lewo \ lfloor {\ tfrac {N} {2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}$

I

${\ Displaystyle {\ Frac {|\ częściowe A|}{|A|}} = {\ Frac {2} {\ lewo \ lfloor {\ tfrac {N} {2}} \ prawo \ rfloor}} \ do 0 {\mbox{ as }}N\do \infty .}$

Ten przykład przedstawia górną granicę dla stałej Cheegera h ( GN _. ) , która również dąży do zera jako N → ∞ W związku z tym uznalibyśmy sieć pierścieniową za wysoce „wąskie gardło” dla dużego N , a to jest wysoce niepożądane w praktyce. Wystarczyłoby, aby jeden z komputerów w pierścieniu uległ awarii, a wydajność sieci zostałaby znacznie zmniejszona. Gdyby dwa niesąsiadujące ze sobą komputery uległy awarii, sieć podzieliłaby się na dwa odłączone komponenty.

Nierówności Cheegera

Stała Cheegera jest szczególnie ważna w kontekście grafów ekspanderów , ponieważ jest sposobem mierzenia ekspansji krawędzi wykresu. Tak zwane nierówności Cheegera wiążą lukę wartości własnej wykresu z jego stałą Cheegera. Bardziej wyraźnie

${\ Displaystyle 2h (G) \ geq \ lambda \ geq {\ Frac {h ^ {2} (G)} {2 \ Delta (G) )}}}$

gdzie $jest$ maksymalnym stopniem węzłów w ${\ Displaystyle \ Delta (G)$ } $i$ jest macierzy Laplace'a wykresu . Nierówność Cheegera jest fundamentalnym wynikiem i motywacją dla teorii grafów widmowych .

Zobacz też

• Teoria grafów widmowych
• Łączność algebraiczna
• Związany z Cheegerem
• Przewodność (wykres)
• Łączność (teoria grafów)
• Wykres ekspandera

•   Donetti, L.; Neri, F. i Muñoz, M. (2006). „Optymalne topologie sieci: ekspandery, klatki, grafy Ramanujana, sieci splątane i tak dalej”. J. Stat. Mech . 2006 (8): P08007. arXiv : cond-mat/0605565 . Bibcode : 2006JSMTE..08..007D . doi : 10.1088/1742-5468/2006/08/P08007 . S2CID 16192273 .
•   Lackenby, M. (2006). „Podziały Heegaarda, praktycznie przypuszczenie Hakena i właściwość (τ)” . Wynaleźć. matematyka _ 164 (2): 317–359. arXiv : matematyka/0205327 . Bibcode : 2006InMat.164..317L . doi : 10.1007/s00222-005-0480-x . S2CID 12847770 .