Matematik Atölyesi: Graf #1

Bulmaca ve matematiğin ilişkisi sanıldığından daha derindir. Matematik tarihi incelendiğinde önemsiz olduğu düşünülen bazı bulmacaların matematiği değiştirdiği, hatta yeni alanlara yol açtığı görülür. Şüphesiz bunlardan en ünlüsü Königsberg’in yedi köprüsüdür (1736).

18. yüzyılın en önemli matematikçilerinden biri olan Leonhard Euler’in “… bu sorunun matematikle bir ilişkisi olduğunu düşünmüyorum.” dediği Königsberg bulmacası çözüldükten yaklaşık 150 yıl sonra iki önemli matematik dalının ortaya çıkmasına yardımcı olmuştu: Topoloji ve çizge teorisi (nam-ı diğer graf teorisi).

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

Herhangi bir çizge teorisi kitabını açıp ve ilk bölümün ilk sayfasına baktığınızda karşınıza Euler’in çözdüğü Königsberg problemi çıkar. Soru şudur:

Königsberg şehrinin ortasında geçen nehrin üzerinde yedi adet köprü vardır. Bu köprülerin her biri bir ama sadece bir defa kullanılarak şehrin tamamı gezilebilir mi?

Bu soruyla ilk defa karşılaştığımda sorunun basitliği sebebiyle cevaba kendi kendime ulaşacağımı düşünmüştüm. Fakat saatler süren uğraşlarım boşa gitmiş, sonuca bir türlü ulaşamamıştım.

My handwriting. Check the date.

Yeah… You can’t solve it that way Serkan…

Aslında çözümün olmadığını anlamıştım. Örneğin köprülerden birini kaldırınca soru çözülüyordu. Ama bunun nedenini açıklayacak bilgim yoktu. Zaten kısa bir süre sonra bu sorunun neden çizge teorisi anlatılırken gösterilen ilk şey olduğunu anlamıştım. Sorunun çözümü yepyeni bir matematik branşının temelini oluşturuyordu.

Euler’in Yaptığı

Euler soruyu ele alırken köprü ve kara parçalarını iki ayrı gruba ayırmıştı. Euler’in zihninde köprüler 1’den 7’ye numaralandırılmış çizgiler, kara parçaları ise A-B-C-D harfleriyle isimlendirilmiş noktalardı. Bunları çizdiğimizde karşıya çıkan şekle graf denilir.

Euler çözümünü açıklamak için en baştan başlamış ve önce tanımlar yapmıştı. Ona göre Königsberg sorusunda yer alan köprülerin ve kara parçalarının fiziksel özellikleri sorunun çözümü için önem teşkil etmiyordu. Böylece soru grafa indirgendiğinde karşısında sadece gerekli bilgiler yer alıyordu. Königsberg sorusunda hangi kara parçaları arasında kaç tane köprü olduğu dışında önemli hiçbir bilgi yoktu.

Tanım: Bir noktaya bağlı olan çizgi sayısı, o noktanın derecesidir.

Euler’e göre bir grafta istenilen türde tur atılabilmesi için iki şart gerekir:

1. Tüm grafta tam olarak iki tane noktanın derecesi tek ise. Bu iki noktadan biri turun başladığı yer, diğeri ise bittiği yer olur.
2. Grafta bulunan tüm noktaların dereceleri çift ise. Böylece grafta turun atılabilmesi için istenilen noktadan başlanılabilir.

Neden?

Bir nokta başlangıç ya da bitiş noktası değilse, o noktaya gelen çizgi varsa noktadan çıkan çizgi de olmalıdır ki nokta son veya ilk duran olmasın. (Eğer bir çizgi gelen noktadan başka bir çizgi çıkmıyorsa, o nokta turun sonlandığı yerdir. Eğer bir çizgi çıkan bir noktaya tekrar bir çizgi gelmiyorsa, o halde o nokta turun başladığı yerdir.) Bu yüzden de noktanın derecesi çifttir. Fakat tek dereceli bir noktadan bahsediyorsak, o noktaya gelen çizgi varsa derecenin tek kalması için noktadan çıkan başka bir çizginin olmaması gerekir. Bu da tek dereceli noktaların ya başlangıç ya da bitiş olduğunu gösterir.

Bir grafta tek dereceli nokta yoksa, o grafta başlangıç ve bitiş noktası aynı nokta olabilir.

Euler Yolu: Bir graftaki tüm noktalar, grafta bulunan kenarlar bir ama sadece bir defa kullanılarak gezilebiliyorsa, bu grafta atılan tura Euler Yolu denir.

Basit Örnekler

1. Tek Köprü: İki kara parçası arasında tek köprü olursa, graf aşağıdaki gibi olur.
   
2. İki Köprü: İki kara parçası arasında iki köprü olursa.
   
3. Üç Kara Parçası: Eğer bir önceki duruma C kara parçası ve B-C arasına bir tane köprü eklenirse, graf aşağıdaki gibi olur.
   
   Bu durumda iki tane tek sayıda derecesi olan (B ve C) nokta vardır. Yani çözüm mümkündür ama başlangıç ve bitiş noktaları B-C noktaları olmalıdır. Kendiniz deneyerek görebilirsiniz.

Königsberg Çözümü

Euler’e göre Königsberg problemi aşağıdaki gibi graf haline getirilip çözülür.

Noktaların dereceleri sırayla 5, 3, 3, 3’tür. Yani Königsberg probleminde ikiden fazla tek sayıda dereceye sahip olan nokta vardır. Bu yüzden de problemin çözümü yoktur.

Topoloji: En basit haliyle deforme edildiğinde (kıvırmak, uzatmak, çekiştirmek gibi) özellikleri değişmeyen cisimlerin geometrik şekillerini inceleyen matematik dalıdır. (Bir cismin topolojik özelliği o cisim yırtılır ve/veya delinirse bozulur.) Örneğin bir çember ile bir elips topolojide aynı şeydir.

Bi’ Göz Atmakta Fayda Var

Aşağıdaki resimde bulunan objelerden hangileri topolojide aynı şeyi ifade eder?

M. Serkan Kalaycıoğlu