Merhaba arkadaşlar, bu yazımda graf’ın tanımını yapıp kullanımını alanlarını söyledikten sonra grafların renklendirilmesine bakacağız.
Graf kelime anlamı olarak grafik, çizelge, diyagram gibi anlamlara gelmektedir. Bilgisayar terimi olarak kullanımı ise gerçek hayatta karşılaşılan problemleri örneğin coğrafi gösterimleri bilgisayar dünyasında ifade etmek amacıyla kullanılan şekillerdir.
Kullanım Alanları
Ağ sistemleri, coğrafi şekil ve gösterimler, en kısa yol problemlerinde kullanımı bulunmaktadır. Harita uygulamaları bu mantıkla çalışmaktadır. Aşağıda bir graf örneği verilmiştir.
Üstteki görselde her bir harf bir şehri temsil ediyor gibi düşünebilirsiniz.
Yönlü ve Yönsüz Graflar
Basit bir örnekleme ile bir şehire gidiş yolu var dönüş yolu yok ise yön belirtmek gerekmektedir. İlk verdiğimiz örnek yönsüz bir graftı. Aşağıdaki örnek ise yönlü bir graftır.
[the_ad id=”1292″]
Ağırlıklı ve Ağırlıksız Graflar
Bir düğümden diğer bir düğüme geçerken aradaki yollarımızın uzunluğudur. Yukarıda verdiğimiz örneklerde ağırlıksız graflar vardı. Şimdi ise ağırlıklı bir grafın örneğini verelim.
Aynı şekilde yönsüz grafların da ağırlıklı hali bulunabilir ama daha çok kullanımı yukarıdaki gibidir. Burada 67 numaralı düğüme hiç bir yol gitmiyor olması hata olduğu anlamına gelmemektedir.
Graflarda Renklendirme
Öncelikle nerede kullanılır ona küçük bir örnek vermek istiyorum. Türkiye haritasını önümüze aldığımızda yan yana olan şehirlerin hiç birisi aynı renkte değildir. Ya ders programları hazırlanırken graflardan faydalanılmaktadır. Bu bir renklendirme örneğidir. Aynı şekilde de graflarda birbirine bağlı iki graf aynı renkte olamıyor.
Graf Renklendirme Kuralları
1) Her düğümün bağlı olduğu düğüm sayıları bulunur. Buna derece denilmektedir.
2) Derecesi en büyük olana istediğiniz bir rengi verin
3) İkinci düğüme de aynı şekilde eğer ilk düğümle bağı yoksa ilk verdiğiniz rengi verin. Eğer bağ varsa ikinci bir renk seçin. Bu şekilde devam eder.
4) En az renk kullanılarak tüm düğümler renklendirilmiş olur.
Bu renklendirme algoritmasına Welch ve Powel Algoritması denilmektedir. Detayları araştırabilirsiniz.
Aşağıda renklendirilmiş bir graf örneği verilmiştir. Eğer aynı dereceye sahip düğümler varsa alfabetik sıra, sayısal değer varsa küçük sayı önceliklidir.
Umarım faydalı olmuştur. Bir sonraki yazımda da Graf üzerinde dolaşma algoritmalarına bakarız 🙂
