DFS Açgözlü Kromatik Sayı

Question

Okulumda rasgele bir grafiğin kromatik sayısını hesaplamanın NP-Complete olduğunu öğrendim. Greddy algoritmasının neden işe yaramadığını anlıyorum, ama DFS/Açgözlü algoritma ne olacak? Ana fikir, henüz tüm renkli olmayan tüm köşeler için bir DFS yapar ve tüm komşular üzerinde minimum renk indeksini alır.

Sayaçlı bir örnek anlayamıyorum ve bu soru aklımdan çıkıyor. Tüm cevaplarınız için teşekkürler.

yalancı kod

Chromatic(Vertex x){ 
    for each neighbour y of vertex x 
     if color(y) = -1 
      color(y) <- minimum color over all the neighbours of y 
      if(y>=numColor) numColors++; 
      Chromatic(y); 
} 
Main(){ 
    Set the color of all vertex equal -1 
    Take an arbitrary vertex u and set color(u) = 0 
    numColors = 1; 
    Chromatic(u); 
    print numColors; 
} 

Answer 1

cevap bazen mevcut 2 renk olan bir köşe olacak ve yanlış bir seçim yapma sonra sorunu henüz belirlenemeyen bir süre neden olacaktır.

1 - 9 arası köşeleriniz olduğunu varsayalım. Daha sonra aşağıdakileri yapmak için kenarları ekleyin.

1, 2, 3 bir üçgen oluşturur. 3, 4'e bağlanır. 4, 5, 6 bir üçgen oluşturur. 5, 6, 7 bir üçgen oluşturur. 6, 7, 8 bir üçgen yapın. 7, 8, 9 bir üçgen yapın. 8, 9, 1 bir üçgen yapın. 9, 1, 2 bir üçgen yapın.

3 renkle renklendirmek kolaydır. petersen graph: Ama bir derinlik ilk açgözlü algoritma yanlış tercihi haline tepe 4. verebileceğiniz ve 4 renk değil, 3.

Answer 2

İşte somut counterexample var ihtiyacı dolayacaksın 2 renk seçeneği vardır. Kişisel algoritma olursa olsun (Sanırım) başlatmak nerede, 4 hesaplar, ancak grafiğin renk indeksi için de 3.

petersen grafik grafik sorunlarının birçok açgözlü girişimleri için bir klasik counterexample olduğunu ve grafik teorisinde varsayımlar.