Ünite 7: Çizge Modelleri

GİRİŞ

Sunucular, şehir vb. birbiriyle ilişkide olan varlıklardan oluşan sistemler olarak yollar ve kablolarla birbirine bağlanırlar. Varlıkları ve varlıklarını birbirine bağlayan bağlantılardan oluşan yapı, çizelge modellerinin temellerini oluşturur. Çizge modelleri proje planlama, üretim, tesis yeri, sosyal grup yapı analizleri gibi çok farklı problemlerde kullanılmaktadır.

Çizge modelleri sistemin bileşenleri arasındaki ilişkileri göstermede görsel ve kavramsal destek sağlamaktadır. Bunun bir sonucu olarak çizge modelleri ile gösterime ekonomi, sosyal ve fen bilimleri gibi pek çok farklı problemlerde kullanılmaktadır.

Çizge Modellerinde Temel Kavramlar

Bir çizge yapısı düğüm adı verilen bir dizi nokta ve bu düğümlerden bazıları veya tamamını birbirine bağlayan bir dizi çizgiden (bağlantıdan, yaydan) oluşur. Bir çizgenin tanımlanmasında (N,S) gösterimi kullanılmaktadır. Bir çizge problemi, N={1,2,3,…,n} düğüm ve bu düğümleri birbirine bağlayan bağlantıların S={(a,b),(c,d),..,(y,z)} kümesi ile ifade edilir. Akış, sistem olarak ele aldığımızda, sistem üzerinde gerçekleştirilecek faaliyetin çizgede ifadesidir. Tramvay yolunu kullanan bir dizi tramvayın hareketi, elektrik hattı üzerindeki elektrik akışı, otobandaki araç trafiği akışa örnek verilebilir. Bazı durumlarda akış, bağlantıların kapasitesine bağlı olarak sınırlandırılmaktadır. Yönlü bir bağlantıda maksimum akış miktarı bağlantı kapasitesi olarak adlandırılır.

Düğüm dışında akışın söz konusu olduğu (düğüm dışında akışı düğüm içine akıştan fazla olduğu) düğüm kaynak ya da tedarik düğümü olarak isimlendirilir. İçine ve dışına akış olan düğüm talep düğümü; tedarik ve talep düğümleri arasındaki akış sırasında içine ve dışına akışın olduğu düğüm ise karma düğüm olarak adlandırılır. Bir coğrafi bölgedeki şehirleri örnek gösterirsek; şehirler çizelgedeki düğümlere, şehirleri birbirine bağlayan kara yolları bağlantılara, bağlantılar üzerindeki araçların hareketi ise akışları oluşturur.

Düğümler birbiriyle birleştirilen bağlantılar yönlü ve yönlü olmayan yönsüz olmak üzere ikiye ayrılmaktadır. Bir düğümden diğerine akış tek yönlü olduğunda bu durum, başlangıç düğümünden uç düğüme çizilen çizgiye uç düğüm noktasını gösteren birleşim noktasına bir ok getirilerek gösterilir. Eğer ok kullanılmaz ise iki düğümü bağlayan çizgi yönlü olmayan bağlantı olarak isimlendirilir ve akışın her iki yöne de (iki merkez arasında akışın söz konusu olduğunu bir boru hattı örneği gibi) olabileceğini gösterir. Yönlü bağlantılardan oluşan çizge, yönlü çizge adını alırken; yönlü olmayan bağlantılardan oluşan çizge ise yönlü olmayan çizge adını alır.

İki düğümü birbirine bağlayan birbirinden ayrı bir dizi bağlantıdan oluşan yapıya yol denir. Bu yolun diğer bir adı da yörüngedir. Başlangıç ve bitiş noktalarının aynı düğüm olduğu, başladığı noktaya geri dönen bağlantıların oluşturduğu yol döngü adını alır. Bir çizgeyi oluşturan tüm düğümler birbirine bağlı olduğunda, bu çizgeler bağlı çizgeler olarak adlandırılır. Döngü içermeyen ve yönlü olmayan bağlantı ile birleştirilmiş düğümlerin oluşturduğu yol ise ağaç olarak adlandırılır. Ağaç, n tane düğümü olan bir çizgenin döngü içermeyen bir alt kümesi olarak ele alınabilir.

En Kısa Yol Problemi

N düğüm ve m bağlantıdan oluşan bir çizgede bir başlangıç noktası (düğüm i) ve bir bitiş noktası (düğüm j) belirlensin. En kısa yol probleminde amaç düğüm i’den düğüm j’ye doğru en kısa (en az bağlantını kullanılmasıyla) rotanın belirlenmesidir.

En kısa yol probleminin çözümünde, başlangıç düğümünden hareketle çizgede yer alan başlangıç düğümüne en yakı uzaklıktaki düğümün eklenmesiyle en kısa yolu veren rotanın belirlenmesi amaçlanır. Bu işlemler yerine getirilirken düğümler çözüme ulaşıncaya kadar geçici ve kalıcı olmak üzere etiketlenir. Geçici olarak etiketlenen düğümler, bu düğümler arasında daha kısa bir rota bulunması durumunda değiştirilir; bulunamaması durumunda kalıcı olarak etiketlenir.

Kalıcı etiketler [], geçici etiketler () ile gösterilir. Herhangi bir düğüm için geçici etkilet (d,n) olarak genellendiğinde; etiketin ilk değeri (d) başlangıç düğümüne olan uzaklığı; ikinci değeri (n) ise bağlandığı düğümün numarasını temsil eder. Buna göre 1 numaralı düğüme kendisinden önce herhangi bir düğüm olmadığından [0,-] etiketi verilir. En kısa yol probleminin adımlar:

1. Adım: Başlangıç düğümü 1 nolu düğüm olarak belirlenir.

2. Adım: Başlangıç düğümü olan 1 nlu düğüme doğrudan bağlı olan düğümler için (d,n) geçici etiket değerleri verilir.

3. Adım: Geçici atama yapılmış düğümlerdeki etiketler dikkate alınarak içlerindeki en kısa uzaklığa sahip düğüm seçilir. Bu düğüm k düğümü olarak isimlendirilir ve k düğümün etiketi kalıcıya çevrilir.

4. Adım: k. Düğüme doğrudan bağlı geçici etikete sahip düğümler dkikate alınarak;

u=(k’den i’ye uzaklık) + (k’nın başlangıç düğümüne uzaklığı)

u > ise (u,k) geçici etiketi verilir,

u ? ise geçici etiket korunur.

5. Adım: Kalıcı etiketin olmadığı düğümlerde bir düğüm için geçici etiketler verilmemiş ise düğüm için (u,k) hesaplaması yapılır ve 3. Adım ‘a geçilir.

6. Başlangıç düğümünden itibaren yapılan atamalar dikkate alınarak başlangıç düğümünden istenen varış düğümüne en kısa yola ait rota bulunur.

En kısa yol probleminin uygulamaları, sadece başlangıç ve bitiş noktaları arasında en kısa yolu veren rotanın hesaplanması ile sınırlı değildir. Düğümleri birbirine bağlayan bağlantılar faaliyetleri tanımlandığında bu kez amaç en az toplam maliyeti veren bir dizi faaliyetin belirlenmesi olacaktır. Yine bağlantılar üzerindeki faaliyetlerin süreleri bilindiğinde bir dizi faaliyetin en kısa sürede tamamlanması da en kısa yol problemi için uygulama alanı oluşturacaktır. Bu durumda en kısa yol problemlerinin; toplam yolun, toplam maliyetin ve toplam sürenin en küçüklenmesi olmak üzere üç grupta toplandığı söylenebilir.

En kısa yol probleminin bir başka uygulaması ise başlangıç noktasından varış noktasına değil diğer tüm noktalara (düğümlere) en kısa rotanın belirlenmesi biçimindedir. Bu durumda başlangıç düğümü dışındaki tüm düğümler varış noktası gibi ele alınır.

En Yüksek Akış Problemi

En yüksek akış problemleri bütün akışın çıkış yaptığı “Kaynak” olarak isimlendirilen düğümden, akışın ulaştırıldığı “Bitim” olarak isimlendirilen düğüme malzemenin (su, petrol, gaz, veri, elektrik, mamül vb.) çokça aktarılmasıyla ilişkilidir. Bir petrol sahasından çıkarılan ham petrolün bir petrol rafinerisine boru hattı ile ulaştırılmasına ilişkin bir çizge ele alalım. Bu çizgenin maksimum kapasitesinin ne olacağının belirlenmesi en yüksek akış problemine örnek oluşturur. Ham petrolün petrol sahasından rafineriye ulaşana kadar belirli aralıklarla akışını sağlayacak pompalama istasyonlarına ihtiyaç duyulacaktır. Akışın gerçekleşeceği başlangıç ve bitim düğümleri arasında kullanılan boruların bir akış kapasitesi söz konusu olacaktır. Böyle bir çizgenin taşıyabileceği en büyük miktarın belirlenmesi en yüksek akış problemi örneği oluşturur. En yüksek akış problemi başlangıç düğümünden bitim düğümüne (hedef notktası) ulaştırılacak akış miktarının en yüksek kılınması olarak tanımlanmaktadır.

En yüksek akış probleminin çözümünde aşağıdaki işlemler yerine getirilir:

1. Başlangıç düğümünden bitim düğümüne giden malzemenin pozitif (sıfırdan farklı) uygun akışını sağlayacak yol belirlenir.
2. Belirlenen yol üzerinde bağlantıların kapasiteleri dikkate alınarak (akış kapasitesi en küçük olan seçilerek) yüklenebilecek en yüksek akış belirlenir.
3. Kalan akış kapasiteleri, akış yönüne göre, akışın gönderildiği yöne doğru azaltılarak akışın yönünde ise artırılarak gözden geçirilir.
4. Adım 1’e dönülür.
5. Bitim düğümüne gönderilen miktar en yüksek akıştır, En iyi çözüme ulaşılmıştır.

En Küçük Yayılma Problemi

En küçük yayılma problemlerinde çizgedeki tüm düğümleri birbirine bağlayan en kısa yolun bulunması amaçlanmaktadır. En küçük yayılma problemlerinin genel yapısı aşağıdaki maddeler biçiminde açıklanmıştır.

• Problemde n tane düğüm vardır.
• Problemdeki çizge yapıda düğümleri birbirine bağlayan bağlantılar yönlü olmayan bağlantılardır ve düğümler arası uzaklıkları (maliyet, süre) göstermektedir.
• Tüm düğümleri birbirine bağlayacak biçimde yeterince bağlantı kullanılarak bir çizge tasarlanır.
• Bu tip bir çizge tasarlanırken toplam uzunluğu en kısa yapacak şekilde bağlantılar seçilmektedir.

En küçük yayılma problemlerinin çözümünde aşağıdaki işlemler yerine getirilir:

1. Çizge içerisinde rastgele bir düğüm seçilir. Bu düğüm kendisine en yakın düğüme bağlanır.
2. Bağlanmamış düğümler arasından, bağlanmış düğümlere komşu düğümler içerisinden en yakın olan seçilerek bu düğüme bağlanır.
3. Tüm düğümler bağlanan kadar işleme devam edilir.

En küçük yayılma problemi uygulamalarına;

• Bir dizi yerleşim birimini bağlayan boru hattı çizgesinin tasarımı,
• Ulaşım (demiryolu, karayolu) çizgesinin tasarımı,
• Yüksek gerilim hatlarının tasarımı,
• Telekomüinkasyon çizgesinin (fiberontik ağlar, kablo tv vb.) belirlenmesi örnek olarak verilebilir.