En kısa yol-1

İstihbarat servisinde çalışıyorsunuz ve şekilde görüldüğü gibi kenarı 1km olan bir karenin köşelerine yerleşmiş 4 tane büronuz var. Bu büroları mümkün olan en kısa kablo hattıyla birbirine bağlamak istiyorsunuz. En az ne kadar kablo kullanmanız gerekir?

Bonus Soru: Kenarı 1 km olan düzgün beşgenin köşelerine yerleşmiş 5 büronuz olsaydı cevabınız ne olurdu? 5 şehir için çözümü ve bu çözümün ispatını yapmak çok zor olduğu için sadece bulabildiğiniz en kısa yolu ve bu değerin hangi yolla elde edileceğinin kısa bir açıklamasını isteyelim. Mesela 4km'den (beşgenin herhangi 4 kenarını birleştiren hat) kısa bir hat bulabilir misiniz?

Cevabı ne olacak? Bu arıların yaptığı olayın basitleştirilmiş hali değil mi?

Bu soruyla birbirlerine doğru uçan arı sorusunun bence kenarı 1km olan kare içermekten başka benzerliği yok.



şekilde bu soruda istenen bağlantıya 3 değişik örnek görülüyor.
1. de kolayca görüleceği üzere kablo hattının uzunluğu 3km
2. de yaklaşık olarak 2.88km
3. de ise yaklaşık 2,83km

bizden istenen bu tür bağlantılar içinde en kısa kablo hattı kullanmış lanı bulmamız.
not:yukarıdakilerden daha kısa bir kablo hattıyla da bu bağlantı sağlanabiliyor.

banada biraz saçma geldi doğru mu acaba?

yanlış hesaplamadıysam bulduğunuz değer 2,98... gibi birşeyler ediyor. 2 köşegenin toplamı daha kısa tutuyor.

minimum kapsayan altgraf steiner ağacı
Tüm Etiketler