KARAR MODELLERİ - Deneme Sınavı - 9

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. Doğru yanıt B şıkkıdır.

Çizgeyi sistem olarak ele aldığımızda akışa, bu sistem üzerinde gerçekleştirilecek faaliyet gözüyle bakabiliriz. Akışa örnek olarak bir tramvay yolunu kullanan bir dizi tramvayın hareketi, elektrik hattı üzerindeki elektrik akımı veya bir otobandaki araç trafiği verilebilir. İki düğüm arasında karar vericinin belirleyeceği akış miktarı ise tipik bir karar değişkenidir. Doğru yanıt C şıkkıdır.

İki düğümü birbirine bağlayan, birbirinden ayrı bir dizi bağlantıdan oluşan yapıya yol
(yörünge) adı verilir. İki düğüm arasında bir yol söz konusu ise bu iki düğüm birbirine
bağlı sayılır. Doğru yanıt D şıkkıdır.

En kısa yol probleminde amaç düğüm i’den düğüm j’ye doğru en kısa rotanın belirlenmesidir. En kısa yol probleminin çözümünde, başlangıç düğümünden hareketle çizgede yer alan ve başlangıç düğümüne en yakın uzaklıktaki düğümün eklenmesiyle en kısa yolu veren rotanın belirlenmesi amaçlanır. Doğru yanıt E şıkkıdır.

Bir çizge üzerinde, başlangıç noktasından bitiş noktasına malzeme taşıma önemli bir problemdir. 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.) aktarılmasına ilişkindir. Doğru yanıt A şıkkıdır.

En yüksek akış problemi başlangıç düğümünden bitim düğümüne (hedef noktası) ulaştırılacak akışın miktarının en yüksek kılınması olarak tanımlanır. Doğru yanıt B şıkkıdır.

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üğümlere bağlanır.
3. Tüm düğümler bağlanana kadar işleme devam edilir.

Doğru yanıt C şıkkıdır.

Yönlü bağlantı: İki bağlı düğümden birinden diğerine tek yönlü akış olduğunu gösteren
bağlantı biçimidir. Doğru yanıt B şıkkıdır.

Yönlü olmayan bağlantı: İki bağlı düğümden akışın her iki yönde olduğunu gösteren bağlantı biçimidir. Doğru yanıt D şıkkıdı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. 

Doğru yanıt C şıkkıdır.

Düğüm dışına akışın söz konusu olduğu yani düğüm dışına akışın düğüm içine akıştan fazla olduğu düğüme kaynak yada tedarik düğümü denilmektedir.

Doğru yanıt A seçeneğidir.

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

Doğru yanıt C seçeneğidir.

"Döngü içermeyen ve yönlü olmayan bağlantı ile birleştirilmiş düğümlerin oluşturduğu yol ağaç adı verilen bir yapıyı oluşturmaktadır." ifadesi yanlıştır.

Bu nedenle doğru cevap D'dir.

"Bir çizgenin tanımlanmasında (N,S) gösterimi kullanılır. Burada N düğümler kümesini, S ise bağlantılar kümesini göstermektedir." ifadesi doğrudur.

Doğru yanıt B seçeneğidir.

8 düğümden oluşan en yüksek akış probleminde yer alacak aktarma düğüm sayısı başlangıç ve bitiş düğümleri haricinde n-2=8-2=6 olmaktadır.

Doğru yanıt D seçeneğidir.

Çizgede yer alan bağlantıların sayısı 7 olup bunları S bağlantı kümesi ile şu şekilde gösterirriz.

S=(1,2),(1,4),(2,4),(2,3),(3,4),(3,5),(4,5)

Doğru yanıt C seçeneğidir.

Başlagıç düğümü olan 1 nolu düğüme bağlı olan düğümlerden en yakın düğüm 7 birime sahip 4 nolu düğümdür. Bu nedenle bu düğüme [4,1] kalıcı etiketi atanır. Düğüm 4'e doğrudan bağlı olan düğümler 2, 3 ve 5 nolu düğümlerdir. 2 nolu düğüm için en kısa uzaklık değeri 9 olup 2 nolu düğüme [9,1] kalıcı etiketi verilir. 3 nolu düğüme 2 ve 4 nolu düğümlerden bağlantı olmaktadır. 2 nolu düğüm dikkate alınırsa uzaklık (15,2) ve 4 nolu düğüm dikkate alındığında ise uzaklık (10,4) olmaktadır. Bunlar arasında en kısa uzaklık değeri olan [10,4] kalıcı etiket değeri seçilir. 5 nolu düğüm için 3 ve 4 nolu düğümlerden bağlantı olmaktadır. 3 nolu düğüm dikkate alınırsa (14,3) ve 4 nolu düğüm dikkate alınırsa (12,4) uzaklık değerleri bulunur. Bunlar arasında ise en kısa uzaklık değeri olan [12,4] kalıcı etiket değeri seçilir. Böylece 1 ile 5 arasında en kısa yolu veren rota 1-4-5 şeklinde olup 12 birimdir.

Doğru yanıt A seçeneğidir.

Başlagıç düğümü olan 1 nolu düğüme bağlı olan düğümlerden en yakın düğüm 7 birime sahip 4 nolu düğümdür. Bu nedenle bu düğüme [4,1] kalıcı etiketi atanır. Düğüm 4'e doğrudan bağlı olan düğümler 2, 3 ve 5 nolu düğümlerdir. 2 nolu düğüm için en kısa uzaklık değeri 9 olup 2 nolu düğüme [9,1] kalıcı etiketi verilir. 3 nolu düğüme 2 ve 4 nolu düğümlerden bağlantı olmaktadır. 2 nolu düğüm dikkate alınırsa uzaklık (15,2) ve 4 nolu düğüm dikkate alındığında ise uzaklık (10,4) olmaktadır. Bunlar arasında en kısa uzaklık değeri olan [10,4] kalıcı etiket değeri seçilir. 5 nolu düğüm için 3 ve 4 nolu düğümlerden bağlantı olmaktadır. 3 nolu düğüm dikkate alınırsa (14,3) ve 4 nolu düğüm dikkate alınırsa (12,4) uzaklık değerleri bulunur. Bunlar arasında ise en kısa uzaklık değeri olan [12,4] kalıcı etiket değeri seçilir. Böylece 1 ile 5 arasında en kısa yolu veren rota 1-4-5 şeklinde olup 12 birimdir.

Doğru yanıt D seçeneğidir.

Kaynaktan bitim düğümüne pozitif akış sağlayabilecek yollardan birisi 1-3-2-4 olmaktadır. Bu yoldan gönderilebilecek en yüksek miktar 3 birim olmaktadır. Yol üzerindeki akış kapasiteleri ileri doğru 3 birim azaltılırken geri doğru 3 birim arttırılır. Sonrasında oluşturulan çizge üzerindeki 1-2-4 yolu üzerinden gönderilebilecek en yüksek miktar 3 birim olmaktadır. Sonrasında oluşturulan çizge üzerindeki 1-3-4 yolu üzerinde gönderilebilecek en yüksek miktar 4 birim olmaktadır. Bunun sonucunda kaynaktan bitim düğümüne pozitif akışın olanaklı olduğu yolun bulunmadığı görülür. Bu durumda kaynaktan bitime gönderilebilecek miktar her iterasyon sonunda gönderilen toplam miktar olan 3+3+4=10 birimdir.

Doğru yanıt B seçeneğidir.

Keyfi olarak başlangıç düğümü seçilir. Sonrasında bu düğüme bağlanabilecek düğümler olan 2 ve 4 nolu düğümler arasından 8 birimli 4 düğümü seçilir. Seçilen 4 nolu düğüme bağlanabilecek düğümler olan 2,3,5 ve 6 nolu düğümler arasından 4 birimli 6 nolu düğüm seçilir. Seçilen 6 nolu düğüme bağlanabilecek olan 5 ve 7 nolu düğümlerin arasından 2 birim uzaklığa sahip 7 nolu düğüm seçilir. Seçilen 7 nolu düğüme bağlanabilecek olan 3 birimlik 5 nolu düğümdür. 5 nolu düğüme 4 birimlik uzaklığa sahip olan 3 nolu düğüm bağlanır ve son olarak da 3 nolu düğüm 5 birim uzaklıktaki 2 nolu düğüme bağlanmaktadır. Depolardaki bağlanma sırası 1-4-6-7-5-3-2 olup toplam bağlanılacak mesafe ise 8+4+2+3+4+5=26 birimdir.

Doğru yanıt B seçeneğidir.