Hadwiger numarası - Hadwiger number

Daraltıldığında tam bir grafik oluşturan dört bağlantılı alt grafiğin bulunduğu bir grafik. Wagner teoremi tarafından beş köşeli tam minör yoktur , bu nedenle Hadwiger sayısı tam olarak dörttür.

Olarak grafik teorisi , Hadwiger sayısı bir bölgesinin yönsüz grafik G en büyük boyutu tam bir grafik elde edilebilir sözleşme kenarları arasında G . Aynı şekilde, Hadwiger sayısı h ( G ) en büyük sayı K tam bir grafiktir olan K _K a, küçük bir G , elde edilen daha küçük bir grafik G kenar kasılmaları ve tepe noktası ve kenar silme ile. Hadwiger numarası olarak da bilinir kasılma klik sayısı arasında G veya homomorfizmi derece arasında G . Bu almıştır Hugo Hadwiger ile birlikte 1943 yılında o tanıttı Hadwiger varsayım Hadwiger numarası gibi büyük her zaman olduğu gibi en azından olduğunu belirtiyor, kromatik sayısı arasında  G .

Hadwiger sayısı en fazla dört olan grafikler Wagner (1937) tarafından karakterize edilmiştir . Hadwiger sayısı üzerinde herhangi bir sonlu sınırı olan grafikler seyrektir ve küçük kromatik sayılara sahiptir. Bir grafiğin Hadwiger numarasını belirlemek NP-zordur ancak sabit parametre izlenebilir .

Küçük Hadwiger numaralı grafikler

Bir grafik G, en fazla iki Hadwiger sayısına sahipse ve bir yalnızca orman yalnızca sözleşme ile oluşturulabilir üç tepe noktası tam küçük için döngüsü içinde  G .

Bir grafiğin en fazla üç Hadwiger sayısı vardır, ancak ve ancak ağaç genişliği en fazla iki ise, bu ancak ve ancak iki bağlantılı bileşenlerinin her biri bir seri-paralel grafikse doğrudur .

Dört numaralı Hadwiger ile daha büyük bir grafik oluşturan, iki düzlemsel grafiğin ve Wagner grafiğinin klik toplamı.

Wagner teoremi karakterize, düzlemsel grafikler kendi tarafından yasaklanmış küçükler , düzlemsel grafik en dörtte Hadwiger numarası olduğunu ima eder. Bu teoremi kanıtlayan aynı makalede, Wagner (1937) ayrıca Hadwiger sayısı ile grafikleri daha kesin olarak karakterize etti: bunlar, düzlemsel grafikleri sekiz köşeli Wagner grafiğiyle birleştiren klik toplamı işlemleriyle oluşturulabilen grafiklerdir .

Hadwiger sayısı en fazla beş olan grafikler , her ikisi de yasaklı küçükleri arasında K ₆ tam grafiğine sahip olan apeks grafiklerini ve bağlantısız gömülebilir grafikleri içerir .

Kıtlık

n köşeli ve Hadwiger sayısı k olan her grafiğin O( nk  √ log k ) kenarı vardır. Bu sınır sıkıdır: her k için , Ω( nk √ log k ) kenarları olan Hadwiger sayısı k olan grafikler vardır . Bir G grafiğinin Hadwiger sayısı k ise , o zaman tüm alt grafikleri de en fazla k olan Hadwiger sayısına sahiptir ve bundan G'nin yozlaşma O( k √ log k ) olması gerekir . Bu nedenle, sınırlı Hadwiger sayısına sahip grafikler seyrek grafiklerdir .   

Boyama

Hadwiger tahmin Hadwiger sayısı kadar büyük zaman en az olduğunu belirtir renk sayısı arasında  G . Yani, Hadwiger sayısı k olan her grafiğin en fazla k renkle renklendirilmiş bir grafiği olmalıdır . Örnek K  = 4 (bu Hadwiger numarası ile grafikler Wagner karakterizasyonu ile) eşdeğerdir dört renk teoremi renklendirici ile düzlemsel grafikler ve saptama, için kanıtlanmıştır k  5 ≤ ama kalıntılar daha büyük değerler için kanıtlanmamış  k .

Çünkü düşük dejenere olması, en çok Hadwiger sayıda grafik k bir ile renklendirilebilir hırslı boyama O (kullanarak algoritma k  √ günlük k ) renkler.

hesaplama karmaşıklığı

Belirli bir grafiğin Hadwiger sayısının en azından belirli bir k değeri olup olmadığının test edilmesi , NP-tamamlanmıştır ve bundan, Hadwiger sayısının belirlenmesinin NP-zor olduğu sonucu çıkar . Bununla birlikte, sorun sabit parametreli izlenebilirdir : yalnızca polinom olarak grafiğin boyutuna, ancak üstel olarak h ( G ) cinsinden bağlı olan bir süre içinde en büyük klik minörünü bulmak için bir algoritma vardır . Ek olarak, polinom zaman algoritmaları, Hadwiger sayısını en büyük tam alt grafiğin boyutuna en iyi polinom zaman yaklaşımından (P ≠ NP varsayarak) önemli ölçüde daha doğru bir şekilde yaklaştırabilir .

Ilgili kavramlar

Renksiz sayısı bir grafik G bir ailesi daraltılmasıyla oluşturulabilir büyük klik boyutudur bağımsız takımdan içinde G .

Sonsuz grafiklerdeki sayılamayan klik küçükleri, belirli takip-kaçınma oyunları için kaçınma stratejilerini resmileştiren sığınaklar açısından karakterize edilebilir : Hadwiger sayısı sayılamazsa, o zaman grafikteki bir sığınağın en büyük sırasına eşittir.

Hadwiger sayısı k olan her grafiğin en fazla n 2 ^{O( k  log log  k )} kliği (tam alt grafikler) vardır.

Halin (1976) , Hadwiger sayısını içeren S- fonksiyonları olarak adlandırdığı bir grafik parametresi sınıfını tanımlar . Grafiklerden tam sayılara kadar olan bu fonksiyonların, kenarları olmayan grafiklerde sıfır olması, küçük monoton olması , önceki tüm köşelere bitişik yeni bir köşe eklendiğinde bir artması ve ikisinden daha büyük bir değer alması gerekir. klik ayırıcının her iki tarafındaki alt grafikler . Tüm bu tür fonksiyonların kümesi, eleman bazında minimizasyon ve maksimizasyon işlemleri altında tam bir kafes oluşturur . Bu kafesteki alt eleman Hadwiger sayısıdır ve üst eleman ağaç genişliğidir .

Notlar

Referanslar