Cevher teoremi - Ores theorem - Wikipedia

Ore teoreminin koşullarını karşılayan bir grafik ve içindeki Hamilton döngüsü. Dereceden daha az olan iki köşe var n/ 2 çizimin merkezinde olduğundan, Dirac teoremi için koşullar karşılanmaz. Bununla birlikte, bu iki köşe bitişiktir ve diğer tüm köşe çiftlerinin toplam derecesi en az yedi, yani köşe sayısıdır.

Cevher teoremi sonuçtur grafik teorisi 1960 yılında Norveççe matematikçi Øystein Cevheri. Bir grafiğin olması için yeterli bir koşul sağlar. Hamiltoniyen, esasen yeterince çok kenarı olan bir grafiğin bir Hamilton döngüsü. Özellikle, teorem toplamını dikkate alır derece çiftlerin bitişik olmayan köşeler: Eğer bu tür her bir çiftin en azından grafikteki toplam köşe sayısına eşit bir toplamı varsa, o zaman grafik Hamilton'dır.

Resmi açıklama

İzin Vermek G (sonlu ve basit) olun grafik ile n ≥ 3 köşeler. İle belirtiyoruz derece v bir tepe noktası derecesi v içinde Gyani sayısı olay kenarlar içinde G -e v. Ardından, Ore teoremi şunu belirtir:

derece v + derece wn her bir çift için bitişik olmayan köşeler v ve w nın-nin G

 

 

 

 

(∗)

sonra G dır-dir Hamiltoniyen.

Kanıt

Ore teoreminin ispatı için örnek. Hamilton yolu ile bir grafikte v1...vn ama Hamilton döngüsü yok, en fazla iki kenardan biri v1vben ve vben − 1vn (mavi kesikli eğriler olarak gösterilmiştir) mevcut olabilir. Çünkü ikisi de mevcutsa, onları yola eklemek ve (kırmızı) kenarı kaldırmak vben − 1vben bir Hamilton döngüsü üretecektir.

Hamilton olmayan her grafiğin G koşula uymuyor (∗). Buna göre izin ver G grafik olmak n ≥ 3 Hamiltonyen olmayan köşeler ve H oluşturulmak G daha fazla kenar eklenemeyene kadar, bir Hamilton döngüsü oluşturmayan kenarları birer birer ekleyerek. İzin Vermek x ve y herhangi iki bitişik olmayan köşe olabilir H. Sonra kenar ekleyerek xy -e H en az bir yeni Hamilton döngüsü yaratır ve xy böyle bir döngüde bir Hamilton yolu v1v2...vn içinde H ile x = v1 ve y = vn. Her indeks için ben aralıkta 2 ≤ benn, iki olası kenarı düşünün H itibaren v1 -e vben ve den vben − 1 -e vn. Bu iki kenardan en fazla biri, Haksi takdirde döngü v1v2...vben − 1vnvn − 1...vben Hamilton döngüsü olacaktır. Bu nedenle, herhangi biriyle ilgili toplam kenar sayısı v1 veya vn en fazla seçenek sayısına eşittir ben, hangisi n − 1. Bu nedenle, H mülke itaat etmez (∗), bu toplam kenar sayısının (derece v1 + derece vn) büyük veya eşit olmalıdır n. Köşe dereceleri G en fazla derece eşittir Hbunu takip eder G mülke de uymaz(∗).

Algoritma

Palmer (1997) Cevher koşulunu karşılayan bir grafikte bir Hamilton döngüsü oluşturmak için aşağıdaki basit algoritmayı açıklar.

  1. Grafikteki bitişiklikleri yok sayarak, köşeleri gelişigüzel bir döngü halinde düzenleyin.
  2. Döngü iki ardışık köşe içerirken vben ve vben + 1 grafikte bitişik olmayanlar için aşağıdaki iki adımı uygulayın:
    • Bir dizin arayın j öyle ki dört köşe vben, vben + 1, vj, ve vj + 1 hepsi farklıdır ve grafik öyle ki vben -e vj ve den vj + 1 -e vben + 1
    • Döngünün bölümünü ters çevirin vben + 1 ve vj (dahil).

Her adım, döngüde grafikte bitişik olan ardışık çiftlerin sayısını bir veya iki çift artırır ( vj ve vj + 1 zaten bitişiktir), bu nedenle dış döngü yalnızca en fazla n algoritma sona ermeden önce n verilen grafikteki köşe sayısıdır. Teoremin ispatındakine benzer bir argümanla, istenen indeks j var olmalı veya bitişik olmayan köşeler vben ve vben + 1 toplam derecesi çok küçük olurdu. Bulma ben ve jve döngünün bir kısmını tersine çevirmek, hepsi O zamanında gerçekleştirilebilir (n). Bu nedenle, algoritmanın toplam süresi O (n2), giriş grafiğindeki kenar sayısıyla eşleşir.

İlgili sonuçlar

Cevher teoremi bir genellemedir Dirac teoremi ki, her köşe en az dereceye sahip olduğunda n/2, grafik Hamiltoniyen. Çünkü, bir grafik Dirac'ın koşulunu karşılıyorsa, o zaman açıkça her köşe çiftinin dereceleri en azından n.

Cevher teoremi sırayla genelleştirilir. Bondy-Chvátal teoremi. Biri, bitişik olmayan iki tepe noktasının en azından ekleyen derecelere sahip olduğu bir grafik üzerinde bir kapatma işlemi tanımlanabilir. nbunlardan biri onları birbirine bağlayan bir kenar ekler; Bir grafik Ore teoreminin koşullarını karşılıyorsa, kapanışı bir tam grafik. Bondy-Chvátal teoremi, bir grafiğin Hamiltoniyen olduğunu belirtir, ancak ve ancak kapanışı Hamiltonian ise; Tam grafik Hamiltonian olduğundan, Ore teoremi acil bir sonuçtur.

Woodall (1972) Ore teoreminin geçerli bir versiyonunu buldu yönlendirilmiş grafikler. Bir digraf varsayalım G her iki köşe için sen ve vya bir avantaj var sen -e v veya genel derecesi sen artı kararsızlık v içindeki köşe sayısına eşit veya daha fazla G. Ardından, Woodall'ın teoremine göre, G yönlendirilmiş bir Hamilton döngüsü içerir. Cevher teoremi, belirli bir yönsüz grafikteki her kenarın bir çift yönlendirilmiş kenar ile değiştirilmesiyle Woodall'dan elde edilebilir. Yakın ilişkili bir teorem Meyniel (1973) belirtir ki n-vertex güçlü bir şekilde bağlı bitişik olmayan her iki köşe noktası için özelliğe sahip digraph sen ve vmeydana gelen toplam kenar sayısı sen veya v en az 2n - 1 Hamiltonyan olmalıdır.

Cevher teoremi, teoremdeki derece koşulunun bir sonucu olarak Hamiltonisiteden daha güçlü bir sonuç verecek şekilde güçlendirilebilir. Spesifik olarak, Ore teoreminin koşullarını karşılayan her grafik bir düzenli tam iki parçalı grafik veya pankeklik (Bondy 1971 ).

Referanslar

  • Bondy, J. A. (1971), "Pansiklik grafikler I", Kombinatoryal Teori Dergisi, B Serisi, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5.
  • Meyniel, M. (1973), "Une condition suffisante d'existence d'existence d'un circuit hamiltonien dans un graphe orienté", Kombinatoryal Teori Dergisi, B Serisi (Fransızcada), 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9.
  • Cevher, Ø. (1960), "Hamilton devreleri üzerine not", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR  2308928.
  • Palmer, E. M. (1997), "Ore teoreminin Hamilton döngüleri üzerindeki gizli algoritması", Uygulamalar İçeren Bilgisayarlar ve Matematik, 34 (11): 113–119, doi:10.1016 / S0898-1221 (97) 00225-3, BAY  1486890.
  • Woodall, D. R. (1972), "Grafiklerdeki devreler için yeterli koşullar", Londra Matematik Derneği BildirileriÜçüncü Seri, 24: 739–755, doi:10.1112 / plms / s3-24.4.739, BAY  0318000.