Re: [MD-sorular] Neden en kısa?

[E. Mehmet Kıral]

Elimizde 4 tane nokta var.

İlk olarak, yolun içinde kavşak olmayan her kısmının doğru parçası
olması gerekiyor. Çünkü iki nokta arasındaki en kısa yol bir doğrudur
ve bu parçanın son iki noktası arasında genel kısalığa katkıda
bulunacak bir şey olmadığından (kavşak mesela) eğer eğri bir bölüm
olsaydı (doğru parçası olmayan anlamında) o eğrinin başından sonuna
bir doğru parçası olarak yolu döşer ve daha kısa bir yol elde ederdik.

Bu haritada hiçbir döngü olamaz, bir döngü olsaydı döngünün bir
kenarını siler ve daha kısa ve aynı özellikleri sağlayan bir harita
elde ederdik. Demek ki kavşaklar ile şehirleri nokta kabul eden ve
yolları kenar kabul eden çizge bir ağaçmış.

Noktaların oluşturduğu karenin dışında herhangi bir yol parçası
olamaz, israf. (karenin dışında kalan nokta sayısı üzerine tümevarımla
kanıtlanabilir, ... sanırım)

Bir şehir iki kavşağa birden bağlanamaz. İki kavşağa bağlandığını
düşünelim. A şehri K1 ve K2 kavşaklarına bağlansın birer yolla. |AK1|
+ |AK2| 'den daha kısa bir yol vardır bu üç şehri bağlayan. K1 A K2
açısı 90 dereceden küçük olduğundan (bir önceki paragraf) 120
dereceden de küçüktür. Dolayısıyla K1 A K2  üçgeninin içerisinde A
noktası olmayan bir Fermat Toricelli noktası vardır. Yani |FA| + |FK1|
+ |FK2| < |AK1| + |AK2|.  AK1 ile AK2 yollarını (yeni bir F kavşağı
ekleyip) FA, FK1 ve FK2 yollarıyla değiştirirsek daha kısa bir yol
elde ederiz. Demek ki bir şehir iki kavşağa bağlanamaz. (En fazla 4
tane kavşak var)

Bir kavşak sadece bir şehre bağlanamaz. A şehrinin ilgili kavşağının K
olduğunu düşünelim ve K'nin bağlandığı tek şehir A olsun. Demek ki K
A'dan başka sadece bir kavşağa (kavşaklara) bağlı. Eğer sadece bir
kavşağa daha, K1, bağlıysa üçgen eşitsizliğinden K kavşağını ve bağlı
olduğu yolları silip yerine AK1 yolunu döşeyebiliriz, ve daha kısa
olur. Eğer iki kavşağa birden bağlıysa K1,K2, bu durumda bu iki
kavşaktan biri sadece bir şehre hizmet eder (bir önceki paragraftan
dolayı) ve bu yaptığımızı onun üzerine uygulayabiliriz. Eğer K üç
kavşağa birden bağlıysa herhangi biri işimizi görür. Bir önceki
paragraftan dolayı da K daha fazla kavşağa bağlı olamaz.
Buradan en fazla iki kavşağımız olması gerektiğini buluruz. (NİHAYET!)

Şimdi bu kavşakların düzleme yerleştirilmesine geldi. İki kavşağımız
varmış gibi hareket edelim. Tek kavşağımız olursa o iki kavşak
çakışır.

Ortak kavşağı olan şehirler köşegenlerdeki köşeler olsun. O zaman iki
kavşağın da çakışması gerektiğini gösterebiliriz (yoksa karenin içinde
kalmak zorunda olduğumuzdan es kaza yeni bir kavşak türeyiverir
(aslında tam olmadı ama göz var izam var, yollar mutlaka kavşak
dışında bir yerde kesişir.)) Türevle ya da başka geometrik yöntemlerle
bu durumda çakışık kavşaklar için en uygun konumun karenin merkezi
olduğu ortaya çıkar.
Bu durumdan daha kısa bir yol bulundu, ve bir sonraki MD sayısında
verildi. Dolayısıyla ortak kavşağı olan şehirler karenin aynı kenarı
üzerindeler.

A ve B şehirleri K1 ortak kavşağını ve C ile D şehirleri de K2 ortak
kavşağını paylaşsın.
Bundan sonra AB ve CD doğrultularını yatay BD doğrultusunu ise dikey
olarak adlandıracağım.
Şu anda durum A,B ve C,D nokta çifleri için simetrik olduğundan K1 ile
K2 kavşaklarının AB ve CD doğrularından (sırasıyla) aynı uzaklıkta
olduğunu varsayabiliriz. |K1K2| uzunluğunun (bu hareket sahasında) en
kısa hali düşey olduğu durumdur. Ayrıca |AK1| + |BK1| uzunluğu da en
kısa AK1B üçgeni eşkenar olduğunda olur. Demek ki en kısa yol planı
soruda verilene oldukça benziyor. Sadece |K1K2| uzunluğunun ne olduğu
kaldı. Onun da türevle cevapta verilen değer olduğunu bulabiliriz.


Uzun oldu ama Allah için güzel oldu.
Eleştirilerinizi, yanlışlarımı bekliyorum. (çok arzu ederseniz övgülerinizi de)


2006/2/12, ali nesin <anesin at bilgi.edu.tr>:
>
> Cok guzel bir soru. Yaniti bilmiyorum. MD'de yayinlanan en kisa yol
> degildi, sadece ilk tahminden daha kisa bir yoldu.
>
> Bu tur sorularin matematiksel anlamda kolay oldugunu hic sanmiyorum
> dogrusu.
>
> Ali
>
> -----Original Message-----
> From: md-sorular-bounces at matematikdunyasi.org
> [mailto:md-sorular-bounces at matematikdunyasi.org] On Behalf Of Emre UNAY
> Sent: 12 Şubat 2006 Pazar 19:31
> To: md-sorular at matematikdunyasi.org
> Subject: [MD-sorular] Neden en kısa?
>
> Herkese iyi günler. Bir soru benim kafamı kurcalıyor. Aynı düzlemde, bir
>
> karenin dört köşesini birleştiren en kısa yol nedir? Yani öyle çizeceğiz
> ki,
> 4 nokta birbirine bağlanmış olacak ve bu çizdiğimiz yol en kısa olacak.
> Bu
> soru eskiden md'de sorulmuştu, bir sonraki sayıda da doğru cevap
> verilmişti,
> ama neden olduğu söylenmemişti. ( Herhangi bir anlatım bozukluğu
> olmasın:
> AB=BC=CD=DA olan, aynı düzlemde, dört şehir olsun. Bu şehirleri
> birleştiren
> en kısa yolu soruyorum. ) Vallahi gözümü korkutuyor bu kadar
> matematikçinin
> içinde, az matematik bilgim ile derdimi anlatmaya çalışmak.
>
> _________________________________________________________________
> Sadece sohbet ile yetinmeyin - eglneceye de doymak için Messenger'i
> tercih
> edin! http://messenger.msn.com/?mkt=tr&DI=3490&XAPID=2584
>
>
>
>
> _______________________________________________
> MD-sorular mailing list
> MD-sorular at matematikdunyasi.org
> http://matematikdunyasi.org/mailman/listinfo/md-sorular
>


--
sorunsuz gençlik