Tam grafik - Complete graph - Wikipedia

Tam grafik
Tam grafik K7.svg
K77 köşeli tam bir grafik
Tepe noktaların
Kenarlar
Yarıçap
Çap
Çevresi
Otomorfizmlern! (Sn)
Kromatik numaran
Kromatik dizin
  • n Eğer n garip
  • n − 1 Eğer n eşit
Spektrum
Özellikleri
GösterimKn
Grafikler ve parametreler tablosu

İçinde matematiksel alanı grafik teorisi, bir tam grafik bir basit yönsüz grafik her çiftin farklı olduğu köşeler benzersiz bir kenar. Bir tam dijital grafik bir Yönlendirilmiş grafik her bir farklı köşe çiftinin bir çift benzersiz kenarla (her bir yönde bir tane) birbirine bağlandığı.

Grafik teorisinin kendisi tipik olarak Leonhard Euler 'nin 1736 çalışması Königsberg'in Yedi Köprüsü. Ancak, çizimler köşeleri bir noktasının üzerine yerleştirilmiş tam grafiklerin normal çokgen, 13. yüzyılda çoktan ortaya çıktı. Ramon Llull.[1] Böyle bir çizime bazen bir mistik gül.[2]

Özellikleri

Tam grafik n köşeler ile gösterilir Kn. Bazı kaynaklar, bu gösterimdeki K harfinin Almanca kelimeyi temsil ettiğini iddia ediyor komplett,[3] ama tam bir grafik için Almanca adı, vollständiger Grafiği, K harfini içermez ve diğer kaynaklar, gösterimin katkılarını onurlandırdığını belirtir. Kazimierz Kuratowski teori grafiğine.[4]

Kn vardır n(n − 1)/2 kenarlar (bir üçgen sayı ) ve bir normal grafik nın-nin derece n − 1. Tüm tam grafikler kendilerine aittir azami klikler. Onlar maksimum bağlı tek olarak köşe kesimi Grafiğin bağlantısını kesen, tam köşe kümesidir. tamamlayıcı grafik tam bir grafiğin boş grafik.

Tam bir grafiğin kenarlarının her birine bir oryantasyon, sonuç Yönlendirilmiş grafik denir turnuva.

Kn ayrıştırılabilir n ağaçlar Tben öyle ki Tben vardır ben köşeler.[5] Ringel'in varsayımı, grafiğin tamamının K2n+1 herhangi bir ağacın kopyalarına ayrıştırılabilir n kenarlar.[6] Bunun yeterince büyük olduğu bilinmektedir. n.[7][8]

Sayısı eşleşmeler grafiklerin tamamı, Telefon numaraları

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (sıra A000085 içinde OEIS ).

Bu sayılar, olası en büyük değeri verir Hosoya endeksi bir ... için n-vertex grafiği.[9] Sayısı mükemmel eşleşmeler tam grafiğin Kn (ile n bile) tarafından verilir çift ​​faktörlü (n − 1)!!.[10]

geçiş numaraları kadar K27 ile bilinmektedir K28 7233 veya 7234 geçiş gerektirir. Diğer değerler, Doğrusal Geçiş Sayısı projesi tarafından toplanır.[11] Doğrusal Geçiş sayıları Kn vardır

0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (sıra A014540 içinde OEIS ).

Geometri ve topoloji

Düğümleri temsil eden köşeleri olan etkileşimli Csaszar çokyüzlü modeli. İçinde SVG resmi, döndürmek için fareyi hareket ettirin.[12]

İle tam bir grafik n düğümler, bir (n − 1)-basit. Geometrik olarak K3 bir kenar kümesini oluşturur üçgen, K4 a dörtyüzlü vb. Császár çokyüzlü, bir topolojisine sahip konveks olmayan bir çokyüzlü simit, tam grafiğe sahip K7 onun gibi iskelet. Her komşu politop dört veya daha fazla boyutta da tam bir iskelete sahiptir.

K1 vasıtasıyla K4 hepsi düzlemsel grafikler. Ancak, beş veya daha fazla köşeli tam bir grafiğin her düzlemsel çizimi bir kesişme ve düzlemsel olmayan tam grafik içermelidir. K5 düzlemsel grafiklerin karakterizasyonlarında anahtar rol oynar: Kuratowski teoremi, bir grafik düzlemseldir ancak ve ancak hiçbirini içermiyorsa K5 ne de tam iki parçalı grafik K3,3 bir alt bölüm olarak ve Wagner teoremi aynı sonuç için de geçerlidir küçük grafik alt bölümlerin yerine. Bir parçası olarak Petersen ailesi, K6 şunlardan biri ile benzer bir rol oynar: yasak küçükler için bağlantısız yerleştirme.[13] Başka bir deyişle, Conway ve Gordon olarak[14] kanıtlanmış, her yerleştirme K6 üç boyutlu uzaya, en az bir çift bağlantılı üçgen ile içsel olarak bağlıdır. Conway ve Gordon ayrıca herhangi bir üç boyutlu yerleştirmenin K7 içerir Hamilton döngüsü uzayda gömülü olan önemsiz düğüm.

Örnekler

Tam grafikler n köşeler için n 1 ile 12 arasında, kenar sayılarıyla birlikte aşağıda gösterilmiştir:

K1: 0K2: 1K3: 3K4: 6
Tam grafik K1.svgTam grafik K2.svgTam grafik K3.svg3-tek yönlü grafik.svg
K5: 10K6: 15K7: 21K8: 28
4-tek yönlü grafik.svg5-tek yönlü grafik.svg6-tek yönlü grafik.svg7-tek yönlü grafik.svg
K9: 36K10: 45K11: 55K12: 66
8-tek yönlü grafik.svg9-tek yönlü grafik.svg10-tek yönlü grafik.svg11-tek yönlü grafik.svg

Ayrıca bakınız

Referanslar

  1. ^ Knuth, Donald E. (2013), "İki bin yıllık kombinatorik", Wilson, Robin; Watkins, John J. (editörler), Kombinatorik: Eski ve ModernOxford University Press, s. 7-37, ISBN  978-0191630620.
  2. ^ Mistik Gül, nrich.maths.org, alındı 23 Ocak 2012.
  3. ^ Gries, David; Schneider, Fred B. (1993), Ayrık Matematiğe Mantıksal Bir Yaklaşım Springer-Verlag, s. 436, ISBN  0387941150.
  4. ^ Pirnot, Thomas L. (2000), Her Yerde Matematik, Addison Wesley, s.154, ISBN  9780201308150.
  5. ^ Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). "Sınırlandırılmış dereceli ağaçların optimum paketlenmesi" (PDF). Avrupa Matematik Derneği Dergisi. 21 (12): 3573–3647. doi:10.4171 / JEMS / 909. ISSN  1435-9855.
  6. ^ Ringel, G. (1963). Grafik Teorisi ve Uygulamaları. Smolenice Sempozyum Bildirileri.
  7. ^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020-01-08). "Ringel'in Varsayımının Kanıtı". arXiv:2001.02665 [math.CO ].
  8. ^ Hartnett, Kevin. "Gökkuşağı Kanıtı Grafiklerin Tektip Parçalara Sahip Olduğunu Gösterir". Quanta Dergisi. Alındı 2020-02-20.
  9. ^ Tichy, Robert F .; Wagner, Stephan (2005), "Kombinatoryal kimyada topolojik endeksler için aşırı sorunlar" (PDF), Hesaplamalı Biyoloji Dergisi, 12 (7): 1004–1013, CiteSeerX  10.1.1.379.8693, doi:10.1089 / cmb.2005.12.1004, PMID  16201918.
  10. ^ Callan, David (2009), Çift faktörlü kimliklerin kombinatoryal bir incelemesi, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.
  11. ^ Oswin Aichholzer. "Doğrusal Geçiş Numarası projesi". Arşivlenen orijinal 2007-04-30 tarihinde.
  12. ^ Ákos Császár, Köşegenleri Olmayan Çokyüzlü. Arşivlendi 2017-09-18 de Wayback Makinesi, Bolyai Enstitüsü, Szeged Üniversitesi, 1949
  13. ^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Grafiklerin 3 boşlukta bağlantısız yerleştirilmesi", Amerikan Matematik Derneği Bülteni, 28 (1): 84–89, arXiv:math / 9301216, doi:10.1090 / S0273-0979-1993-00335-5, BAY  1164063.
  14. ^ Conway, J. H.; Cameron Gordon (1983). "Uzamsal Grafiklerdeki Düğümler ve Bağlantılar". J. Grafik Th. 7 (4): 445–453. doi:10.1002 / jgt.3190070410.

Dış bağlantılar