Kafes (grafik teorisi) - Cage (graph theory)
Gelen matematiksel alanında grafik teorisi , bir kafes , bir olan normal grafik birkaç olarak sahip köşeler onun için mümkün olduğunca çevresi .
Biçimsel olarak, bir ( R , g tanımlandığı -graph) her köşe tam olduğu bir grafik olduğu r komşuları, ve burada en kısa devir tam uzunluğa sahip gr . Bir ( R , g ) -cage bir (bir R , g Tüm (arasında köşe mümkün olan en az sayıda) -graph, R , g ) -graphs. Bir (3, g ) -cage genellikle g- kafesi olarak adlandırılır .
R ≥ 2 ve g ≥ 3'ün herhangi bir kombinasyonu için bir ( r , g ) -grafının mevcut olduğu bilinmektedir. Tüm ( r , g ) -kafeslerinin var olduğu sonucu çıkar.
Derece r ve çevresi g olan bir Moore grafiği varsa , bu bir kafes olmalıdır. Dahası, Moore grafiklerinin boyutlarındaki sınırlar kafeslere genellenir: tek çevresi g olan herhangi bir kafes en azından
köşeler ve çevresi g olan herhangi bir kafes en azından
köşeler. Tam olarak bu kadar köşeye sahip herhangi bir ( r , g ) -graf, tanımı gereği bir Moore grafiğidir ve bu nedenle otomatik olarak bir kafestir.
Belirli bir r ve g kombinasyonu için birden fazla kafes olabilir . Örneğin, her biri 70 köşeli üç izomorfik olmayan (3,10) kafes vardır : Balaban 10 kafesi , Harries grafiği ve Harries – Wong grafiği . Ancak yalnızca bir (3,11) kafesi vardır: Balaban 11 kafesi (112 köşeli).
Bilinen kafesler
1 düzenli grafiğin döngüsü yoktur ve bağlı 2 düzenli grafiğin çevresi köşe sayısına eşittir, bu nedenle kafesler yalnızca r ≥ 3 için ilgi çekicidir . ( R , 3) kafesi tam bir grafiktir K r +1 ile r + 1 köşeler ve ( r, bir -cage olduğu, 4) tam ikili grafik K r , r, 2 r köşe.
Önemli kafesler şunları içerir:
- (3,5) -cage: Petersen grafiği , 10 köşe
- (3,6) -cage: Heawood grafiği , 14 köşe
- (3,8) -cage: Tutte – Coxeter grafiği , 30 köşe
- (3,10) -cage: Balaban 10 kafesi , 70 köşe
- (3,11) -cage: Balaban 11 kafesi , 112 köşesi
- (4,5) -cage: Robertson grafiği , 19 köşe
- (7,5) -cage: Hoffman-Singleton grafiği , 50 köşe.
- Tüm r 1 - bir ana güç, ( R , 6) kafesleri sıklığı grafiklerdir yansıtmalı düzlemlerde .
- Tüm r 1 - bir ana güç, ( R , 8) ve ( R , 12) kafes olan poligonlar genelleştirilmiş .
Yansıtmalı düzlemler ve genelleştirilmiş çokgenler dışındaki bilinen ( r , g ) kafeslerdeki r > 2 ve g > 2 değerleri için köşe sayısı:
|
g
r
|
3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
| 4 | 5 | 8 | 19 | 26 | 67 | 80 | 728 | |||
| 5 | 6 | 10 | 30 | 42 | 170 | 2730 | ||||
| 6 | 7 | 12 | 40 | 62 | 312 | 7812 | ||||
| 7 | 8 | 14 | 50 | 90 |
Asimptotik
Büyük g değerleri için , Moore bağı, n sayısının g'nin bir fonksiyonu olarak en azından üstel olarak tek başına büyümesi gerektiğini ifade eder . Eşdeğer olarak, g en fazla n'nin logaritması ile orantılı olabilir . Daha kesin,
Bu sınırın sıkı veya sıkıya yakın olduğuna inanılmaktadır ( Bollobás & Szemerédi 2002 ). G üzerindeki en iyi bilinen alt sınırlar da logaritmiktir, ancak daha küçük bir sabit faktörle ( n'nin tek başına üssel olarak ancak Moore sınırından daha yüksek bir oranda büyüdüğünü gösterir). Spesifik olarak, inşaat Ramanujan grafikleri ile tanımlanan Lubotzky, Phillips ve Sarnak (1988) bağlı tatmin
Bu sınır , Lazebnik, Ustimenko & Woldar (1995) tarafından biraz geliştirildi .
Bu grafiklerin kendilerinin kafes olmaları pek olası değildir, ancak bunların varlığı, bir kafeste ihtiyaç duyulan köşe sayısına bir üst sınır verir.
Referanslar
- Biggs, Norman (1993), Cebirsel Grafik Teorisi (2. baskı), Cambridge Matematik Kitaplığı, s. 180–190, ISBN 0-521-45897-8 .
- Bollobás, Béla ; Szemerédi, Endre (2002), "Seyrek grafiklerin çevresi ", Journal of Graph Theory , 39 (3): 194–200, doi : 10.1002 / jgt.10023 , MR 1883596 .
- Exoo, G; Jajcay, R (2008), "Dinamik Cage Araştırması" , Dinamik Araştırmaları, Kombinatorik Elektronik Dergisi , DS16 , arşivlenmiş orijinal 2015-01-01 tarihinde , alınan 2012-03-25 .
- Erdős, Paul ; Rényi, Alfréd ; Sós, Vera T. (1966), "Grafik teorisi sorunu üzerine" (PDF) , Studia Sci. Matematik. Hungar. , 1 : 215-235, arşivlenmiş orijinal (PDF) 2016-03-09 tarihinde , alınan 2010-02-23 .
- Hartsfield, Nora ; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction , Academic Press, pp. 77–81 , ISBN 0-12-328552-6 .
- Holton, DA; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , s. 183–213, ISBN 0-521-43594-3 .
- Lazebnik, F .; Ustimenko, VA; Woldar, AJ (1995), "Yüksek çevrenin yeni bir yoğun grafikleri serisi", Amerikan Matematik Derneği Bülteni , Yeni Seri, 32 (1): 73–79, arXiv : math / 9501231 , doi : 10.1090 / S0273- 0979-1995-00569-0 , MR 1284775 .
- Lubotzky, A .; Phillips, R .; Sarnak, P. (1988), "Ramanujan grafikleri", Combinatorica , 8 (3): 261–277, doi : 10.1007 / BF02126799 , MR 0963118 .
- Tutte, WT (1947), "Bir kübik grafik ailesi", Proc. Cambridge Philos. Soc. , 43 (4): 459–474, Bibcode : 1947PCPS ... 43..459T , doi : 10.1017 / S0305004100023720 .