1
Bir dizgenin tanımlanmasında kullanılan (N,S) gösterimindeki N ve S ne ifade etmektedir?
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.
Çizge Modelleri
- 20 soru-cevap
- Karar Modelleri
2
Çizge modellerinde iki düğümü birbirine bağlayan çizgiye ne isim verilmektedir?
Bağlantı: İki düğümü birbirine bağlayan çizgidir.
3
Düğüm dışına akış söz konusu ise düğüm nasıl adlandırılır?
Düğüm dışına akışın söz konusu olduğu (düğüm dışına akışın düğüm içine akıştan fazla olduğu) düğüm, kaynak veya tedarik düğümü olarak isimlendirilir.
4
Düğüm içine akış söz konusu ise bu düğüm nasıl adlandırılır?
İçine akış olan düğüm, talep düğümü olarak adlandırılır.
5
Aktarma düğüm nedir? Tanımlayınız.
Düğüm dışına akışın söz konusu olduğu (düğüm dışına akışın düğüm içine akıştan fazla olduğu) düğüm, kaynak veya tedarik düğümü olarak isimlendirilir. İçine 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 aktarma düğümü olarak adlandırılır.
6
Tipik bir çizge modelinin elemanları nelerdir?
Tipik bir çizge modelinin elemanları; düğümler, bağlantı ve akış olarak sıralanır.
7
Çizge modellerine ilişkin iki temek uygulamayı açıklayınız.
Çizge modellerinin iki temel uygulaması vardır. İlk uygulama alanı mal akışının söz konusu olduğu; malların, malzemenin bir veya birkaç tedarik düğüm kaynağından ara düğümlere, ara düğümlerden talep düğüm veya düğümlerine teslimine ilişkindir. Diğer uygulama alanı ise çizgedeki tüm düğümlerin belirli bir yaklaşım ile birleştirilmesine yöneliktir.
8
İki düğümü birbirine bağlayan, birbirinden ayrı bir dizi bağlantıdan oluşan yapıya ne ad verilmektedir?
İki düğümü birbirine bağlayan, birbirinden ayrı bir dizi bağlantıdan oluşan yapıya yol (yörünge) adı verilir.
9
Yönlü olmayan bağlantıyı tanımlayınız.
Yönlü olmayan bağlantı: İki bağlı düğümden akışın her iki yönde olduğunu gösteren bağlantı biçimidir.
10
Yönlü bağlantı nedir? Tanımlayınız.
Yönlü bağlantı: İki bağlı düğümden birinden diğerine tek yönlü akış olduğunu gösteren bağlantı biçimidir.
11
Döngü nedir? Tanımlayınız.
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.
12
Döngü içermeyen ve yönlü olmayan bağlantı ile birleştirilmiş düğümlerin oluşturduğu yol ne 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.
13
n adet düğümden oluşan bir çizgede, n düğüm döngü oluşturmayacak biçimdeki bir kapsayan ağaç için kullanılması gereken bağlantı sayısı nedir?
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.
14
8 tane bağlantı kullanılarak düğümler döngü oluşturmayacak biçimde birleştirilen kapsayan ağaçta kaç tane düğüm vardır?
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 oluşturulan ağaca kapsayan ağaç denir.
Bu tanıma göre 8 tane bağlantı (n-1=8) kullanılarak düğümler döngü oluşturmayacak biçimde birleştirilen kapsayan ağaçta 9 tane düğüm (n=9) vardır.
15
En yüksek akış probleminin çözümünde uygulanan işlemler nelerdir?
En yüksek akış probleminin çözümünde aşağıdaki işlemler yerine getirilir.
- Başlangıç düğümünden bitim düğümüne giden malzemenin pozitif (sıfırdan farklı) uygun akışını sağlayacak yol belirlenir. Eğer böyle bir yol belirlenemiyorsa 5. adıma geçilir.
- 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.
- Kalan akış kapasiteleri, akışın yönü dikkate alınarak akışın gönderildiği yönde azaltılarak, akışın ters yönünde ise arttırılarak gözden geçirilir.
- Adım 1’e dönülür.
- Bitim düğümüne gönderilen miktar en yüksek akıştır, en iyi çözüme ulaşılmıştır.
16
En yüksek akış problemi uygulamalarına iki örnek veriniz.
En yüksek akış problemi uygulamalarına;
- Boru hatları boyunca petrol, gaz,su gibi malzeme için en yüksek akışın belirlenmesi,
- Haberleşme sisteminde en yüksek bilgi akışının belirlenmesi,
- Bir hat boyunca en yüksek elektrik akışının belirlemesi,
- Ulaşımda en yüksek araç akışının belirlenmesi,
- Bir üretim merkezine tedarik ağından en yüksek malzeme akışının belirlenmesi örnek olarak verilebilir.
17
En küçük yayılma problemlerinde amaç nedir?
En küçük yayılma problemlerinde çizgedeki tüm düğümleri birbirine bağlayan en kısa yolun bulunması amaçlanmaktadır.
18
En küçük yayılma problemlerinin genel yapısı nasıldır? Maddeler halinde yazınız.
En küçük yayılma problemlerinin genel yapısı aşağıda 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ındaki 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 çizge tasarlanırken toplam uzunluğu en kısa yapacak şekilde bağlantılar seçilmektedir.
19
En küçük yayılma problemlerinin çözümünde uygulanan işlemler nelerdir?
En küçük yayılma problemlerinin çözümünde aşağıdaki işlemler yerine getirilir:
- Çizge içerisinde rastgele bir düğüm seçilir. Bu düğüm kendisine en yakın düğüme
bağlanır. - 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.
- Tüm düğümler bağlanana kadar işleme devam edilir.
20
En küçük yayılma problemi uygulamalarına iki örnek veriniz.
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ünikasyon çizgesinin (fiber optik ağları, kablolu televizyon ağları vb.) belirlenmesi örnek olarak verilebilir.