Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
9 beğenilme 0 beğenilmeme
2.5k kez görüntülendi
1) Resimdeki Turkiye idari haritasini boyamak icin 8 renk kullanilmis (Edirne yesil, Kirklareli sari, Tekirdag mor, Canakkale turuncu, Bilecik gri, Kutahya kirmizi, Mugla kahverengi, Denizli degisik yesil). Bu haritayi 7 renk kullanarak boyayabilir misiniz? 6 Renk? 5 Renk? 4 Renk? 3 Renk? 2 Renk? Tek kuralimiz var: Komsu sehirler ayni renk olamazlar (Komsu sehir olmak icin gereken sart aralarinda sinir olmasi. Tek noktada komsu olmak, komsuluk sayilmiyor.) 

Not: Tekirdag, Kirklareli ve Edirne'ye bakarak 2 renk ile boyamanin mumkun olmayacagini soyleyebiliriz.

2) Resimdeki Sirnak haritasini boyamak icin 4 renk kullanilmis. 3 renk kullanilabilir miydi? Buradaki amac yukarida belirledigimiz kurali biraz daha acik hale getirmek: Eger bir noktada uc ya da daha fazla bolge bir araya geliyorsa, o noktaya kose noktasi diyecegiz. Eger iki bolgenin kesisim noktasi bir kose noktasi ise o bolgeler komsu olmuyorlar. Sirnak'ta Cizre, Idil, Guclukonak ve Sirnak il Merkezi'nin bir ortak noktasi var. Bu bir kose noktasi oluyor. Dolayisiyla Idil ve Sirnak il Merkezi'ni komsu kabul etmiyoruz, dolayisiyla ayni renge boyanabilirler. Ayni sekilde Guclukonak ve Cizre de ayni renge boyanabilir.

3) Bu resimdeki haritayi en az kac renk ile boyayabilirsiniz? Bu resimdeki haritayi?

4) Bu resimdeki haritayi? Ya bu resimdeki haritayi en az kac renk ile boyayabilirsiniz? 

5) Bu resmi en az kac renk kullanarak boyayabilirsiniz?

4 Renk Teoremi, hangi haritayi alirsaniz alin yukarida verilen tek kurala uymak sartiyla sadece 4 ya da daha az renge ihtiyaciniz oldugunu soyluyor. Bu teorem bilgisayar yardimiyla kanitlanan teoremlerden. Dolayisiyla, matematikciler arasinda pek sevilmedigi saniliyor. Henuz bilgisayardan yardim almadan verilen bir kanit yok. Bu teorem 4 rengin her haritayi boyamaya yetecegini soyluyor. Eger 4 renk yetiyorsa, 5 renk hayli hayli yeter. Bunu kanitlamak 4 rengi kanitlamaktan daha kolay olmali (mi?) ve P.J. Heawood bunu 1890'da kanitlamis: "5 renk yeterli" demis. 

Asil Soru: Bir lise ogrencisinin anlayabilecegi seviyede kalarak, bir ust sinir oldugu kanitlanabilir mi? Yine bir lise ogrencisinin anlayacagi hesaplar yapilarak guzel bir ust sinir bulunabilir mi? Atiyorum, "hangi haritayi alirsak alalim en fazla 1000 renk kullanarak o haritayi boyayabiliriz." gibi bir teorem bir lise ogrencisine anlatilabilir mi?
Akademik Matematik kategorisinde (2.5k puan) tarafından  | 2.5k kez görüntülendi

bu soruyu 91-1 matematik dünyasında okumuştum çok garip ve ilgi çekici, üst sınır olarak haritadaki ülke sayısı verilebilir çünki komşuluklar değişir mesela A şehrinin 5 komşusu varsa  C şehrinin 3 komşusu varsa yani ülkedeki şehir komşulukları farklıysa maximum renk = şehir sayısı diyebiliriz sanırım

@fotonyiyenadam "Hangi haritayi alirsak alalim..." ise yarayacak bir ust sinir istiyorum.

$n$ renk teoremine bakabilirsin, foton. "$n$ color theorem". Fakat bakmadan once biraz elle islem yapmak da mantilkli.

Aslinda oradaki $n$ sabit bir sayi fakat kafalari direk o sayiya cekmeyeyim dedim. 

O sabit sayi 4 degil mi Sercan? Ben zaten yazdim onu soruda?

Pardon ya, haritalara tikladiktan sonra alt kismi okumayi unutmusum :) 

Araya ek soru fırlatayım: Sonlu her haritanın 4 renkle boyanabildiğini varsayalım. Bu durumda sonsuz her haritanın da 4 renkle boyanabileceğini gösterin.

 Sonlu her haritanın 4 renkle boyanabildiğini varsayalım. Bu durumda sonsuz her haritanın da 4 renkle boyanabileceğini gösterin.

1 cevap

2 beğenilme 0 beğenilmeme

Ust sinir bulmak cok zor degilmis. Elimizde herhangi bir harita olsun. Ne kadar basit ya da ne kadar komplike oldugu onemli degil. Istedigimiz bir haritayi alalim.

Teorem: Hangi haritayi almis olursak olalim, bu haritayi sadece (ya da en fazla) alti renk kullanarak boyayabiliriz. Yedinci bir renge ihtiyacimiz yok.

Kanit: Baslamadan once: Eger elimizde sadece bir tane bolge olmus olsaydi, o zaman sadece bir renge ihtiyacimiz olacakti. Diger bes rengi kullanmayacaktik bile.

Oncelikle islemleri biraz daha kolaylastirmak icin sunu yapalim: Haritadaki her bolge icin o bolgenin ortasina bir nokta yerlestirelim. Eger iki bolge birbirine komsuysa, bu bolgelerin icine yerlestirdigimiz noktalarin arasina bir cizgi cizelim. Yalniz su kosula dikkat edelim: Iki nokta arasina cizdigim cizgi sadece bu iki bolge icinden gecsin, araya parazit bolge girmesin. Simdi elimizde bazi noktalar ve cizgiler var. Bundan sonra nokta yerine kose, cizgi yerine de kenar diyelim. Ozet gecelim: Iki kose arasinda bir kenar var demek tam olarak bu koselerin icinde bulundugu bolgeler arasinda bir sinir var demek. Bir baska deyisle, iki kose birbirine komsu demek bu koselerin icinde bulundugu bolgeler birbirine komsu demek. Daha once duyduysaniz, dual graftan bahsediyorum sadece.

Haritayi boyamak, yani bolgeleri boyamak demek ise her koseye bir renk vermek demek. Komsu bolgelerin ayni renge sahip olamamasi kosulu da arasinda kenar olan koselerin ayni renge sahip olamamasi kosuluna donustu.

Bundan sonra haritayi unutup sadece bu iskelete odaklanalim. Elimizde noktalar, kenarlar ve yuzler var. Yuz dedigimiz sey koseler ve kenarlar tarafindan sinirlandirilmis kapali alan. Bir de en disarida kalan, haritanin disi dedigimiz bir tane daha yuz var.

Simdi sunu gozlemleyelim: Hicbir kenar birbirini kesmiyor, birbirinin uzerinden gecmiyor. Cunku yukarida belirttigimiz gibi iki nokta arasinda cizdigimiz cizgi sadece bu iki noktanin icinde bulundugu bolgelerden geciyor. Yani teknik deyisle elimizde bir duzlemsel cizge (planar graph) var. Yani (disaridaki kocaman bolgeyi de bir bolge sayarsak) elimizde 

koseler - kenarlar + yuzler = 2

esitligi var. Bu formul, Euler formulu olarak da biliniyor. Eger bir cizgeyi duzleme kenarlar birbirini kesmeyecek sekilde cizebiliyorsak, koseler - kenarlar + bolgeler = 2 esitligi saglanmak zorunda.

Bundan sonra bir gozlem daha yapmamiz gerekiyor: Her yuz en az uc tane kenara sahip olmak zorunda. Eger tek bir kose olsaydi bir yuz elde edemezdik, bir kenar bile elde edemezdik. Her iki tane kose olsaydi, bir kenar elde edebilirdik ama bir yuz elde edemezdik.

Bu son gozlemi ve Euler formulunu kullanarak sunu gosterebiliriz:

Derecesi 6'dan kucuk olan en az bir kose vardir. (Yani, hangi haritayi almis olursak olalim, oyle bir bolge vardir ki 5 ya da 5'ten az sayida komsusu vardir.). Ya da baska deyisle butun koselerin derecesi 6 ya da 6'dan buyuk olamaz.

Bu son yazdigimizi kanitlamadik, ama dogru oldugunu varsayalim. Yani derecesi 6'dan kucuk bir kose oldugunu varsayalim. K kosesi boyle bir kose olsun. Simdi K kosesini ve K kosesine ait butun kenarlari silelim. Elimizde kalan yeni cizgede orijinal cizgeden bir eksik kose var. Tumevarim kullanarak, bu bir eksiltilmis cizgenin alti renge boyandigini varsayarsak, K kosesinin en fazla 5 tane kosesi oldugu icin, K kosesi bu butun komsulardan farkli bir renge boyanabilir. Bu da kaniti tumevarim yardimiyla bitirdigimiz anlamina gelir.

Yukaridaki Euler formulu ve derecesi 6'dan kucuk olan bir kose oldugu gercegi bir lise ogrencisine birkac saatte anlatilabilir. Demek ki bir lise ogrencisine 6 Renk Teoremi kanitlanabilir. Hatta birkac hafta icinde birkac kere bulusup, kucuk odevler vererek ogrencinin kaniti kendi kendine tamamlamasi saglanabilir. 

6 Renk Teoremi bu kadar kolaymis, 5 Renk Teoremi de zor degil. Ama yazmak istemedim, cizerek anlatilabilir. Ama 4 Renk Teoremi zor. Hala bilgisayar destegi olmadan kanitlanamiyor. 

(2.5k puan) tarafından 
20,200 soru
21,726 cevap
73,275 yorum
1,887,809 kullanıcı