Yöneylem araştırmasında şebeke (ağ) modelleri, sistemlerin grafiksel gösterimi ve optimiza… — KPSS İstatistik

Yöneylem araştırmasında şebeke (ağ) modelleri, sistemlerin grafiksel gösterimi ve optimizasyonu için temel araçlardır. $n$ adet düğüme ( $node$ ) sahip bir şebeke modeli göz önüne alındığında, bu şebekenin tüm düğümlerini birbirine bağlayan ancak içerisinde herhangi bir kapalı yol (çevrim) bulundurmayan alt şebeke yapısı 'yayılan ağaç' ( $spanning \ tree$ ) olarak adlandırılır.

Buna göre, 'yayılan ağaç' kavramı ile ilgili aşağıda verilen ifadelerden hangisi her zaman doğrudur?

Şebekedeki tüm düğümleri kapsamalı ve toplamda $n-1$ adet yay içermelidir.Cevap
B
Şebekedeki tüm düğümleri kapsamalı ve en az bir adet kapalı çevrim barındırmalıdır.
C
Sadece kaynak ( $source$ ) ve hedef ( $sink$ ) düğümler arasındaki en kısa yay dizisinden oluşmalıdır.
D
Şebekedeki toplam yay sayısı, düğüm sayısına ( $n$ ) eşit veya daha fazla olmalıdır.
E
Yayların kapasiteleri, şebekedeki akışın yönüne göre her zaman eşit ve sabit olmalıdır.

Cevap

Şebekedeki tüm düğümleri kapsamalı ve toplamda

n-1

adet yay içermelidir.

Yayılan ağaç, graf teorisinde

n

adet düğümü olan bir grafiğin, tüm düğümleri kapsayan ve çevrim içermeyen alt grafıdır. Bu yapının sürekliliği ve çevrimsizliği sağlaması için gerekli olan yay sayısı matematiksel bir zorunluluk olarak tam olarak

n-1

adettir.

Adım Adım Çözüm

Şebeke bileşenlerini tanımlama

n

adet düğüm ve bu düğümleri bağlayan yaylar belirlenir.

Temel şebeke yapısının anlaşılması için gereklidir.

Ağaç (

tree

) özelliğini uygulama

Yapının çevrim (

cycle

) içermemesi gerektiği kuralı hatırlanır.

Graf teorisinde ağaçların temel karakteristiği çevrimsiz olmalarıdır.

Bağlılık (

connectivity

) şartını sağlama

Tüm

n

düğümün birbirine bağlı olması sağlanır.

Yayılan (

spanning

) özelliği tüm düğümlerin dahil edilmesini gerektirir.

Yay sayısını hesaplama

n

düğümü çevrim oluşturmadan bağlamak için gereken minimum ve maksimum yay sayısı

n-1

olarak bulunur.

Matematiksel olarak

n

düğümlü bağlı ve çevrimsiz bir grafik tam olarak

n-1

ayrıta sahiptir.

Anahtar Kavram

Yayılan ağaç, bir şebekedeki tüm düğümleri en az sayıda yayla birbirine bağlayan ve kapalı çevrim içermeyen yapıdır.

Tahmini Süre:1m 30s

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru