Kromatik Sayı ve Kritik Graf Sorusu

Merhaba Seda, bu videoda seninle birlikte bu grafın kromatik sayısını bulacağız ve ardından grafik yapısını inceleyerek kritik bir graf olup olmadığını belirleyeceğiz.

İşte grafımızın sadeleştirilmiş ve temiz bir çizimi. Köşelerimizi birer birer isimlendirerek analizimizi yapalım.

İlk olarak sol taraftaki bir, iki, üç ve dört numaralı köşelere odaklanalım. Bu dört köşe kendi aralarında tamamen birbirine bağlıdır.

Bir tam graf, tüm köşe çiftleri arasında bir kenar bulunduran graftır. Dört köşeli tam grafı, yani ka dört grafını sol tarafta görebiliyoruz.

Aynı analizi sağ taraftaki beş, altı, yedi ve sekiz numaralı köşeler için de yapabiliriz. Bu köşeler de kendi aralarında bir tam graf oluşturur.

Şimdi dokuzuncu köşeyi inceleyelim. Dokuz numaralı köşe, sol taraftaki tüm köşelere, yani bir, iki, üç ve dörde bağlıdır.

Sol taraftaki ka dört tam grafına dokuzuncu köşeyi eklediğimizde, beş köşeli bir tam graf olan ka beş grafını elde ederiz.

Benzer şekilde, dokuz numaralı köşe sağ taraftaki beş, altı, yedi ve sekiz numaralı köşelerin hepsine de bağlıdır.

Dolayısıyla, sağ taraftaki alt graf ile dokuz numaralı köşenin birleşimi de beş köşeli başka bir tam graf, yani ka beş oluşturur.

Harika! Grafımızın yapısını anladık. Grafımız aslında dokuz numaralı köşe üzerinden birleştirilmiş iki adet ka beş tam grafından oluşmaktadır. Şimdi kromatik sayıyı hesaplayalım.