Fleischners teoremi - Fleischners theorem - Wikipedia

2 köşe bağlantılı bir grafik, karesi ve karede bir Hamilton döngüsü

İçinde grafik teorisi bir matematik dalı, Fleischner teoremi bir grafiğin bir Hamilton döngüsü. Bu, eğer G bir 2 köşe bağlantılı grafik, sonra kare G Hamiltoniyen. adını almıştır Herbert Fleischner, 1974'te kanıtını yayınlayan.

Tanımlar ve ifade

Bir yönsüz grafik G Hamiltonyandır, eğer bir döngü her bir köşesine tam olarak bir kez dokunur. Bir artikülasyon tepe noktasına sahip değilse, 2 tepe noktasına bağlıdır, silinmesi kalan grafiğin bağlantısını kesecek bir tepe noktasıdır. Her 2 köşe bağlantılı grafik Hamilton değildir; karşı örnekler şunları içerir: Petersen grafiği ve tam iki parçalı grafik K2,3.

Kare G bir grafik G2 ile aynı köşe ayarına sahip Gve ancak ve ancak aralarında en fazla iki mesafe varsa, iki köşenin bitişik olduğu G. Fleischner teoremi, en az üç köşeli sonlu 2 köşe bağlantılı bir grafiğin karesinin her zaman Hamiltonian olması gerektiğini belirtir. Eşdeğer olarak, her 2 köşe bağlantılı grafiğin köşeleri G şeklinde düzenlenebilir döngüsel düzen öyle ki bu sıradaki bitişik köşeler, birbirlerinden en fazla iki uzaklıkta G.

Uzantılar

Fleischner teoreminde, Hamilton döngüsünü kısıtlamak mümkündür. G2 böylece verilen köşeler için v ve w nın-nin G iki kenarını içerir G ile olay v ve bir kenarı G ile olay w. Dahası, eğer v ve w bitişik G, o zaman bunlar üç farklı kenar G.[1]

Bir Hamilton döngüsüne sahip olmanın yanı sıra, 2 köşe bağlantılı bir grafiğin karesi G ayrıca Hamilton ile bağlantılı olmalıdır (yani bir Hamilton yolu herhangi iki belirlenmiş köşede başlar ve biter) ve 1-Hamiltonian (yani herhangi bir köşe silinirse, kalan grafiğin hala bir Hamilton döngüsü vardır).[2] Aynı zamanda tepe noktası olmalı pankeklik yani her köşe için v ve her tam sayı k 3 ≤ ilek ≤ |V(G) |, bir uzunluk döngüsü vark kapsamakv.[3]

Bir grafik G 2-köşe bağlantılı değildir, o zaman karesinin Hamilton döngüsü olabilir veya olmayabilir ve olup olmadığını belirleme NP tamamlandı.[4]

Sonsuz bir grafiğin Hamilton döngüsü olamaz, çünkü her döngü sonludur, ancak Carsten Thomassen kanıtladı eğer G sonsuz yerel olarak sonlu 2 köşe bağlantılı bir grafiktir ve tek bir son sonra G2 zorunlu olarak iki kat sonsuz Hamilton yolu vardır.[5] Daha genel olarak, eğer G yerel olarak sonlu, 2 köşe bağlantılı ve herhangi bir sayıda uca sahipse G2 Hamilton çemberi vardır. İçinde kompakt topolojik uzay grafiği bir basit kompleks ve uçlarının her birine sonsuzda fazladan bir nokta ekleyerek, bir Hamilton çemberi, bir alt uzay olarak tanımlanır. homomorfik bir Öklid çemberine ve her köşeyi kaplar.[6]

Algoritmalar

Bir karesinde Hamilton döngüsü n-vertex 2 bağlantılı grafik doğrusal zamanda bulunabilir,[7] Lau'nun ilk algoritmik çözümüne göre iyileştirme[8] çalışma süresi O (n2).Fleischner teoremi bir sağlamak için kullanılabilir 2-yaklaşım için darboğaz seyyar satıcı sorunu içinde metrik uzaylar.[9]

Tarih

Fleischner teoreminin bir kanıtı tarafından açıklandı Herbert Fleischner 1971'de ve 1974'te yayınladı, 1966 varsayımını çözerek Crispin Nash-Williams tarafından bağımsız olarak da yapılmıştır L. W. Beineke ve Michael D. Plummer.[10] Fleischner'ın makalesine yaptığı incelemede Nash-Williams, "birkaç yıldır diğer grafik teorisyenlerinin yaratıcılığını yenen iyi bilinen bir sorunu" çözdüğünü yazdı.[11]

Fleischner'ın orijinal kanıtı karmaşıktı. Václav Chvátal, icat ettiği işte grafik tokluğu, bir karenin k-vertex bağlantılı grafik zorunlu olarak k-zorlu; o varsayılmış Fleischner teoreminin başka bir kanıtı da onu takip eden Hamiltoniyendir.[12] Bu varsayıma karşı örnekler daha sonra keşfedildi,[13] ancak tokluğa sonlu bir sınırın Hamiltonisite anlamına gelme olasılığı, grafik teorisinde önemli bir açık problem olmaya devam etmektedir. Hem Fleischner teoreminin hem de uzantılarının daha basit bir kanıtı Chartrand vd. (1974) tarafından verildi Říha (1991),[14] ve teoremin bir başka basitleştirilmiş kanıtı tarafından verildi Georgakopoulos (2009a).[15]

Referanslar

Notlar

  1. ^ Fleischner (1976); Müttel ve Rautenbach (2012).
  2. ^ Chartrand vd. (1974); Chartrand, Lesniak ve Zhang (2010)
  3. ^ Hobbs (1976), bir varsayıma cevap vermek Bondy (1971).
  4. ^ Yeraltı (1978); Bondy (1995).
  5. ^ Thomassen (1978).
  6. ^ Georgakopoulos (2009b); Diestel (2012).
  7. ^ Alstrup, Georgakopoulos, Rotenberg, Thomassen (2018)
  8. ^ Lau (1980); Parker ve Rardin (1984).
  9. ^ Parker ve Rardin (1984); Hochbaum ve Shmoys (1986).
  10. ^ Fleischner (1974). Daha önceki varsayımlar için bkz. Fleischner ve Chartrand, Lesniak ve Zhang (2010).
  11. ^ BAY0332573.
  12. ^ Chvátal (1973); Bondy (1995).
  13. ^ Bauer, Broersma ve Veldman (2000).
  14. ^ Bondy (1995); Chartrand, Lesniak ve Zhang (2010).
  15. ^ Chartrand, Lesniak ve Zhang (2010); Diestel (2012).

Birincil kaynaklar

İkincil kaynaklar