Examkin

Question

Difficulty: HardŞebeke Modellerinde Temel Kavramlar

Yöneylem araştırmasında karmaşık sistemlerin optimizasyonu (örneğin en kısa yol, maksimum akış) şebeke (ağ) modelleri üzerinden gerçekleştirilir. Bu analizlerde düğüm, ayrıt, yol, çevrim ve ağaç gibi topolojik kavramların yapısal özellikleri çözüm algoritmalarının matematiksel altyapısını oluşturur.

Buna göre, şebeke modellerindeki temel kavramların özellikleri dikkate alındığında aşağıdaki ifadelerden hangisi kesinlikle doğrudur?

  1. Bağlantılı bir şebekeye ait herhangi bir yayılan ağaca (spanning tree), ağaç dışında kalan bir ayrıtın (kirişin) eklenmesi, sistemde tam olarak bir adet temel çevrim (fundamental cycle) oluşturur.Answer
  2. B
    Yönlü bir şebekede başlangıç ve bitiş düğümleri aynı olan tüm kapalı yürüyüşler (closed walks), hiçbir düğümün tekrar edilmediği basit birer yönlü çevrim (simple directed cycle) belirtmek zorundadır.
  3. C
    Şebeke üzerindeki aktarma düğümlerinin (transshipment nodes) akış dengesini sağlayabilmesi için, bu düğümlere giren ayrıt sayısı ile bu düğümlerden çıkan ayrıt sayısının topolojik olarak birbirine eşit olması gerekir.
  4. D
    Toplam nn adet düğümden oluşan ve her düğüm çifti arasında bir bağlantı bulunan tam yönsüz şebekelerde (complete undirected networks), toplam ayrıt sayısı n2n^2 formülü ile belirlenir.
  5. E
    Bir şebekede tanımlanan yönlü bir yol (directed path) üzerinde yer alan düğümler takip edildiğinde, ardışık bazı ayrıtların ana akış yönüne ters yönde yönlendirilmiş olması mümkündür.

Answer

Bağlantılı bir şebekeye ait yayılan ağaca ağaç dışı bir ayrıtın eklenmesiyle tam olarak bir adet temel çevrimin oluştuğunu belirten ifadedir.
Yayılan ağaç (spanning tree), bağlantılı bir şebekedeki tüm düğümleri birbirine bağlayan ancak içinde hiçbir çevrim barındırmayan alt şebekedir. Bu ağaçtaki herhangi iki düğüm arasında sadece tek bir basit yol bulunur. Bu nedenle, ağaçta yer almayan bir ayrıt (buna kiriş veya chord denir) ağaca eklendiğinde, bağladığı iki düğüm arasındaki mevcut ağaç yoluna alternatif bir bağlantı oluşturur ve bu iki yol birleşerek sistemde tam olarak bir adet kapalı çevrim (temel çevrim) meydana getirir. Bu mantık, Yöneylem Araştırmasında Atlama Taşı (Stepping-Stone) algoritması ve Ağ Simpleks (Network Simplex) yönteminde çözüm geliştirmek için kullanılan temel topolojik kuraldır.

Step-by-Step Solution

1
Yayılan ağaç (spanning tree) kavramının temel topolojik özelliklerini analiz et.
Yayılan ağaç, nn düğümlü bağlantılı bir şebekedeki tüm düğümleri kapsayan, tam olarak n−1n-1 ayrıttan oluşan ve kesinlikle çevrim (cycle) içermeyen alt grafiktir.
Topolojik analizde doğru ve yanlış ifadeleri ayırmak için temel tanımların net olarak bilinmesi gerekir.
2
Yayılan ağaca yeni bir ayrıt (kiriş) eklemenin etkisini değerlendir.
Ağaç halihazırda tüm düğümler arasında tek ve benzersiz bir yol (path) barındırdığından, herhangi yeni bir ayrıt eklendiğinde bu ayrıt, birleştirdiği iki düğüm arasındaki mevcut yol ile birleşerek tek bir kapalı döngü yaratır.
Bu özellik 'Temel Çevrim' (Fundamental Cycle) olarak adlandırılır ve doğrusal programlamada (örneğin ağ simpleks yönteminde) yeni değişkenin temel çözüme girmesi mantığını açıklar.
3
Diğer seçeneklerdeki kavram yanılgılarını belirle.
Yürüyüş ve basit çevrim tanımlarının karıştırıldığı, akış kısıtlarında miktar yerine ayrıt sayısına odaklanıldığı, ayrıt sayısı formülünün yanlış verildiği ve yönlü yol tanımında kural ihlali yapıldığı tespit edilmiştir.
Kesinlikle doğru olan tek yargının matematiksel olarak kanıtlanması.

Key Concept

Şebeke Topolojisi: Yayılan Ağaç, Temel Çevrim ve Ağ Modelleri
Estimated Time:1m 30s
Rate this question

Topics

Şebeke Modellerinde Temel Kavramlar

More questions from this topic