Düğüm Derecesi (Order of Node)


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:

euler1

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:

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:

yonlugraf

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.


« Denkşekillilik (Isomorphism)   |   Laplas Matrisi (Laplacian Matrix) »



Yorumlar

Kullanıcı girişi yaparak ya da zorunlu olan * alanlarını doldurarak yorum yapabilirsiniz.

İsminiz *

Email adresiniz *

Web siteniz

Mesajınızı buraya yazabilirsiniz:

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Düğüm Derecesi (Order of Node)' isimli yazı 18 Jun 2009 tarihinde, saat: 02:53 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 569 defa okunmuştur.

Benzer yazıları graf teorisi (graph theory, çizge kuramı) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar