KARAR MODELLERİ - Deneme Sınavı - 8

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.

Tedarik ve talep düğümleri arasındaki akış sırasında içine ve dışına akışın olduğu düğüm ise aktarma düğümü olarak adlandırılır.

İki düğümü birbirine bağlayan, birbirinden ayrı bir dizi bağlantıdan oluşan yapıya yol (yörünge) adı verilir.

n adet düğümden oluşan bir çizgede, n düğüm döngü oluşturmayacak biçimde n-1 bağlantı kullanılarak birleştirildiğinde ise oluşturulan ağaca kapsayan ağaç denir.

Bir çizgede bağlantılar birleştirdikleri (her iki uçtaki) düğümler kullanılarak isimlendirilir.

Yönlü olmayan bağlantı: İki bağlı düğümden akışın her iki yönde olduğunu gösteren bağlantı biçimidir.

1 ve 6 düğümleri arasındaki en kısa rota 1-3-4-6 yoludur.

1-3-4-6 rotası en kısa yol olup uzunluğu 11 dir.

En küçük yayılma problemlerinde Problemdeki çizge yapıda düğümleri birbirine bağlayan bağlantılar yönlü olmayan bağlantılardır ve düğümler arasındaki uzaklıkları (maliyet, süre) göstermektedir. Bu çizge tasarlanırken toplam uzunluğu en kısa yapacak şekilde bağlantılar seçilmektedir. Çizge içerisinde rastgele bir düğüm seçilir. Bu düğüm kendisine en yakın düğüme bağlanır. Tüm düğümler bağlanana kadar işleme devam edilir.

Çizge modellerinin iki temel uygulaması vardır.

A’ dan B’ ye ikisi arası arasındaki fark olan 2 birim kadar olacaktır.

"Düğümleri birbirleri ile birleştiren bağlantılar üçe ayrılmaktadır." şıkkı için bağlantılar ikiye ayrılmaktadır. "Ok eklenerek yapılan bağlantı yönlü olmayan bağıntıdır." şıkkı için ok kullanılıyorsa bu yönlü bağlantıyı ifade etmektedir. "Bir çizgenin asla bir kısmı yönlü bir kısmı yönsüz bağlantılardan oluşmaz." şıkkı için bir çizge bir kısmı yönlü bir kısmı yönsüz bağlantılardan oluşabilir. "Yönlü olmayan bağlantıda akış asla iki yönde de olmaz." şıkkında yönlü olmayan bağlantıda akış iki yönde de olabilir cevapları ile doğru seçenek "Çizgeler eğer istenirse yönsüz bağıntılar iki zıt akışı simgeleyen iki yönlü bağlantı kullanılarak yönlü çizgeye dönüştürülebilir." şıkkı doğrudur.

I-II-IV-VI-III-V doğru seçenektir.

Problemde n tane düğüm vardır.

En yüksek akış akış problemi "Haberleşme sisteminde en yüksek bilgi akışının belirlenmesi" seçeneğidir.

En küçük yayılma problemi örneği "Ulaşım çizgesinin tasarımı" seçeneğidir.

Bir çizgeyi oluşturan tüm düğümler birbirine bağlı olduğunda bu çizgeler bağlı çizgeler olarak adlandırılır.

İki düğümü birbirine bağlayan birbirinden ayrı bir dizi bağlantıdan oluşan yapıya yörünge (yol) adı verilir.

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. Bu gösterimde N düğümlerin kümesi, S ise bağlantılar kümesidir. 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.

Bağlantı İki düğümü birbirine bağlayan çizgidir. Yay olarak da adlandırılır.