Mükemmel grafik - Perfect graph

Paley grafik amacıyla 9, üç renk ile renkli ve üç köşe bir klik gösteren. Bu grafikte ve indüklenmiş alt grafiklerinin her birinde, kromatik sayı klik numarasına eşittir, bu nedenle mükemmel bir grafiktir.

Olarak grafik teorisi , bir mükemmel grafiktir a, grafik olan renk sayısı , her bir uyarılan alt grafiği büyük sırasını eşit klik bu alt grafiğinin (arasında klik sayısı ). Sembolik terimlerle eşdeğer olarak ifade edildiğinde, keyfi bir grafik , ancak ve ancak sahip olduğumuz her şey için mükemmelse mükemmeldir . ${\görüntüleme stili G=(V,E)}$${\görüntüleme stili S\alt küme V}$${\displaystyle \chi (G[S])=\omega (G[S])}$

Mükemmel grafikler, birçok önemli grafik ailesini içerir ve bu ailelerdeki renklendirmeler ve klikler ile ilgili sonuçları birleştirmeye hizmet eder . Örneğin, tüm mükemmel grafiklerde, grafik renklendirme problemi , maksimum klik problemi ve maksimum bağımsız küme problemi polinom zamanında çözülebilir . Ek olarak, Dilworth teoremi gibi kombinatorikteki birkaç önemli min-max teoremi , belirli ilişkili grafiklerin mükemmelliği açısından ifade edilebilir.

Bir grafik olan 1 mükemmel ancak ve ancak . O halde, ancak ve ancak her alt grafiği 1-mükemmel ise mükemmeldir. ${\görüntüleme stili G}$${\displaystyle \chi (G)=\omega (G)}$${\görüntüleme stili G}$${\görüntüleme stili G}$

Özellikler

• By mükemmel grafik teoremi , bir grafiği onun ancak ve ancak mükemmel tamamlayıcısı mükemmeldir.${\görüntüleme stili G}$ ${\görüntüleme stili {\bar {G}}}$
• Tarafından güçlü kusursuz bir grafik teoremi , mükemmel grafikler aynıdır Berge grafikler, grafiklerdir burada ne de bir içermektedir neden döngüsü tek uzunluğu 5 ya da daha fazla.${\görüntüleme stili G}$${\görüntüleme stili G}$${\görüntüleme stili {\bar {G}}}$

Daha fazla ayrıntı için aşağıdaki bölüme bakın.

Tarih

Bir 1958 sonucundan geliştirilen mükemmel grafikler teorisi Tibor Gallai çağdaş dilde belirten şeklinde yorumlanabilir bu tamamlayıcı a ikiye ayrılır çizge mükemmeldir; bu sonuç aynı zamanda Kőnig teoreminin basit bir eşdeğeri olarak da görülebilir , iki parçalı grafiklerde eşleşmeler ve tepe kapakları ile ilgili çok daha eski bir sonuç. "Mükemmel grafik" ifadesinin ilk kullanımı, Berge grafiklerine adını veren Claude Berge'in 1963 tarihli bir makalesinde görünmektedir . Bu yazıda mükemmel grafikler tanımlayarak Gallai'nin sonucunu birkaç benzer sonuçla birleştirdi ve mükemmel grafiğin eşdeğerliğini ve Berge grafiği tanımlarını tahmin etti; onun varsayımı 2002'de güçlü mükemmel grafik teoremi olarak kanıtlandı .

Mükemmel grafik aileleri

Daha iyi bilinen mükemmel grafiklerden bazıları şunlardır:

• İki parçalı grafikler olabilir grafiklerdir, renkli olmak üzere iki renk ile, ormanlar (Döngü olmayan grafikler).
• İki parçalı grafiklerin çizgi grafikleri (bkz. Kőnig teoremi ). Rook'un grafikleri ( tam iki parçalı grafiklerin çizgi grafikleri ) özel bir durumdur.
• Kiriş grafikler , dört veya daha fazla köşelerin her döngüsü olan grafikler akor , döngü ardışık olmayan iki köşe arasında bir kenar. Bunlar şunları içerir:
  • ormanlar, k -ağaçlar (belirli bir ağaç genişliğine sahip maksimum grafikler ),
  • bölünmüş grafikler (bir klik ve bağımsız bir kümeye bölünebilen grafikler ),
  • blok grafikler (iki bağlantılı her bileşenin bir klik olduğu grafikler),
  • Batlamyus grafikleri (mesafeleri Batlamyus'un eşitsizliğine uyan grafikler ),
  • aralık grafikleri (her bir köşenin bir doğrunun aralığını temsil ettiği ve her bir kenarın iki aralık arasındaki boş olmayan bir kesişimi temsil ettiği grafikler),
  • önemsiz derecede mükemmel grafikler (iç içe aralıklar için aralık grafikleri), eşik grafikleri (toplam ağırlıkları sayısal bir eşiği aştığında iki köşenin bitişik olduğu grafikler),
  • yel değirmeni grafikleri (eşit kliklerin ortak bir tepe noktasında birleştirilmesiyle oluşturulur),
  • ve güçlü kiriş grafikleri (altı veya daha fazla uzunluktaki her çift döngünün tek bir kirişe sahip olduğu kiriş grafikleri).
• Kısmi sırayla ilişkili olduklarında eleman çiftlerinin bir kenarla birleştirilmesiyle kısmen sıralı kümelerden oluşturulan karşılaştırılabilirlik grafikleri . Bunlar şunları içerir:
  • ikili grafikler, aralık grafiklerinin tamamlayıcıları, önemsiz derecede mükemmel grafikler, eşik grafikleri, yel değirmeni grafikleri,
  • permütasyon grafikleri (kenarların bir permütasyonla tersine çevrilmiş eleman çiftlerini temsil ettiği grafikler),
  • ve cographs (ayrık birleşme ve tamamlamanın özyinelemeli işlemleriyle oluşturulan grafikler).
• Açgözlü bir renklendirme algoritmasının her uyarılmış alt grafikte optimal olacağı şekilde sıralanabilen grafikler olan mükemmel sıralanabilir grafikler . Bunlar, ikili grafikler, kiriş grafikleri, karşılaştırılabilirlik grafikleri,
  • mesafe-kalıtsal grafikler (bağlantılı indüklenmiş alt
  grafiklerdeki en kısa yol mesafelerinin tüm grafiktekilere eşit olduğu),
• ve tek sayıda köşeli tekerlek grafikleri .

min-max teoremleriyle ilişkisi

Tüm grafiklerde, klik numarası kromatik sayı için bir alt sınır sağlar, çünkü bir klikteki tüm köşelere herhangi bir uygun renklendirmede farklı renkler atanmalıdır. Mükemmel grafikler, sadece grafiğin kendisinde değil, tüm indüklenmiş alt grafiklerinde bu alt sınırın sıkı olduğu grafiklerdir. Mükemmel olmayan grafikler için kromatik sayı ve klik numarası farklı olabilir; örneğin, beş uzunlukta bir döngü, herhangi bir uygun renklendirmede üç renk gerektirir, ancak en büyük kliği iki bedene sahiptir.

Bir grafik sınıfının mükemmel olduğunun kanıtı bir min-max teoremi olarak görülebilir: Bu grafikler için gereken minimum renk sayısı, bir kliğin maksimum boyutuna eşittir. Kombinatorikteki birçok önemli min-max teoremi bu terimlerle ifade edilebilir. Örneğin, Dilworth teoremi , kısmen sıralı bir kümenin zincirler halindeki bir bölümündeki minimum zincir sayısının , bir anti zincirin maksimum boyutuna eşit olduğunu belirtir ve karşılaştırılabilirlik grafiklerinin tamamlayıcılarının mükemmel olduğunu belirterek yeniden ifade edilebilir . Mirsky'nin teoremi , bir zincir karşıtına bölünen minimum zincir karşıtı sayısının bir zincirin maksimum boyutuna eşit olduğunu ve aynı şekilde karşılaştırılabilirlik grafiklerinin mükemmelliğine tekabül ettiğini belirtir.

Permütasyon grafiklerinin mükemmelliği, sıralı elemanların her dizisinde, en uzun azalan alt dizinin uzunluğunun, artan alt dizilere bölünen bir bölümdeki minimum dizi sayısına eşit olduğu ifadesine eşdeğerdir . Erdos-Szekeres teoremi bu bildiriminin kolay sonucudur.

Kőnig'in çizge teorisindeki teoremi , iki parçalı bir çizgedeki minimum köşe kaplamasının maksimum eşleşmeye karşılık geldiğini ve bunun tersini belirtir ; ikili grafiklerin tamamlayıcılarının mükemmelliği olarak yorumlanabilir. İki parçalı grafiklerle ilgili bir başka teorem, kromatik indekslerinin maksimum derecelerine eşit olması, iki parçalı grafiklerin çizgi grafiklerinin mükemmelliğine eşdeğerdir.

Karakterizasyonlar ve mükemmel grafik teoremleri

Mükemmel grafikler üzerindeki ilk çalışmasında Berge, yapıları hakkında ancak daha sonra kanıtlanacak olan iki önemli varsayım yaptı.

Bu iki teoremden ilki , Lovász'ın (1972) mükemmel grafik teoremiydi ve bir grafiğin ancak ve ancak tümleyeni mükemmel olduğunda mükemmel olduğunu belirtir . Bu nedenle, mükemmellik (her uyarılmış alt grafikte maksimum klik boyutu ve kromatik sayının eşitliği olarak tanımlanır), maksimum bağımsız küme boyutu ve klik kapak sayısının eşitliğine eşdeğerdir.

Yedi köşeli bir döngü ve tamamlayıcısı, her durumda bir optimal renklendirme ve bir maksimum klik (ağır kenarlarla gösterilmiştir). Her iki grafik de kendi klik boyutuna eşit sayıda renk kullanmadığından, ikisi de mükemmel değildir.

Berge tarafından tahmin edilen ikinci teorem, mükemmel grafiklerin yasaklanmış bir grafik karakterizasyonunu sağladı . Bir neden döngü tek uzunluğunun en az bir 5 bir adlandırılan tek bir delik . Tek bir deliğin tamamlayıcısı olan indüklenmiş bir alt grafiğe tek antidelik denir . 3'ten büyük tek bir uzunluk döngüsü mükemmel olamaz, çünkü kromatik sayısı üç ve klik numarası ikidir. Benzer şekilde, uzunluğu tek bir döngüsünün tamamlayıcı 2 k  + 1 kendi renk bir sayı olduğundan, mükemmel olamaz k  + 1 ve klik sayıdır k . (Alternatif olarak, bu grafiğin kusuru, mükemmel grafik teoreminden ve tamamlayıcı tek döngünün kusurundan kaynaklanır). Bu grafikler mükemmel olmadığı için, her mükemmel grafik bir Berge grafiği , tek boşlukları ve tek antidelikleri olmayan bir grafik olmalıdır. Berge, tersini, her Berge grafiğinin mükemmel olduğunu tahmin etti. Bu nihayet olarak kanıtlandı güçlü mükemmel grafik teoremi ait Chudnovsky , Robertson , Seymour ve Thomas (2006). Önemsiz bir şekilde mükemmel grafik teoremini ima eder, dolayısıyla adı.

Mükemmel grafik teoreminin kısa bir kanıtı vardır, ancak güçlü mükemmel grafik teoreminin kanıtı, Berge grafiklerinin derin bir yapısal ayrışmasına dayanan uzun ve tekniktir. İlgili ayrıştırma teknikleri, diğer grafik sınıflarının ve özellikle pençesiz grafikler için yapılan çalışmalarda da meyve vermiştir .

İlk olarak Hajnal tarafından önerilen, yine Lovász'dan kaynaklanan üçüncü bir teorem vardır . En büyük kliğin ve en büyük bağımsız kümenin boyutları, birlikte çarpıldığında, grafiğin köşelerinin sayısına eşitse veya bu sayıyı aşıyorsa bir grafiğin mükemmel olduğunu belirtir ve aynısı herhangi bir indüklenmiş alt grafik için de geçerlidir. Güçlü mükemmel grafik teoreminin kolay bir sonucuyken, mükemmel grafik teoremi bunun kolay bir sonucudur.

Hajnal karakterizasyonu tek ile karşılanmadığında , n -cycles veya kendi tamamlayıcı n > 3 : tek döngüsü üzerinde n > 3 köşe klik sayı bulunmakta 2 ve bağımsızlık sayısını ( n - 1) / 2 . Tümleyen için bunun tersi doğrudur, dolayısıyla her iki durumda da çarpım n − 1'dir .

Mükemmel grafiklerde algoritmalar

Tüm mükemmel grafiklerde, grafik boyama problemi , maksimum klik problemi ve maksimum bağımsız küme problemi polinom zamanında çözülebilir ( Grötschel, Lovász & Schrijver 1988 ). Genel durum için algoritma , (belirli bir grafiğin tamamlayıcısı için) kromatik sayı ve klik numarası arasına sıkıştırılan bu grafiklerin Lovász sayısını içerir. Lovász sayısının hesaplanması yarı tanımlı bir program olarak formüle edilebilir ve doğrusal programlama için elipsoid yöntemi kullanılarak polinom zamanında sayısal olarak yaklaşık olarak hesaplanabilir . Mükemmel grafikler için, bu yaklaşımı bir tam sayıya yuvarlamak, polinom zamanında kromatik sayıyı ve klik numarasını verir; maksimum bağımsız küme, grafiğin tamamlayıcısına aynı yaklaşımı uygulayarak bulunabilir. Bununla birlikte, bu yöntem karmaşıktır ve yüksek bir polinom üssüne sahiptir. Birçok özel durum için daha verimli kombinatoryal algoritmalar bilinmektedir.

Uzun yıllar boyunca Berge grafiklerini ve mükemmel grafikleri tanımanın karmaşıklığı açık kaldı. Berge grafiklerinin tanımından, bunların tanınmalarının eş-NP'de olduğu hemen anlaşılır (Lovász 1983). Son olarak, güçlü mükemmel grafik teoreminin ispatının ardından Chudnovsky, Cornuéjols, Liu, Seymour ve Vušković tarafından bir polinom zaman algoritması keşfedildi.

Referanslar

• Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Üniv. Halle-Wittenberg Math.-Doğa. Reihe . 10 : 114.
• Berge, Claude (1963). "Mükemmel grafikler". Grafik Teorisi Üzerine Altı Kağıt . Kalküta: Hindistan İstatistik Enstitüsü. s. 1-21.
• Chudnovsky, Maria ; Cornuejols, Gerard ; Liu, Xinming; Seymur, Paul ; Vušković, Kristina (2005). "Berge grafiklerini tanıma" . Kombinatorika . 25 (2): 143–186. doi : 10.1007/s00493-005-0012-8 . S2CID  2229369 .
• Chudnovsky, Maria ; Robertson, Neil ; Seymur, Paul ; Thomas, Robin (2006). "Güçlü mükemmel grafik teoremi" . Matematik Annals . 164 (1): 51–229. arXiv : matematik/0212070 . doi : 10.4007/annals.2006.164.51 . S2CID  119151552 .
• Gallai, Tibor (1958). "Maksimum-minimum Sätze über Grafen" . Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. doi : 10.1007/BF02020271 . S2CID  123953062 .
• Golumbik, Martin Charles (1980). Algoritmik Grafik Teorisi ve Mükemmel Grafikler . Akademik Basın. ISBN'si 0-444-51530-5. Arşivlenmiş orijinal 2010-05-22 tarihinde . 2007-11-21 alındı . İkinci baskı, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1988). Geometrik Algoritmalar ve Kombinatoryal Optimizasyon . Springer-Verlag. Özellikle bkz. bölüm 9, "Grafiklerde Kararlı Kümeler", s. 273–303.
• Lovász, László (1972). "Normal hipergraflar ve mükemmel grafik varsayımı" . Ayrık Matematik . 2 (3): 253–267. doi : 10.1016/0012-365X(72)90006-4 .
• Lovász, László (1972). "Mükemmel grafiklerin bir karakterizasyonu" . Kombinatoryal Teori Dergisi . Seri B. 13 (2): 95–98. doi : 10.1016/0095-8956(72)90045-7 .
• Lovász, László (1983). "Mükemmel grafikler". Beineke'de Lowell W.; Wilson, Robin J. (ed.). Grafik Teorisinde Seçilmiş Konular, Cilt. 2 . Akademik Basın. s. 55-87. ISBN'si 0-12-086202-6.

Dış bağlantılar

• Güçlü mükemmel grafik teoremi tarafından Václav Chvátal .
• Amerikan Matematik Enstitüsü tarafından sağlanan mükemmel grafikler üzerinde açık problemler .
• Václav Chvátal tarafından sağlanan Mükemmel Sorunlar .
• Grafik Sınıfı Kapanımları Hakkında Bilgi Sistemi : mükemmel grafik