GRAFİK ALGORİTMASI

 Grafik Algoritması

   

    Grafik, nesne çiftleri arasındaki bağlantıyı temsil etmek için kullanılan soyut bir
    notasyondur. Bir grafik oluşur −

• Köşeler − Grafikteki birbirine bağlı nesnelere köşe denir. Köşeler düğümler olarak da bilinir.

• Kenarlar − Kenarlar köşeleri birbirine bağlayan bağlantılardır.

                 İki tür grafik vardır −

• Yönlendirilmiş grafik − Yönlendirilmiş bir grafikte, kenarların yönü vardır, yani kenarlar bir tepe noktasından diğerine geçer.

• Yönlendirilmemiş grafik − Yönlendirilmemiş bir grafikte kenarların yönü yoktur.

Grafik Renklendirme

Grafik renklendirme, iki bitişik köşenin aynı renge sahip olmaması için grafiğin köşelerine renk atama yöntemidir. Bazı grafik renklendirme problemleri −

• Köşe renklendirme − Bir grafiğin köşelerini, bitişik iki köşenin aynı rengi paylaşmaması için renklendirmenin bir yoludur.

• Kenar Renklendirme − Her kenara bir renk atama yöntemidir, böylece bitişik iki kenar aynı renge sahip olmaz.

• Yüz boyama − Düzlem grafiğinin her yüzüne veya bölgesine bir renk atar, böylece ortak bir sınırı paylaşan iki yüz aynı renge sahip olmaz.

Kromatik Sayı

Renklendirme sayısı, grafiği renklendirmek için gereken minimum renk sayısıdır. Örneğin, aşağıdaki grafiğin kromatik sayısı 3'tür.

Grafik renklendirme kavramı, haritaların hazırlanmasında, mobil radyo frekansı atamasında, Suduku'da, kayıt tahsisinde ve renklendirmede uygulanır.

Grafik boyama adımları

• N boyutlu dizideki her işlemcinin başlangıç değerini 1 olarak ayarlayın.

• Şimdi bir tepe noktasına belirli bir renk atamak için, bu rengin bitişik köşelere zaten atanmış olup olmadığını belirleyin.

• İşlemci bitişik köşelerde aynı rengi algılarsa, dizideki değerini 0 olarak ayarlar.

• n yaptıktan sonra2 karşılaştırmalar, dizinin herhangi bir öğesi 1 ise, geçerli bir renklendirmedir.

Grafik renklendirme için sahte kod

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

En Kısa Yol Algoritması

En Kısa Yol algoritması, kaynak düğümden hedef düğüme (D) en az maliyetli yolu bulma yöntemidir. Burada, Moore'un Breadth first search algorithm olarak da bilinen algoritması tartışacağız.

Moore'un algoritması

• Kaynak köşeyi etiketle, S ve i olarak etiketle ve i=0'ı ayarla.

• i etiketli köşeye bitişik tüm etiketsiz köşeleri bulun. Köşeye hiçbir köşe bağlı değilse, S, o zaman köşe, D, S'ye bağlı değildir. S'ye bağlı köşeler varsa, bunları i+1 olarak etiketleyin.

• D etiketliyse, 4.

• En kısa yolun uzunluğu bulunduktan sonra durun.