3 kuyu 3 ev problemi

3 kuyu – 3 ev problemi (), grafik teorisinde klasik bir örnek olarak ele alınan ve düzlem üzerinde çözülemediği matematiksel olarak kanıtlanmış bir problemdir. Problem, grafik teorisinde tam iki parçalı grafik olan K₃,₃ ile modellenir ve düzlemsel olmayan grafiklerin temel örneklerinden biri olarak kabul edilir.

 Problemin tanımı 
Problem, üç adet kuyu ve üç adet evin bulunduğu bir düzeni konu alır. Her evin her kuyuya bağlanması gerekmekte, çizilen bağlantı çizgilerinin birbirini kesmemesi ve bağlantıların ortak kullanılmaması şart koşulmaktadır. Amaç, bu koşullar altında tüm evleri kuyulara bağlayan bir düzen kurmaktır.

Bu kurallar altında problemin düz bir yüzey üzerinde çözülemediği gösterilmiştir.

 Grafik teorisi ile modelleme 
Problem grafik teorisi kullanılarak modellenebilir. Evler ve kuyular iki ayrı köşe kümesi olarak ele alındığında, her evin her kuyuya bağlanması gerektiği için ortaya çıkan yapı tam iki parçalı bir grafiktir. Bu grafik literatürde K₃,₃ olarak adlandırılır.

K₃,₃ grafiği altı köşeden (üç ev ve üç kuyu) ve dokuz kenardan oluşur. Temel soru, bu grafiğin düzlem üzerinde kenarları kesişmeden çizilip çizilemeyeceğidir.West, D. B. (2001). Introduction to Graph Theory. Prentice Hall. Bu problem, düzlemsel olmayan çizgelerin karakterizasyonunu veren
Kuratowski teoremi ile doğrudan ilişkilidir.

 Düzlemsellik ve Euler formülü 
Düzlemsel grafikler için geçerli olan Euler formülü şu şekildedir:

 V − E + F = 2

Burada V köşe sayısını, E kenar sayısını ve F yüz sayısını ifade eder.Diestel, R. (2017). Graph Theory. Springer.

K₃,₃ grafiği tek sayılı çevrimler içermez. Bu nedenle grafikte oluşabilecek her yüz en az dört kenarla çevrilidir. Düzlemsel bir grafikte her kenar iki yüzü sınırladığı için aşağıdaki eşitsizlik elde edilir:

 4F ≤ 2E

Buradan F ≤ E/2 sonucu elde edilir. Bu eşitsizlik Euler formülünde yerine konulduğunda:

 V − E + E/2 ≥ 2

eşitsizliği ortaya çıkar. K₃,₃ grafiği için V = 6 ve E = 9 değerleri kullanıldığında:

 6 − 9/2 = 1,5

sonucu elde edilir. Bu değer Euler formülünün gerektirdiği 2 değerinden küçüktür ve bir çelişki oluşturur.Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.

 Sonuç 
Ortaya çıkan bu çelişki, K₃,₃ grafiğinin düzlemsel olmadığını gösterir. Dolayısıyla 3 kuyu – 3 ev problemi, düz bir yüzey üzerinde ve çizgiler kesişmeden çözülemez. Bu durum, bireysel çizim yöntemlerinden bağımsız olarak matematiksel yapının doğasından kaynaklanmaktadır.

 Alternatif çözümler 
Problem, düzlem dışına çıkıldığında çözülebilir. Üç boyutlu uzayda bağlantılardan birinin alttan geçirilmesi, yüzeyin delinerek arka tarafın kullanılması veya küresel bir yüzey üzerinde çizim yapılması durumunda çözüm mümkündür. Ancak bu yaklaşımlar, problemin klasik tanımında yer alan kuralları ihlal eder.

 Kuratowski teoremi ile ilişkisi 
3 kuyu – 3 ev problemi, Kuratowski teoreminin bilinen örneklerinden biridir. Bu teoreme göre bir grafik, K₅ veya K₃,₃ grafiğini altgraf olarak içeriyorsa düzlemsel değildir.Tutte, W. T. (1984). Graph Theory. Cambridge University Press.
 Ayrıca bakınız 
 Graf teorisi
 Königsberg'in yedi köprüsü

 Kaynakça 

Kategori:Matematiksel problemler