Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Königsberg'in yedi köprüsü; graf teorisinin temelini oluşturan ve XVIII. yüzyılda Königsberg köprülerinden ilhamlanılarak ortaya atılan ünlü bir matematik problemidir.
Problemin kökeni
Königsberg kentinde Eski Pregel ve Yeni Pregel nehirleri birleşerek () nehrini oluşturmaktadır. Bu nehirler, şehri dört 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 defa 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 graf (çizge) çizilir. Graflar graf elemanı, noktalar düğüm, düğüme bağlı olan elemanların sayısı ise düğüm derecesi olarak adladırılmak üzere soru, grafın herhangi bir düğümünden başlayarak yedi elemanının her birini bir ve yalnız bir kere kullanarak dolaşma problemine dönüşmüş olur.
 | → |  |
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 grafların şu özelliklere sahip olmaları gerektiğini göstermiştir: Birleşik bir grafın bütün elemanlarını bir ve yalnız bir defa kullanarak dolaşmak için o grafın 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. Grafta 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 graflara da "Euler grafları" denmiştir.
Problemin değişik biçimleri
Problemin, klasik ifadesinden farklı 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.İngilizce wikipedia
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ü imkânsı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 → turuncu, kilise → beyaz) olan bir grafa 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.
 Renkli graf |  Sekizinci köprü |  Dokuzuncu köprü |  Onuncu köprü |
Piskopos'un isteğinde ise farklı bir durum söz konusudur. Yeni grafta başlangıç ve bitiş noktası aynı olmalıdır. Buna göre graftaki 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 graf teorisinin 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.
Köprülerin günümüzdeki durumu
Probleme konu olan yedi köprünün ikisi II. Dünya Savaşı sırasındaki bombardımanlarla yok edildi. Daha sonra iki tanesi Ruslar tarafından yıkıldı ve yerine modern bir otoyol inşa edildi. Geriye kalan üç köprü ise hala ayakta durmakta. Bunlardan biri Almanlar tarafından 1935 yılında tekrar inşa edildi. Sadece geri kalan ikisi Euler zamanından bu yana ayakta kalmayı başardı. Sonuç olarak günümüz modern Königsberg'inde beş köprü bulunmakta.
Graf teorisine göre günümüzde ikinci dereceden üç düğüm ve üçüncü dereceden iki düğüm olacak şekilde konumlanmış olan Königsberg'in köprülerinde her köprüden bir ve yalnız bir kez geçmek koşulu ile bir yürüyüş yapmak mümkündür. Fakat bu yürüş bir adada başlayıp diğer bir adada biteceğinden dolayı bir Euler Turu oluşturmamaktadır.
Kaynakça
Dış bağlantılar
- Avriel, M. ve Golany, B. (1996). Mathematical Programming For Industrial Engineers, Marcel Dekker Inc., New York.
- Math Forum 11 Nisan 2008 tarihinde Wayback Machine sitesinde .
- Tokad, Y. (1996). Devre Analizi Dersleri, Çağlayan Kitabevi, İstanbul
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Konigsberg in yedi koprusu graf teorisinin temelini olusturan ve XVIII yuzyilda Konigsberg koprulerinden ilhamlanilarak ortaya atilan unlu bir matematik problemidir 18 yuzyilda Konigsberg ve 7 kopruProblemin kokeniKonigsberg kentinde Eski Pregel ve Yeni Pregel nehirleri birleserek nehrini olusturmaktadir Bu nehirler sehri dort bolume ayirmaktadir ve nehir uzerinde bu bolgeleri birlestiren yedi kopru bulunmaktadir Merak edilen ise sudur Butun koprulerden bir ve yalniz bir defa gecmek kosulu ile bir yuruyus yapilabilir mi Bu soru 1736 da Isvicreli matematikci Leonhard Euler tarafindan cevaplandirilmistir Euler in cozumuAsagidaki sekilde kara parcalari harflerle kopruler ise sayilarla isaretlenmistir Once cozumu biraz daha kolaylastirmak ve sekli gereksiz bilesenlerden arindirmak amaciyla kara parcalarinin noktalar koprulerin ise bu noktalari birlestiren cizgiler olarak gosterildigi ikinci bir sekil yani graf cizge cizilir Graflar graf elemani noktalar dugum dugume bagli olan elemanlarin sayisi ise dugum derecesi olarak adladirilmak uzere soru grafin herhangi bir dugumunden baslayarak yedi elemaninin her birini bir ve yalniz bir kere kullanarak dolasma problemine donusmus olur 1736 da Euler in incelemeleri boyle bir gezintinin mumkun olmadigini kanitlamis ve bu tur dolasmayi mumkun kilacak graflarin su ozelliklere sahip olmalari gerektigini gostermistir Birlesik bir grafin butun elemanlarini bir ve yalniz bir defa kullanarak dolasmak icin o grafin tek dereceli dugumlerinin sayisi eger varsa iki olmalidir Tek dereceli dugumler dolasmanin baslangic ve bitis dugumleridir Grafta boyle dugumler yoksa dolasmaya herhangi bir dugumden baslanabilir Cozumun temelinde yatan dusunce sudur Bir dugum baslangic ya da bitis dugumu degilse o dugume gelen kisinin turu tamamlayabilmek icin oradan ayrilmasi gerekecektir Dolayisiyla bu tip dugumler cift dereceleri olmalidir Oysa tek dereceli bir dugume ornegin D dugumune ikinci kez gelen bir kisi cikis yolu bulamayacaktir Dolayisiyla bu dugum ya gezintinin bitis dugumu olmalidir ya da baslangic dugumu olarak secilmelidir ki ikinci geliste cikis yolu bulunabilsin Buna gore tek dereceli dugum sayisi ikiden fazlaysa gezinti tamamlanamayacaktir Yuruyusun sonunda baslangic noktasina donulebilmesi icinse butun dugumler cift dereceli olmalidir Boylece baslangic ve bitis dugumu ayni olan ve her bir elemani sedece ve en az bir kez iceren turlara Euler turu ve Euler turu iceren graflara da Euler graflari denmistir Problemin degisik bicimleriProblemin klasik ifadesinden farkli olarak her dugumun degisik renk veya isimlerle adlandirildigi ve yeni koprulerin eklendigi cesitleri de mevcuttur Ingilizce wikipedia Prensler ve Piskopos Sehrin kuzey yakasinda A Mavi Prens in satosu guney yakasinda B Kirmizi Prens in satosu doguda D Piskopos un kilisesi ve ortadaki adada C bir han bulunmaktadir Mavi Prens koprulerden istenen sekilde yurunemeyecegini anlar ve gizlice sekizinci kopruyu yapmayi planlar Kopruyu oyle bir yere yapmalidir ki aksamustu kendi satosundan yuruyuse baslamali ve gezintisini handa tamamlayarak zaferini kutlamalidir Ancak Kirmizi Prens gezintiyi tamamlayamamalidir Mavi Prens sekizinci kopruyu nereye insa etmelidir Mavi Prens in sekizinci kopruyu insa etmesi Kirmizi Prens i cok kizdirir Handa tamamlayabilecegi bir yuruyusu olanakli ve Mavi Prens in yuruyusunu imkansiz hale getirecek dokuzuncu kopruyu insa etmek ister Kirmizi Prens dokuzuncu kopruyu nereye insa etmelidir Piskopos ise bu kopru kurma yarisini endiseyle izlemektedir Bu durum hem sehrin goruntusunu bozmaktadir hem de han da sonlanan yuruyusler sarhoslugu artirmaktadir Tum gezintilerin basladigi yerde bitmesi icin onuncu bir kopru yaptirmalidir Onuncu kopru nereye insa edilmelidir Cozum Oncelikle sekil dugumleri renkli han turuncu kilise beyaz olan bir grafa indirgenir Ilk soruda amac orijinal cozumde de belirtildigi gibi tek dereceli dugumlerin sayinin iki olmasini saglamaktir Tek dereceli dugumlerden biri baslangic digeri ise bitis dugumu olacagina gore Mavi Prens in sekizinci kopruyu kirmizi sato ile kilisenin arasina yapmasi gerekir Boylece mavi ve turuncu dugumler tek dereceli kalarak baslangic ve bitis dugumleri olurlar Dokuzuncu koprunun insasinda da ayni yontem izlenir Bu kez yalnizca kirmizi ve turuncu dugumler tek dereceli kalmalidir Turuncu dugum zaten tek derecelidir Mavi dugumun cift dereceli kirmizi dugumun ise tek dereceli olmasini saglamak icin dokuzuncu kopru mavi sato ile kirmizi sato arasina yapilmalidir Renkli graf Sekizinci kopru Dokuzuncu kopru Onuncu kopru Piskopos un isteginde ise farkli bir durum soz konusudur Yeni grafta baslangic ve bitis noktasi ayni olmalidir Buna gore graftaki butun dugumler cift dereceli yapilmalidir Dolayisiyla onuncu kopru kirmizi sato ile han arasina insa edilmelidir Matematik tarihindeki onemiLeonhard Euler in bu arastirmalari matematikte tamamiyla yeni bir dal olan graf teorisinin ilk teoremi ve topolojinin kesfinin habercisi olmustur Cozumun ardindan Euler Solutio problematis ad geometriam situs pertinentis isimli makaleyi yayimlamistir Cozumun kullanim alanlariAyrit rotalama problemleri pek cok arastirmacinin uzerinde calistigi bir rota en iyilemesi problemidir Bu problemin gercek hayatta mektup dagitimi yol bakimi kar temizleme cop toplama devriye araclari ve yol tuzlama konularinda pek cok uygulamasi vardir Gerek hukumetler gerekse de isletmeler her yil bu islemler icin onemli harcamalar yapmaktadirlar Fakat planlamanin etkin olarak yapilamamasi durumunda onemli miktarlarda kaynak israfi soz konusudur Koprulerin gunumuzdeki durumuProbleme konu olan yedi koprunun ikisi II Dunya Savasi sirasindaki bombardimanlarla yok edildi Daha sonra iki tanesi Ruslar tarafindan yikildi ve yerine modern bir otoyol insa edildi Geriye kalan uc kopru ise hala ayakta durmakta Bunlardan biri Almanlar tarafindan 1935 yilinda tekrar insa edildi Sadece geri kalan ikisi Euler zamanindan bu yana ayakta kalmayi basardi Sonuc olarak gunumuz modern Konigsberg inde bes kopru bulunmakta Graf teorisine gore gunumuzde ikinci dereceden uc dugum ve ucuncu dereceden iki dugum olacak sekilde konumlanmis olan Konigsberg in koprulerinde her kopruden bir ve yalniz bir kez gecmek kosulu ile bir yuruyus yapmak mumkundur Fakat bu yurus bir adada baslayip diger bir adada biteceginden dolayi bir Euler Turu olusturmamaktadir Kaynakca 19 Mart 2012 tarihinde kaynagindan arsivlendi Erisim tarihi 30 Mayis 2008 The 7 5 Bridges of Koenigsberg Kaliningrad 1 Aralik 2008 tarihinde kaynagindan Erisim tarihi 30 Mayis 2008 Dis baglantilarAvriel M ve Golany B 1996 Mathematical Programming For Industrial Engineers Marcel Dekker Inc New York Math Forum 11 Nisan 2008 tarihinde Wayback Machine sitesinde Tokad Y 1996 Devre Analizi Dersleri Caglayan Kitabevi Istanbul