3 kuyu 3 ev problemi
Bu madde, öksüz maddedir; zira herhangi bir maddeden bu maddeye verilmiş bir bağlantı yoktur. (Şubat 2026) |
3 kuyu – 3 ev problemi (İngilizce: three utilities problem), 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ı
[değiştir | kaynağı değiştir]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
[değiştir | kaynağı değiştir]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.[1] Bu problem, düzlemsel olmayan çizgelerin karakterizasyonunu veren Kuratowski teoremi ile doğrudan ilişkilidir.
Düzlemsellik ve Euler formülü
[değiştir | kaynağı değiştir]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.[2]
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.[3]
Sonuç
[değiştir | kaynağı değiştir]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
[değiştir | kaynağı değiştir]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
[değiştir | kaynağı değiştir]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.[4]