Cheeger sabiti (grafik teorisi) - Cheeger constant (graph theory)

Gelen matematik , Cheeger sabiti (aynı zamanda Cheeger numarası veya Kümenin sayısı a) grafiğinde bir grafiktir, bir "darboğaz" olup olmadığını sayısal bir ölçüsüdür. "Darboğazlığın" bir ölçüsü olarak Cheeger sabiti birçok alanda büyük ilgi görüyor: örneğin, iyi bağlanmış bilgisayar ağları oluşturmak , kart karıştırmak . Grafik teorik kavram ve akabinde oluşan Cheeger Kümenin sabit bir bölgesinin kompakt Riemann manifoldu .

Cheeger sabiti, matematikçi Jeff Cheeger'in adını almıştır .

Tanım

G , köşe kümesi V ( G ) ve kenar kümesi E ( G ) olan yönsüz bir sonlu grafik olsun . Köşelerin bir toplama için bir ⊆ V ( G ) , izin ∂ bir göstermektedirler bir tepe giden tüm kenarların toplama A 'lik bir tepe dışarıya A (bazen kenar sınır bölgesinin A ):

${\ displaystyle \ kısmi A: = \ {\ {x, y \} \, E (G) \: \ x \ içinde, V (G) \ setminus A \} içinde y \.}$

Kenarların sırasız olduğuna dikkat edin, yani . Cheeger sabit bölgesinin G ile gösterilen h ( G ) , ile tanımlanır ${\ displaystyle \ {x, y \} = \ {y, x \}}$

${\ displaystyle h (G): = \ min \ sol \ {{\ frac {| \ kısmi A |} {| A |}} \: \ A \ subseteq V (G), 0 <| A | \ leq { \ tfrac {1} {2}} | V (G) | \ sağ \}.}$

Cheeger sabit kesinlikle pozitiftir , ancak ve ancak G, a, bağlı grafiktir . Sezgisel olarak, Cheeger sabiti küçük ama pozitifse, aralarında "birkaç" bağlantı (kenar) bulunan iki "büyük" köşe kümesi olması anlamında bir "darboğaz" vardır. Cheeger sabiti, iki alt kümeye ayarlanan tepe noktasının olası herhangi bir bölümü, bu iki alt küme arasında "birçok" bağlantıya sahipse "büyüktür".

Örnek: bilgisayar ağı

Halka ağ düzeni

Teorik bilgisayar bilimi uygulamalarında, Cheeger sabitinin yüksek olduğu (en azından sıfırdan uzaklaştığı için) ağ yapılandırmaları tasarlamak istenir | V ( G ) | (ağdaki bilgisayar sayısı) büyük.

Örneğin, bir G _N grafiği olarak düşünülen N ≥ 3 bilgisayardan oluşan bir halka ağ düşünün . Halkanın etrafında saat yönünde 1, 2, ..., N bilgisayarları numaralandırın . Matematiksel olarak, köşe kümesi ve kenar kümesi şu şekilde verilir:

${\ displaystyle {\ başla {hizalı} V (G_ {N}) & = \ {1,2, \ cdots, N-1, N \} \\ E (G_ {N}) & = {\ büyük \ { } \ {1,2 \}, \ {2,3 \}, \ cdots, \ {N-1, N \}, \ {N, 1 \} {\ büyük \}} \ end {hizalı}}}$

A'yı bağlı bir zincirdeki bu bilgisayarların bir koleksiyonu olarak alın : ${\ displaystyle \ sol \ lfloor {\ tfrac {N} {2}} \ sağ \ rfloor}$

${\ displaystyle A = \ sol \ {1,2, \ cdots, \ sol \ lfloor {\ tfrac {N} {2}} \ sağ \ rfloor \ sağ \}.}$

Yani,

${\ displaystyle \ kısmi A = \ sol \ {\ sol \ {\ sol \ lfloor {\ tfrac {N} {2}} \ sağ \ rfloor, \ sol \ lfloor {\ tfrac {N} {2}} \ sağ \ rfloor +1 \ sağ \}, \ {N, 1 \} \ sağ \},}$

ve

${\ displaystyle {\ frac {| \ kısmi A |} {| A |}} = {\ frac {2} {\ sol \ lfloor {\ tfrac {N} {2}} \ sağ \ rfloor}} \ ila 0 {\ mbox {as}} N \ ila \ infty.}$

Bu örnek, Cheeger sabiti h ( G _N ) için bir üst sınır sağlar , bu da N → ∞ olarak sıfıra meyillidir . Sonuç olarak, bir halka ağını büyük N için oldukça "darboğazlı" olarak kabul edeceğiz ve bu pratik açıdan oldukça istenmeyen bir durumdur. Başarısız olmak için halkadaki bilgisayarlardan yalnızca birine ihtiyacımız olacak ve ağ performansı büyük ölçüde azalacaktı. Bitişik olmayan iki bilgisayar arızalanırsa, ağ bağlantısı kesilen iki bileşene bölünür.

Cheeger Eşitsizlikleri

Cheeger sabiti, bir grafiğin kenar genişlemesini ölçmenin bir yolu olduğu için özellikle genişletici grafikler bağlamında önemlidir . Sözde Cheeger eşitsizlikleri , bir grafiğin Özdeğer boşluğunu Cheeger sabiti ile ilişkilendirir. Daha açık bir şekilde

${\ displaystyle 2h (G) \ geq \ lambda \ geq {\ frac {h ^ {2} (G)} {2 \ Delta (G)}}}$

burada düğümlerin en yüksek derece ve bir spektral aralık içinde Laplace matris grafiğinin. ${\ displaystyle \ Delta (G)}$${\ displaystyle G}$${\ displaystyle \ lambda}$

Ayrıca bakınız

• Cebirsel bağlantı
• Cheeger bağlı
• İletkenlik (grafik)
• Bağlantı (grafik teorisi)
• Genişletici grafik

Referanslar

• Donetti, L .; Neri, F. & Muñoz, M. (2006). "Optimal ağ topolojileri: genişleticiler, kafesler, Ramanujan grafikleri, dolaşık ağlar ve hepsi". J. Stat. Mech . 2006 (08): P08007. arXiv : koşullu / 0605565 . Bibcode : 2006JSMTE..08..007D . doi : 10.1088 / 1742-5468 / 2006/08 / P08007 .
• Lackenby, M. (2006). "Heegaard bölünmeleri, neredeyse Haken varsayımı ve özelliği (τ)". İcat etmek. Matematik . 164 (2): 317–359. arXiv : matematik / 0205327 . Bibcode : 2006InMat.164..317L . doi : 10.1007 / s00222-005-0480-x .