veri yapıları logo

Graf Nedir, Kullanımı ve Renklendirilmesi

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.

graflar örnek

Ü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.

yönlü graf

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.

ağırlıklı yönlü graf

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.

 

renklendirilmiş graf

Umarım faydalı olmuştur. Bir sonraki yazımda da Graf üzerinde dolaşma algoritmalarına bakarız 🙂

Bir cevap yazın