Mükemmel grafik teoremi - Perfect graph theorem

Olarak grafik teorisi , tam grafik teoremi arasında László Lovász  ( 1972a , 1972b ) bir bildiren yönsüz grafik olan mükemmel olan, ancak ve ancak tamamlayıcı grafiği de mükemmeldir. Bu sonuç Berge  ( 1961 , 1963 ) tarafından tahmin edilmişti ve mükemmel grafikleri yasaklanmış alt grafikleriyle karakterize eden güçlü mükemmel grafik teoreminden ayırt etmek için bazen zayıf mükemmel grafik teoremi olarak adlandırılır .

Beyan

Bir kusursuz bir grafik olan her birinde, özelliği bir yönsüz grafiktir neden Alt Graflar , büyük boyutu klik bir renk az sayıda eşit boyama alt grafiği arasında. Mükemmel grafikler, ikili grafikler , kordal grafikler ve karşılaştırılabilirlik grafikleri dahil olmak üzere birçok önemli grafik sınıfını içerir .

Bir grafiğin tümleyeni, ancak ve ancak orijinal grafiğin aynı iki köşe arasında bir kenarı yoksa, iki köşe arasında bir kenara sahiptir. Böylece, orijinal grafikteki bir klik , tamamlayıcıda bağımsız bir küme haline gelir ve orijinal grafiğin bir rengi, tamamlayıcının bir klik örtüsü olur .

Mükemmel grafik teoremi şunları belirtir:

Mükemmel bir grafiğin tamamlayıcısı mükemmeldir.

Eşdeğer olarak, mükemmel bir grafikte, maksimum bağımsız kümenin boyutu, bir klik kapağındaki minimum klik sayısına eşittir.

Örnek

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

G , üçten büyük tek uzunlukta bir döngü grafiği olsun ("tek delik" olarak adlandırılır). O zaman G , herhangi bir renklendirmede en az üç renk gerektirir, ancak üçgeni yoktur, bu nedenle mükemmel değildir. Mükemmel grafik teoremi ile, G'nin ("tek bir antidelik") tümleyeni de bu nedenle mükemmel olmamalıdır. Eğer G beş köşe bir döngüdür, bunun tamamlayıcısı izomorf , ancak bu özellik daha uzun tek döngü için doğru değildir, ve bunun bir in olduğu gibi tek bir antihole içinde klik sayısı ve renk sayısını hesaplamak için önemsiz olarak değil garip delik. Olarak güçlü kusursuz bir grafik teoremi durumları, tek delikler ve tek antiholes az olduğu ortaya çıkar yasak neden subgraphs mükemmel grafikler için.

Uygulamalar

Önemsiz bir iki parçalı grafikte , optimal renk sayısı (tanım gereği) ikidir ve (iki parçalı grafikler üçgen içermediğinden ) maksimum klik boyutu da ikidir. Ayrıca, iki parçalı bir grafiğin herhangi bir indüklenmiş alt grafiği iki parçalı olarak kalır. Bu nedenle, iki parçalı grafikler mükemmeldir. Gelen n -vertex bipartit grafikler, minimum klik kapağı şeklini alır , maksimum karşılaştırma boyutu ile her eşsiz tepe için ek bir klik ile birlikte N  -  E , E eşleme kardinalitesi olup. Böylece, bu durumda, mükemmel grafik teoremi, iki parçalı bir grafikte maksimum bağımsız bir kümenin boyutunun da n  -  M olduğu şeklindeki Kőnig'in teoremini ima eder ; bu, Berge'nin mükemmel grafikler teorisi formülasyonu için büyük bir ilham kaynağı olmuştur.

Mirsky teoremi bir yüksekliğinin karakterize kısmen sıralı bir setin içine bölmeler açısından antichains mükemmelliği olarak formüle edilebilir karşılaştırılabilirlik grafik kısmen sıralı bir setin ve Dilworth teoremi zincirlerine bölmeler açısından kısmen sıralı bir setin genişliğini karakterize eden can bu grafiklerin tamamlayıcılarının mükemmelliği olarak formüle edilebilir. Bu nedenle, mükemmel grafik teoremi, Dilworth teoremini Mirsky teoreminin (çok daha kolay) kanıtından kanıtlamak için kullanılabilir veya tam tersi.

Lovász'ın kanıtı

Mükemmel grafik teoremini kanıtlamak için Lovász, bir grafikteki köşeleri klikler ile değiştirme işlemini kullandı; Berge, bir grafik mükemmelse, bu değiştirme işlemiyle oluşturulan grafiğin de mükemmel olduğunu zaten biliyordu. Bu tür herhangi bir değiştirme işlemi, bir köşeyi ikiye katlamak için tekrarlanan adımlara bölünebilir. İki katına çıkan tepe grafiğin maksimum kliğine aitse, hem klik numarasını hem de kromatik sayıyı bir artırır. Öte yandan, ikiye katlanan tepe noktası bir maksimum kliğe ait değilse, verilen grafiğin optimal renginden iki katına çıkan tepe ile aynı renge sahip olan (ancak ikiye katlanan tepe noktasının kendisi değil) köşeleri çıkararak bir H grafiği oluşturun. . Kaldırılan köşeler her maksimum kliği karşılar, bu nedenle H klik numarasına ve verilen grafiğin kromatik numarasından bir eksiktir. Kaldırılan tepe noktaları ve ikiye katlanan tepe noktasının yeni kopyası daha sonra tek bir renk sınıfı olarak geri eklenebilir; bu, bu durumda ikiye katlama adımının kromatik sayıyı değiştirmeden bıraktığını gösterir. Aynı argüman, ikiye katlamanın, verilen grafiğin indüklenen her alt grafiğindeki klik numarası ve kromatik sayının eşitliğini koruduğunu, böylece her iki katlama adımının grafiğin mükemmelliğini koruduğunu gösterir.

Mükemmel bir grafiği verilen G , Lovász bir grafik oluşturan G her köşe değiştirerek * v bir klik ile t v köşe, t v belirgin maksimum bağımsız takımdan sayısıdır G içeren v . Belirgin maksimum bağımsız kümelerinin her tekabül mümkündür G maksimum bağımsız setleri biriyle G seçilen maksimum bağımsız setleri bu şekilde, * G * Tüm ayrık ve her köşe olan G * a görünür tek seçilmiş set; yani G *, her renk sınıfının maksimum bağımsız küme olduğu bir renklendirmeye sahiptir. Mutlaka bu renklendirme, G * ' nin optimal bir renklendirmesidir . Çünkü G mükemmeldir, bu nedenle bir G * ve bu nedenle maksimum klik sahip K olan boyutu belirgin maksimum bağımsız takımdan sayısıdır, bu boyama renk sayısını eşittir * G ; zorunlu olarak, K * bu maksimum bağımsız kümelerin her biri için ayrı bir temsilci içerir. Karşılık gelen resim K tepe nokta G (ki genişletilmiş klikler de köşe G * kesiştiği K *) 'de bir klik olan G bunun içinde her bir maksimum bağımsız set kesişen özelliği ile G . Bu nedenle, oluşturulan grafik G kaldırarak K klik az klik sayısından daha çok bir de kapak sayıda G ve bağımsızlık sayısını daha bağımsızlığı sayısından daha az bir G ve sonuç bu sayı indüksiyonu ile takip eder.

Güçlü mükemmel grafik teoremi ile ilişkisi

Güçlü kusursuz bir grafik teoremi arasında Chudnovsky ve diğ. (2006) , bir grafiğin, ancak ve ancak indüklenmiş alt grafiklerinden hiçbiri beşe eşit veya daha büyük tek uzunluktaki döngüler veya bunların tamamlayıcıları olmadığında mükemmel olduğunu belirtir. Bu karakterizasyon, grafik tamamlamadan etkilenmediği için, hemen zayıf mükemmel grafik teoremini ima eder.

genellemeler

Cameron, Edmonds & Lovász (1986) , tam bir grafiğin kenarları, her üç köşenin üç alt grafikten birinde bağlantılı bir grafiği indükleyecek şekilde üç alt grafiğe bölünmesi durumunda ve alt graflardan ikisi mükemmel ise kanıtladı. , o zaman üçüncü alt yazı da mükemmeldir. Mükemmel grafik teoremi, üç alt grafikten biri boş grafik olduğunda bu sonucun özel halidir .

Notlar

Referanslar

  • Berge, Claude (1961), "Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind", Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche : 10 Almanca.
  • Berge, Claude (1963), "Mükemmel grafikler", Grafik Teorisi Üzerine Altı Kağıt , Kalküta: Hint İstatistik Enstitüsü, s. 1-21.
  • Cameron, K.; Edmonds, J .; Lovász, L. (1986), "Mükemmel grafikler üzerine bir not", Periodica Mathematica Hungarica , 17 (3): 173–175, doi : 10.1007/BF01848646 , MR  0859346.
  • Chudnovsky, Maria ; Robertson, Neil ; Seymur, Paul ; Thomas, Robin (2006), "Güçlü mükemmel grafik teoremi", Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , MR  2233847.
  • Chudnovsky, Maria ; Robertson, Neil ; Seymur, Paul ; Thomas, Robin (2003), "Mükemmel grafiklerde ilerleme" (PDF) , Matematiksel Programlama , Seri B., 97 (1-2): 405-422, doi : 10.1007/s10107-003-0449-8 , MR  2004404.
  • Gallai, Tibor (1958), "Maksimum-minimum Sätze über Graphen", Acta Mathematica Academiae Scientiarum Hungaricae (Almanca), 9 (3–4): 395–434, doi : 10.1007/BF02020271 , MR  0124238
  • Golumbic, Martin Charles (1980), "3.2. Mükemmel grafik teoremi", Algoritmik Grafik Teorisi ve Mükemmel Grafikler , New York: Academic Press, s. 53–58, ISBN 0-12-289260-7, MR  0562306.
  • Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok (Macarca), 38 : 116-119
  • Lovász, László (1972a), "Normal hipergraflar ve mükemmel çizge varsayımı", Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4.
  • Lovász, László (1972b), "Mükemmel grafiklerin karakterizasyonu", Journal of Kombinatory Theory , Series B, 13 (2): 95–98, doi : 10.1016/0095-8956(72)90045-7.
  • Reed, Bruce A. (2001), "Sanırımdan teoreme", Ramírez Alfonsín, Jorge L.; Reed, Bruce A. (ed.), Perfect Graphs , Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley, pp. 13–24, MR  1861356.