Königsberg'in Yedi Köprüsü

Kısaca: Königsberg'in yedi köprüsü; çizge kuramının (graf teorisi) temelini oluşturan ve XVIII. ...devamı ☟

Königsberg'in yedi köprüsü
Königsberg'in Yedi Köprüsü

right|thumb|355px|18. yüzyılda KönigsbergKönigsberg`in yedi köprüsü; çizge kuramının (graf teorisi) temelini oluşturan ve XVIII. yüzyılda, Königsberg köprülerinden esinlenerek ortaya atılan ünlü bir matematik problemidir.


Problemin kökeni

Königsberg kentinde Eski ve Yeni Pregel nehirleri birleşerek Pregel (Pregolya)nehrini oluşturmaktadır. Bu nehirler şehri 4 bölüme ayırmaktadır ve nehir üzerinde bu bölgeleri birleştiren yedi köprü bulunmaktadır. Merak edilen ise şudur: ``Bütün köprülerden bir ve yalnız bir kez geçmek koşulu ile bir yürüyüş yapılabilir mi?``

Bu soru 1736`da İsviçreli matematikçi Leonhard Euler tarafından cevaplandırılmıştır.

Euler`in çözümü

Aşağıdaki şekilde kara parçaları harflerle, köprüler ise sayılarla işaretlenmiştir. Önce çözümü biraz daha kolaylaştırmak ve şekli gereksiz bileşenlerden arındırmak amacıyla kara parçalarının noktalar, köprülerin ise bu noktaları birleştiren çizgiler olarak gösterildiği ikinci bir şekil yani ``çizge`` (``graf``) çizilir. Çizgiler ``çizge elemanı``, noktalar ``düğüm``, düğüme bağlı olan elemanların sayısı ise ``düğüm derecesi`` olarak adladırılmak üzere soru, çizgenin herhangi bir düğümünden başlayarak yedi elemanının her birini bir ve yalnız bir kez kullanarak dolaşma problemine dönüşmüş olur.

a†’


1736`da Euler`in incelemeleri böyle bir gezintinin mümkün olmadığını kanıtlamış ve bu tür dolaşmayı mümkün kılacak çizgelerin şu özelliklere sahip olmaları gerektiğini göstermiştir: Birleşik bir çizgenin bütün elemanlarını bir ve yalnız bir kez kullanarak dolaşmak için o çizgenin tek dereceli düğümlerinin sayısı, eğer varsa, iki olmalıdır. Tek dereceli düğümler dolaşmanın başlangıç ve bitiş düğümleridir. Çizgede böyle düğümler yoksa dolaşmaya herhangi bir düğümden başlanabilir.

Çözümün temelinde yatan düşünce şudur: Bir düğüm, başlangıç ya da bitiş düğümü değilse o düğüme gelen kişinin turu tamamlayabilmek için oradan ayrılması gerekecektir. Dolayısıyla bu tip düğümler çift dereceleri olmalıdır. Oysa tek dereceli bir düğüme, örneğin ``D`` düğümüne ikinci kez gelen bir kişi çıkış yolu bulamayacaktır. Dolayısıyla bu düğüm ya gezintinin bitiş düğümü olmalıdır ya da başlangıç düğümü olarak seçilmelidir ki ikinci gelişte çıkış yolu bulunabilsin. Buna göre tek dereceli düğüm sayısı ikiden fazlaysa gezinti tamamlanamayacaktır.

Yürüyüşün sonunda başlangıç noktasına dönülebilmesi içinse bütün düğümler çift dereceli olmalıdır. Böylece, başlangıç ve bitiş düğümü aynı olan ve her bir elemanı sedece ve en az bir kez içeren turlara "Euler turu" ve Euler turu içeren çizgelere de "Euler çizgesi" denmiştir.

Problemin değişik biçimleri

Problemin, klasik ifadesinden faklı olarak her düğümün değişik renk veya isimlerle adlandırıldığı ve yeni köprülerin eklendiği çeşitleri de mevcuttur.

Prensler ve Piskopos



Şehrin kuzey yakasında (A) Mavi Prens`in şatosu, güney yakasında (B) Kırmızı Prens`in şatosu, doğuda (D) Piskopos`un kilisesi ve ortadaki adada (C) bir han bulunmaktadır.

Mavi Prens köprülerden istenen şekilde yürünemeyeceğini anlar ve gizlice sekizinci köprüyü yapmayı planlar. Köprüyü öyle bir yere yapmalıdır ki akşamüstü kendi şatosundan yürüyüşe başlamalı ve gezintisini handa tamamlayarak zaferini kutlamalıdır. Ancak Kırmızı Prens gezintiyi tamamlayamamalıdır. ``Mavi Prens sekizinci köprüyü nereye inşa etmelidir?``

Mavi Prens`in sekizinci köprüyü inşa etmesi Kırmızı Prens`i çok kızdırır. Handa tamamlayabileceği bir yürüyüşü olanaklı ve Mavi Prens`in yürüyüşünü imkansız hale getirecek dokuzuncu köprüyü inşa etmek ister. ``Kırmızı Prens dokuzuncu köprüyü nereye inşa etmelidir?``

Piskopos ise bu köprü kurma yarışını endişeyle izlemektedir. Bu durum hem şehrin görüntüsünü bozmaktadır hem de han da sonlanan yürüyüşler sarhoşluğu artırmaktadır. Tüm gezintilerin başladığı yerde bitmesi için onuncu bir köprü yaptırmalıdır. ``Onuncu köprü nereye inşa edilmelidir?``

Çözüm



Öncelikle şekil düğümleri renkli (han a†’ turuncu, kilise a†’ beyaz) olan bir çizgeye indirgenir.

İlk soruda amaç orijinal çözümde de belirtildiği gibi tek dereceli düğümlerin sayının iki olmasını sağlamaktır. Tek dereceli düğümlerden biri başlangıç diğeri ise bitiş düğümü olacağına göre Mavi Prens`in sekizinci köprüyü kırmızı şato ile kilisenin arasına yapması gerekir. Böylece mavi ve turuncu düğümler tek dereceli kalarak başlangıç ve bitiş düğümleri olurlar.

Dokuzuncu köprünün inşasında da aynı yöntem izlenir. Bu kez yalnızca kırmızı ve turuncu düğümler tek dereceli kalmalıdır. Turuncu düğüm zaten tek derecelidir. Mavi düğümün çift dereceli, kırmızı düğümün ise tek dereceli olmasını sağlamak için dokuzuncu köprü mavi şato ile kırmızı şato arasına yapılmalıdır.
center;">Renkli çizge center;">Sekizinci köprü center;">Dokuzuncu köprü center;">Onuncu köprü
Piskopos`un isteğinde ise farklı bir durum söz konusudur. Yeni çizgede başlangıç ve bitiş noktası aynı olmalıdır. Buna göre çizgedeki bütün düğümler çift dereceli yapılmalıdır. Dolayısıyla onuncu köprü kırmızı şato ile han arasına inşa edilmelidir.

Matematik tarihindeki önemi

Leonhard Euler`in bu araştırmaları matematikte tamamıyla yeni bir dal olan çizge kuramının ilk teoremi ve topolojinin keşfinin habercisi olmuştur. Çözümün ardından Euler, "Solutio problematis ad geometriam situs pertinentis" isimli makaleyi yayımlamıştır.

Çözümün kullanım alanları

Ayrıt rotalama problemleri, pek çok araştırmacının üzerinde çalıştığı bir rota en iyilemesi problemidir. Bu problemin, gerçek hayatta mektup dağıtımı, yol bakımı, kar temizleme, çöp toplama, devriye araçları ve yol tuzlama konularında pek çok uygulaması vardır. Gerek hükümetler gerekse de işletmeler her yıl bu işlemler için önemli harcamalar yapmaktadırlar. Fakat planlamanın etkin olarak yapılamaması durumunda önemli miktarlarda kaynak israfı söz konusudur.

Kaynaklar

  • Tokad,Y. (1996). ``Devre Analizi Dersleri``, Çağlayan Kitabevi, İstanbul
  • Math Forum
  • Avriel, M. ve Golany, B. (1996). ``Mathematical Programming For Industrial Engineers``, Marcel Dekker Inc., New York.
  • http://www.anadolu.edu.tr/arastirma/hakemli_dergiler/sosyal_bilimler/pdf/2003-1/sos_bil.6.pdf


Kaynaklar

Vikipedi

Bu konuda henüz görüş yok.
Görüş/mesaj gerekli.
Markdown kullanılabilir.

Königsberg'in yedi köprüsü Resimleri

Çizge Teorisi
3 yıl önce

Leonhard Euler tarafından, 1736 yılında, Königsberg'in yedi köprüsü (Almanca: Die Sieben Brücken von Königsberg) adında günümüzde hâlâ popülerliğini koruyan...

Çizge Teorisi, Leonhard Euler, Matematik, Taslak, Königsberg'in yedi köprüsü
Eylau Muharebesi
5 yıl önce

Napolyon'un üstünlük sağlayamadığı ilk muharebedir. Doğu Prusya'da, Königsberg'in (Kaliningard) 37 km güneyindeki Eylau kasabası (bugün Bagrationovsk...

Heiligenbeil Kuşatması
6 yıl önce

Prusya'daki esas Alman savunmasını ele geçirmek ve Doğu Prusya'nın başkenti Königsberg'in alınması amacıyla başladı. Bölgedeki Sovyet taarruzu Alman Merkez Ordular...

Leonhard Euler
3 yıl önce

- C = 1 (“C” grafikteki bileşenlerin sayısıdır). 1736 yılında Königsberg'in yedi köprüsü olarak bilinen bir problemi çözdü ve grafik teorisi ve topolojinin...

Leonhard Euler, 15 Nisan, 1707, 1726, 1727, 1730, 1733, 1734, 1735, 1740, 1741
Friedland Muharebesi
6 yıl önce

Lestocq'un ertesi gün yaklaşık 25 bin kişiyle Königsberg'i terk ederek Tilsit'e çekilmesiyle, Königsberg Fransızların eline geçti. Savaşın ardından Fransa...

Bilim
3 yıl önce

gelen rönesans, önceki çağlardan çok farklı bir düşünce sistemine geçişin köprüsü konumundadır. Bilim ve felsefenin ayrışması modern çağa yaklaşırken iyice...

Bilimin tarih içindeki gelişimi, Bilim tarihi, Bilimsel yöntem, Ahlak, Arapça, Astronomi, Bilim Portalı, Bilimsel kuram, Dilbilgisi, Ekoloji, Fransızca, Mantık, Matematik, Deney
Berlin Muharebesi
3 yıl önce

önemliydi. Königsberg, uzun bir direnmenin ardından 9 Nisan 1945'te Kızıl Ordu birliklerinin kontrolüne geçti. (Königsberg Kuşatması) Königsberg'in düşmesi...

Matematik tarihi
3 yıl önce

etkili matematikçisi muhtemelen Leonhard Euler'di. Katkıları, Königsberg'in Yedi Köprüsü problemi ile graf teorisi çalışmasının kurulmasından, birçok modern...

Matematik tarihi, Arşimet, Bernhard Riemann, Blaise Pascal, Boole, Cantor, Cardano, Carl Friedrich Gauss, Cauchy, Charles Hermite, Daniel Bernoulli