Yazan : Şadi Evren ŞEKER

Bir ağacın dış düğümlerine ayrı ayrı ulaşılması için geçilmesi gereken yol miktarıdır. Örneğin aşağıdaki ağaç için bu değeri hesaplayalım:

yukarıdaki ağaçta kırmızı renkli düğümler iç düğümdür. Siyah renk ile gösterilen düğümleri ise dış düğümlerdir.

Buna göre kökten başlandığında ağacın sol tarafında 1 adet dış düğüm vardır ve erişim 1 yolla yapılır. Ağacın sağında 3 adet dış düğüm vardır. Bunlardan en soldakine 3 sağındakine 3 en sağdakine ise 2 yol ile ulaşılır. Dolayısıyla bu ağacın dış düğüm sayısı 1+3+3+2 = 9 olarak bulunur.

Bir ağacın iç yol uzunluğu (internal path length) biliniyorsa dış yol uzunluğu aşağıdaki şekilde hesaplanabilir:

E = I + 2n

I: iç yol uzunluğu

E: dış yol uzunluğu

n: iç düğüm sayısıdır.

Yukarıdaki örnekte iç yol uzunluğu 3’tür. İç düğüm sayısı da 3 tür. Dolayısıyla E = 3 + 2×3 = 9 bulunabilir.

Yukarıdaki grafiğin iç yol uzunluğu için ilgili yazıyı okuyabilirisiniz.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


sekiz × 8 =