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