Yazan : Şadi Evren ŞEKER

Graf teorisinde (graph theory) bir grafın temel unsurlarından olan düğümlerin (nodes) giren veya çıkan kenar (edge) sayısını verir.

Tanım olarak yönsüz graflar (undirected graphs) ve yönlü graflar (directed graphs) için iki ayrı tanım yapılabilir.

Yönsüz graflarda bir düğümün derecesi

Yönsüz graflarda bir düğümün derecesi, doğrudan düğüme bağlı komşu düğüm sayısına veya o düğüme bağlı kenar sayısına eşittir.

Örneğin aşağıdaki yönsüz grafı (undirected graph) ele alalım:

Yukarıdaki bu grafta bulunan düğümlerin dereceleri aşağıda listelenmiştir:

A 5

B 3

C 3

D 3

Görüldüğü üzere düğümlerin dereceleri komşu olduğu düğümlerin sayısı veya o düğüme bağlı olan kenar sayısı olarak bulunabilir.

Yönlü graflarda düğüm derecesi

Yönlü graflarda(directed graphs) düğüm derecesinden bahsedilirken iki farklı değer bulunabilir:

• Giren derecesi (Inorder)
• Çıkan derecesi (outorder)

Bir düğümün giren derecesi yönü düğüme doğru olan kenar sayısıdır. Aynı zamanad bir düğüme ulaşılabilen diğer düğümlerin sayısıdır.

Çıkan derecesi ise bir düğümden çıkan kenarların sayısı veya bir düğümden ulaşılabilen diğer düğümlerin sayısı olarak tanımlanır.

Daha iyi anlaşılması için aşağıdaki grafı ele alalım:

Yukarıda gösterilen yönlü graftaki düğümlerin giren dereceleri (in order) aşağıdaki şekilde sıralanabilir:

A 1

B 2

C 2

D 2

E 2

Benzer şekilde çıkan dereceleri (out order) de aşağıda verilmiştir:

A 2

B 1

C 2

D 2

E 2

Dikkat edilirse bir graftaki çıkan dereceleri ile giren derecelerinin toplamı eşit olmalıdır. Örneğimizde 9 = 9 durumu doğrudur.