Üçgensiz grafik - Triangle-free graph
Olarak matematiksel alan grafik teorisi , bir üçgen içermeyen grafik bir üç köşe bir formu olduğu bir yönsüz grafiktir üçgen kenarlarının. Üçgensiz grafikler, klik sayısı ≤ 2 olan grafikler, çevresi ≥ 4 olan grafikler, indüklenmiş 3 döngü içermeyen grafikler veya yerel olarak bağımsız grafikler olarak eşdeğer şekilde tanımlanabilir .
Tarafından turan teoremi , n kenarlarının en fazla olan -vertex üçgen içermeyen grafiği olan tam ikili grafik bipartition her bir tarafında köşe sayısı mümkün olduğu kadar eşit olarak olduğu.
Üçgen bulma sorunu
Üçgen bulma problemi, bir grafiğin üçgensiz olup olmadığını belirleme problemidir. Grafik bir üçgen içerdiğinde, grafikte bir üçgen oluşturan üç köşeyi çıktılamak için genellikle algoritmalar gerekir.
m kenarlı bir grafiğin O( m 1.41 ) zamanında üçgensiz olup olmadığını test etmek mümkündür . Diğer bir yaklaşım, bulmaktır iz bir A 3 , bir olduğu komşuluk matrisi grafik. Sadece ve sadece grafik üçgensiz ise iz sıfırdır. İçin yoğun grafikler , dayanır, bu basit bir algoritma kullanmak daha etkilidir matris çarpımı bu O (zamanı karmaşıklığı aşağı alır, çünkü n 2.373 ), burada n, köşe sayısıdır.
Imrich, Klavžar & Mulder'ın (1999) gösterdiği gibi , üçgensiz graf tanıma karmaşıklık bakımından medyan graf tanımaya eşdeğerdir ; bununla birlikte, medyan grafik tanıma için mevcut en iyi algoritmalar, tersi yerine üçgen algılamayı bir alt program olarak kullanır.
Karar ağacı karmaşıklığı veya sorgu karmaşıklık sorguları depolayan bir grafik komşuluk matrisi bir oracle olan bir sorun, ve, Θ olan ( n- 2 ). Bununla birlikte, kuantum algoritmaları için en iyi bilinen alt sınır Ω( n )'dir, ancak en iyi bilinen algoritma O( n 5/4 )'dir.
Bağımsızlık sayısı ve Ramsey teorisi
Bir bağımsız ayar √ arasında , n bir in köşe N -vertex üçgen içermeyen grafik bulmak kolaydır: iki fazla √ bir tepe vardır , n komşu (ki bu durumda bu komşu bağımsız grubu iken) ya da tüm köşe az olması √ n komşu (bu durumda herhangi bir maksimum bağımsız kümenin en az √ n köşesi olmalıdır). Bu sınır biraz daraltılabilir: üçgensiz her grafikte bağımsız bir köşeler kümesi vardır ve bazı üçgensiz grafiklerde her bağımsız kümenin köşeleri vardır. Tüm bağımsız kümelerin küçük olduğu üçgensiz grafikler oluşturmanın bir yolu, bir üçgeni tamamlamayan rastgele seçilmiş kenarları art arda ekleyerek maksimum üçgen içermeyen bir grafik oluşturan üçgensiz işlemdir . Yüksek olasılıkla, bu işlem bağımsızlık sayısına sahip bir grafik üretir . Aynı özelliklere sahip düzenli grafikler bulmak da mümkündür .
Bu sonuçlar aynı zamanda şu şekildeki Ramsey sayıları R(3, t ) üzerinde asimptotik sınırlar verdiği şeklinde yorumlanabilir : eğer tam bir grafiğin köşeleri kırmızı ve mavi renkliyse, o zaman kırmızı grafik bir üçgen içeriyorsa veya üçgen içermez, o zaman mavi grafikte aynı boyutta bir kliğe karşılık gelen bağımsız bir t boyutu kümesine sahip olmalıdır .
Üçgen içermeyen grafikleri boyama
Üçgensiz grafiklerle ilgili pek çok araştırma, grafik renklendirmeye odaklanmıştır . Her iki parçalı grafik (yani, her 2 renklendirilebilir grafik) üçgen içermez ve Grötzsch teoremi , her üçgensiz düzlemsel grafiğin 3 renkli olabileceğini belirtir . Ancak, düzlemsel olmayan üçgen içermeyen grafikler üçten fazla renk gerektirebilir.
Rastgele yüksek kromatik sayıya sahip üçgensiz grafiklerin ilk yapısı Tutte'den ( Blanche Descartes olarak yazıyor ) kaynaklanmaktadır. Bu yapı tek bir tepe söz sahibi olan grafikten başladı ve indüktif inşa dan şöyle: let sahip köşeleri, sonra bir dizi çekmek ait köşeler ve her alt kümesi için bir boyutta bir ayrık kopyasını eklemek için ve katılmak bir eşleme ile. Gönderen güvercin yuvası prensibi o tümevarımsal aşağıdaki değildir setleri en az bir yana, renklendirilebilmesidir biz sadece kullanım k renklere izin verilmesi halinde monochromatically renkli olmalıdır. Mycielski (1955) , başka bir üçgen içermeyen grafikten yeni bir üçgen içermeyen grafik oluşturmak için şimdi Mycielskian olarak adlandırılan bir yapı tanımladı . Bir grafiğin kromatik sayısı k ise, Mycielskian'ının kromatik sayısı k + 1'dir, bu nedenle bu yapı, düzlemsel olmayan üçgensiz grafikleri renklendirmek için keyfi olarak çok sayıda renge ihtiyaç duyulabileceğini göstermek için kullanılabilir. Özellikle Mycielski'nin yapısının tekrar tekrar uygulanmasıyla oluşturulan 11 köşeli bir grafik olan Grötzsch grafiği , dörtten az renkle renklendirilemeyen üçgensiz bir grafiktir ve bu özelliğe sahip en küçük grafiktir. Gimbel & Thomassen (2000) ve Nilli (2000) , herhangi bir m kenarlı üçgen içermeyen grafiği renklendirmek için gereken renk sayısının
ve bu sınırla orantılı kromatik sayılara sahip üçgensiz grafikler var.
Üçgen içermeyen grafiklerde minimum derecede renklendirme ile ilgili çeşitli sonuçlar da vardır. Andrásfai, Erdős & Sós (1974) , her bir tepe noktasının 2'den fazla n /5 komşuya sahip olduğu herhangi bir n -köşesi üçgensiz grafiğin iki parçalı olması gerektiğini kanıtladı . Bu, bu türün olası en iyi sonucudur, çünkü 5-döngü üç renk gerektirir, ancak köşe başına tam olarak 2 n /5 komşuya sahiptir. Bu sonuçtan hareketle, Erdős & Simonovits (1973) , her bir tepe noktasının en az n /3 komşuya sahip olduğu herhangi bir n -köşesi üçgensiz grafiğin yalnızca üç renkle renklendirilebileceğini varsaymıştır ; bununla birlikte, Häggkvist (1981) , Grötzsch grafiğinin her bir köşesinin, dikkatlice seçilmiş bir boyutta bağımsız bir küme ile değiştirildiği bir karşı örnek bularak bu varsayımı çürütmüştür. Jin (1995) , her tepe noktasının 10'dan fazla n /29 komşusu olduğu herhangi bir n -köşe üçgensiz grafiğin 3-renklenebilir olması gerektiğini gösterdi; bu, bu türün olası en iyi sonucudur, çünkü Häggkvist'in grafiği dört renk gerektirir ve köşe başına tam olarak 10 n /29 komşuya sahiptir. Son olarak, Brandt & Thomassé (2006) , her bir tepe noktasının n /3'ten fazla komşuya sahip olduğu herhangi bir n -köşe üçgensiz grafiğin 4 renklendirilebilir olması gerektiğini kanıtladı . Hajnal , herhangi bir ε > 0 için keyfi olarak büyük kromatik sayı ve minimum derece (1/3 − ε) n olan üçgen içermeyen grafik örnekleri bulduğundan, bu türden ek sonuçlar mümkün değildir .
Ayrıca bakınız
- Andrásfai grafiği , çapı iki olan üçgen içermeyen dolaşım grafikleri ailesi
- Henson grafiği , indüklenmiş alt grafikler olarak tüm sonlu üçgen içermeyen grafikleri içeren sonsuz üçgensiz bir grafik
- Kaydırma grafiği , keyfi olarak yüksek kromatik sayıya sahip üçgen içermeyen bir grafik ailesi
- Kneser grafik üçgen ücretsiz ve renk sayısına sahip
- Monokromatik üçgen problemi, verilen bir grafiğin kenarlarını üçgen içermeyen iki grafiğe bölme problemi
- Her kenarın tam olarak bir üçgene ait olduğu grafiklerde Ruzsa-Szemerédi problemi
Referanslar
- Notlar
- Kaynaklar
- Alon, Noga ; Ben Şimon, Sonny; Krivelevich, Michael (2010), "Normal Ramsey grafikleri üzerine not", Journal of Graph Theory , 64 (3): 244–249, arXiv : 0812.2386 , doi : 10.1002/jgt.20453 , MR 2674496 , S2CID 1784886.
- Alon, N. ; Yuster, R.; Zwick, U. (1994), "Verilen uzunluk döngülerini bulma ve sayma", 2. Avrupa Algoritmalar Sempozyumu Bildiriler Kitabı, Utrecht, Hollanda , s. 354–364.
- Andrasfai, B.; Erdaş, P. ; Sós, VT (1974), "Kromatik sayı, maksimum klik ve bir grafiğin minimum derecesi arasındaki bağlantı üzerine" (PDF) , Discrete Mathematics , 8 (3): 205–218, doi : 10.1016/0012-365X(74) 90133-2.
- Belovs, Aleksandrs (2012), "Sabit boyutlu 1-sertifikalara sahip fonksiyonlar için yayılma programları", Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (STOC '12) , New York, NY, ABD: ACM, s. 77–84, arXiv : 1105.4024 , doi : 10.1145/2213977.2213985 , ISBN 978-1-4503-1245-5, S2CID 18771464.
- Bohman, Tom (2009), " Üçgensiz süreç", Matematikte Gelişmeler , 221 (5): 1653–1677, arXiv : 0806.4375 , doi : 10.1016/j.aim.2009.02.018 , MR 2522430 , S2CID 17701040.
- Boppana, Ravi; Halldórsson, Magnús M. (1992), "Alt grafikler hariç tutularak maksimum bağımsız kümelerin yaklaşıklaştırılması", BIT , 32 (2): 180–196, doi : 10.1007/BF01994876 , MR 1172185 , S2CID 123335474.
- Brandt, S.; Thomassé, S. (2006), Yoğun üçgen içermeyen grafikler dört renklenebilir: Erdős-Simonovits problemine bir çözüm (PDF).
- Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listeleme algoritmaları" , SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 , S2CID 207051803.
- Descartes, Blanche (Nisan 1947), "Üç renk sorunu", Eureka , 21.
- Descartes, Blanche (1954), "İleri Sorunun Çözümü no. 4526", Amer. Matematik. Aylık , 61 : 352.
- Chvátal, Vašek (1974), "Mycielski grafiğinin minimalliği", Grafikler ve kombinatorik (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , Lecture Notes in Mathematics, 406 , Springer-Verlag, s. 243–246.
- Erdaş, P. ; Simonovits, M. (1973), "Ekstremal çizge teorisinde bir değerlik probleminde", Discrete Mathematics , 5 (4): 323–334, doi : 10.1016/0012-365X(73)90126-X.
- Erdaş, P. ; Suen, S.; Winkler, P. (1995), "On the boyutu of a random maksimal graph", Random Structures and Algorithms , 6 (2–3): 309–318, doi : 10.1002/rsa.3240060217.
- Gimbel, John; Thomassen, Carsten (2000), "Sabit boyutlu üçgensiz grafikler boyama", Discrete Mathematics , 219 (1–3): 275–277, doi : 10.1016/S0012-365X(00)00087-X.
- Grötzsch, H. (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109–120.
- Häggkvist, R. (1981), "Bipartite olmayan grafiklerde belirtilen uzunluktaki tek döngüler", Graph Theory (Cambridge, 1981) , 62 , s. 89–99, doi : 10.1016/S0304-0208(08)73552-7.
- Imrich, Wilfried; Klavzar, Sandi; Mulder, Henry Martyn (1999), "Medyan grafikler ve üçgensiz grafikler" , SIAM Journal on Discrete Mathematics , 12 (1): 111–118, doi : 10.1137/S0895480197323494 , MR 1666073 , S2CID 14364050.
- İtai, A.; Rodeh, M. (1978), "Bir grafikte bir minimum devre bulma", SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137/0207033.
- Jin, G. (1995), " Üçgensiz dört renkli grafikler", Discrete Mathematics , 145 (1–3): 151–170, doi : 10.1016/0012-365X(94)00063-O.
- Kim, JH (1995), "Ramsey sayısı büyüklük sırasına sahiptir " , Rastgele Yapılar ve Algoritmalar , 7 (3): 173–207, doi : 10.1002/rsa.3240070302 , S2CID 16658980.
- Le Gall, François (Ekim 2014), "Birleşimsel argümanlar yoluyla üçgen bulma için iyileştirilmiş kuantum algoritması", 55th Annual Symposium on Foundations of Computer Science (FOCS 2014) , IEEE, s. 216–225, arXiv : 1407.0085 , doi : 10.1109/focs.2014.31 , ISBN 978-1-4799-6517-5, S2CID 5760574.
- Lee, Troy; Magniez, Frederic; Santha, Miklos (2013), "Üçgen bulma ve ilişkilendirme testi için iyileştirilmiş kuantum sorgu algoritmaları" , Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) , New Orleans, Louisiana, s. 1486–1502, ISBN'si 978-1-611972-51-1.
- Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Matematik. , 3 (2): 161–162, doi : 10.4064/cm-3-2-161-162.
- Nilli, A. (2000), "Büyük kromatik sayılara sahip üçgensiz grafikler", Discrete Mathematics , 211 (1–3): 261–262, doi : 10.1016/S0012-365X(99)00109-0.
- Shearer, JB (1983), " Üçgensiz grafiklerin bağımsızlık sayısına ilişkin not", Discrete Mathematics , 46 (1): 83–87, doi : 10.1016/0012-365X(83)90273-X.
- Thomassen, C. (1994), "Grötzsch's 3-color teoremi", Journal of Kombinatory Theory, Series B , 62 (2): 268–279, doi : 10.1006/jctb.1994.1069.
Dış bağlantılar
- "Graphclass: üçgensiz" , Grafik Sınıfları ve İnklüzyonları Üzerine Bilgi Sistemi