3 Kulübe Problemi ve Çizge Kuramı: 6 Noktayı Birbirine Eşleştirmek Ne Kadar Zor Olabilir?

Bir belediye başkanı olduğunuzu hayal edin. 3 kulübeye elektrik, su ve doğal gaz bağlatmak için, bünyenizde çalışan mühendise inşa edeceği boruların, kağıda bir planını çizmesini istediniz. Kural çok basit: Elektrik, elektrik merkezinden gelecek. Su, su merkezinden gelecek. Doğal gaz, doğal gaz merkezinden gelecek. Ve bu hatların hiçbiri, birbiriyle kesişemez. Tıpkı ana görseldeki gibi...

Aradan günler geçer ve mühendis odanıza gelip çizimi bir türlü yapamadığını söyler. Görselden fark edebileceğiniz gibi, mavi hizmet (diyelim ki su), 2. kulübeye bağlanamamıştır. Böylesine basit bir çizimi bile yapamadığı için mühendisin bir beceriksiz olduğunu düşünüp onu kovdunuz, daha sonra bir de siz uğraşmaya karar verdiniz.

Burada yazıyı okumayı durdurup bu projeyi kağıtta denemenizi istiyoruz. Eğer çizebildiyseniz yazıyı okumanıza gerek yok; derhal bir makale yazmanız gerekiyor! Ama muhtemelen başaramayacaksınız, çünkü çizge kuramı bu planı, bir kağıtta asla çizemeyeceğinizi söylüyor. İyi ama... Çizge kuramı da ne?

Çizge Kuramı Nedir?

Çizge kuramı, 18. yüzyılın ilk yarısında Leonhard Euler tarafından Königsberg köprüleri problemini çözmek için geliştirilen bir kuramdır. Königsberg köprüleri probleminden biraz bahsedelim.

Königsberg, Prusya (büyük oranda şimdiki Almanya) kentlerinden biridir. Günümüzde, Rusya topraklarında olan Kaliningrad şehrinin eski adıdır. O yıllarda şehir kuş bakışı olarak aşağıdaki resim gibi görünüyordu. Günümüzde bu köprülerin ikisi, 2. Dünya Savaşı sırasında yıkılmıştır.

medium

Bu şehirdeki köprülerle ilgili matematikçiler arasında o zamanlarda şöyle bir problem dönüyordu;

Her bir köprüden bir kere geçmek koşuluyla şehirde tam bir tur atmak mümkün mü?

Leonhard Euler, bu soruyu çok şık bir yöntemle çözmeyi başardı ve ömrü boyunca birçok kez yaptığı gibi matematiğin tarihini değiştirdi. Euler, ortaya yeni bir kuram attı ki, bu kuram sonradan topoloji isimli bilimin doğuşuna sebep olmuştur. Euler, köprülerin uç noktalarını birer nokta; köprüleri ise birer çizgi olarak düşünmüştür.

ResearchGate

Yukarıdaki şekilde, sağdaki görsel gibi düşününce, problem daha basite indirgendi. Çözüm, artık Euler'in apaçık karşısındaydı: Şehri dolaşmak isteyen kişi, üzerine gittiği her noktadan ayrılmak zorundaydı. Bu da her noktanın çift sayıda çizgiye sahip olması gerektiği gerçeğini önümüze sermekteydi. Euler, her bir noktanın çift sayıda çizgiye sahip olmadığı için, Königsberg şehrini her köprüden bir kez geçerek dolaşma fikrinin imkansız olduğunu kanıtlamıştır.

Bu çözüm yöntemi daha sonrasında çeşitli problemlerin çözümünde kullanılmıştır. Bu yöntem, günümüzde çizge kuramı adını almıştır ve artık çok sayıda akademik makaleye sahip, başlı başına bir matematik alanıdır.

Biraz bu kuramdan bahsetmek gerekirse: Bu kuramda çizge üzerinde işlem yapılır. Çizge denilen matematiksel yapı, bir kenar $E$ ve bir köşe $V$ kümesinden yapıdan oluşur. Gösterimi ise $G=(V,E)$ ile yapılır. Bu yapı, bilgisayar bilimlerinde veri saklama sahasında da sıkça karşımıza çıkmaktadır.

Bundan yüzyıllar önce bir şehri öyle istediğimiz gibi gezemeyeceğimizi söyleyip hayallerimizi suya düşüren bu kuram, günümüzden yaklaşık 100 yıl önce başka bir hayalimizi daha suya düşürdü. Ama bu konuyu incelemeden önce, kuram hakkında biraz daha bilgi edinelim.

Euler bu kuramı sadece geliştirmekle kalmayıp ayrıca birçok katkıda bulunmuştur, bunlardan belki de en önemlisi Euler karakteristiğidir.

Euler Karakteristiği

Çizgeleri, aslında lisede uğraştığımız geometrik şekillerin genelleştirilmiş formu olarak düşünebiliriz. Herhangi bir çizgenin Euler karakteristiği, bağlantılı çizgeler için (her köşe bir kenarla başka bir köşeye bağlı) çizgeler için $\chi =V-E+F$ formülü ile hesaplanır. Burada $V$ köşe sayısı, $E$ kenar sayısı, $F$ de yüz sayısıdır.

Örneğin bir karenin 4 köşesi, 4 kenarı ve 2 yüzü vardır (yukarı ve aşağı). Dolayısıyla Euler karakteristiği 2'dir.

Aslında kare için sonucun 2 olması bir tesadüf değildir. Kanıtını kaynaklarımızdan görebileceğiniz kanıtsava göre bir düzlemde yer alan bütün çizgelerin Euler karakteristiği 2'dir. Bu kanıtsavın çok ilginç uygulamaları vardır. Örnek olarak aşağıdaki şekildeki gibi bir futbol topunun kaç beşgene sahip olduğunu hesaplayalım.

vectorstock

Dikkat edilirse topu bir yerinden kesip açarsak düzlem üzerinde bir bölge oluştururuz, yani Euler karakteristiği 2 olmak zorundadır. Bir beşgene karşılık, 5 tane altıgen tekabül etmektedir. Beşgenlerin sayısına $B$, altıgenlerin sayısına $A$ dersek, beşgenlerin köşe sayısı $5B$ altıgenlerin köşe sayısı $6A$ olacaktır. Ancak dikkat edilmesi gerekir ki, bir köşeyi iki altıgen ve bir beşgen yani üç tane şekil ortak kullanıyor, yani toplam köşe sayısı $V=\genfrac{}{}{0ex}{}{6A+5B}{3}$ olacaktır. Kenar sayısı da aynı argüman sayesinde $E=\genfrac{}{}{0ex}{}{6A+5B}{2}$ olarak hesaplanır, yüz sayısının da $F=A+B$ olduğu açıktır.

Euler karakteristiği denkleminde yerine yazarsak $B=12$ olarak bulunur. Bir beşgene karşı beş altıgen olduğundan, fakat bu altıgenlerin üçü diğer bir beşgenle ortak kullanıldığı gerçeğinden, $A=20$ olarak bulunur.

Euler karakteristiğinin ilginç kullanım alanlarından başka bir tanesi ile yani ana problemimizle baş başa kalmanın zamanı artık geldi.

Üç Kulübe Problemi

Okuyucu yukarıda bahsedilen bu problemi bir kağıtta çözmeyi deneyip başarılı olamadığını varsayıyoruz. Sorun, her defasında son kenarın her defasında başka bir kenarla kesişmesi ile alakalıdır. Doğal gaz, elektrik veya su borularından herhangi ikisinin kesişmemesi gerekiyor, problemi imkansız kılan da bu zaten. Peki neden imkansız?

Euler'in yaptığı gibi problemi basitleştirme yoluna gidelim. Kulübeler ile elektrik, su ve doğal gaz kaynaklarını birer köşe olarak düşünelim. Borular da kenar olarak... Kulübeleri yukarıya kaynakları aşağıya nokta olarak bir kağıda çizelim. Elimizde 6 köşe ve 9 kenar olması gerektiği açıktır. O halde bu çizgenin düzlemde çizilebilmesi için Euler karakteristiğinden yüz sayısının 5 olması gerekmektedir.

Çizmeye kalkınca, her bir yüzün 4 kenar arasında kalması gerektiğini görürüz. Ayrıca her kenar iki bölge arasında kalması gerektiğinden $4F\le 2E$ olması gerekir, bu da bize $F=5$ eşitliğinin yanlış olduğunu söyler dolayısıyla bu çizgenin düzlemde çizilemeyeceği sonucuna varırız.

Elbette ki boruların kesişmemesi koşulunu kaldırırsak, problem çözülebilir olacaktır. Hatta bu çizgenin özel bir ismi de vardır: $K_{3,3}$ çizgesi.

Wikimedia

Sonuç olarak görebiliyoruz ki, başta mühendisi atma kararımız hatalıymış. Zaten hikayenin geriye kalan kısmında mühendisimiz kapıyı kırarcasına bir heyecanla içeriye giriyor ve problemi evindeki fincan üzerinde çizince çözdüğünü gösteriyor. Bu çözüm için 3Blue1Brown kanalının aşağıdaki videosunu öneririz.

Ayrıca bu videoda görebileceğiniz gibi, fincan üzerinde çözüm mümkündür, çünkü fincan düzlemsel değildir. Bir diğer deyişle, yukarıdaki imkansız çözümün fincan üzerinde çözülebilir olması, fincanın düzlemsel olmadığı kanıtlamaktadır. Başka bir çözüm ise torus üzerindedir:

Science4All