Ağ Yapıları

Bir ağ yapısı (graph) "nod" adı verilen düğüm noktaları ve bunlar arasındaki bağlantılardan oluşur. İngilizce kaynaklarda nodlar arası bağlantılara edge denir.

Bir ağ yapısında bağlantılara atanmış "ağırlık" (weight) değerleri olabilir. Bunlar yukarıdaki gibi bağlantı uzunlukları da olabilir, taşıma kapasiteleri de olabilir. Bir ağ yapısı bağlantılarında birden fazla türden ağırlık değeri de olabilir. Çözeceğiniz problem tipine göre belli türden ağırlık değerine odaklanırsınız.

Ağ yapıları üzerinde çözülecek problem tiplerine geçmeden önce, ağ yapıları hakkında bazı temel bilgiler sunmalıyız:

1. Ağ yapıları bağlantıların yönlenişine göre ikiye ayrılırlar:

a. Yön kısıtlaması olmayan bağlantılardan oluşan ağlar "yönsüz" (undirected) ağlardır. Yukarıdaki örnek resimdeki ağ bir yönsüz ağdır.

b. Yön kısıtlaması olan ağlar (tek yönlü sokaklardan oluşan bir şehir merkezi gelsin aklınıza) "yönlü" (directed) ağdır.

2. Yönsüz bir ağda herhangi iki nod arasında ancak tek bir bağlantı olabilir. Bu durumda, N nodu olan bir ağ yapısında ilk nod (yukarıdaki 0 nolu nod) diğer N-1 tanesine, ikinci nod (yukarıdaki 1 nolu nod) kalan N-2 tanesine, üçüncü nod kalan N-3 tanesine, … bağlanabilir. Sonuç olarak yönsüz bir ağda olabilecek en fazla bağlantı sayısı (N-1) + (N-2) + (N-3) + … + 2 + 1 = N*(N-1)/2 olacaktır.

3. Yönlü bir ağda herhangi iki nod arasında iki bağlantı olabilir. Yani her nod diğer her noda bağlı olabilir, bir o yönden, bir de tersi yönden. Bu nedenle de yönlü ağın maksimum bağlantı sayısı N*(N-1) kadar olacaktır.