Üç yardımcı program sorunu - Three utilities problem

"Su, gaz ve elektrik" buraya yönlendiriyor. Yardımcı programlar için bkz. Toplumsal kullanım.
Üç yardımcı program sorunu. Her ev, kesişen bağlantı hatları olmadan her bir hizmet birimine bağlanabilir mi?
Uçakta tek geçiş gereklidir

Klasik matematiksel bulmaca olarak bilinir üç yardımcı program sorunu; üç kulübe sorunu ya da bazen su, gaz ve elektrik şu şekilde ifade edilebilir:

Bir düzlemde (veya küre) üç kulübe olduğunu ve her birinin su, gaz ve elektrik şirketlerine bağlanması gerektiğini varsayalım. Üçüncü bir boyut kullanmadan veya bağlantıların herhangi birini başka bir şirket veya yazlık aracılığıyla göndermeden, dokuz bağlantının tümünü hiçbir hat birbirini kesmeden yapmanın bir yolu var mı?

Problem, pratik bir mühendislik durumunda var olmayacak kısıtlamaları empoze eden soyut bir matematiksel bilmecedir. matematiksel alanı topolojik grafik teorisi hangi çalışır gömme nın-nin grafikler açık yüzeyler. Daha resmi olarak grafik teorik sorun olup olmadığını sorar. tam iki parçalı grafik K3,3 dır-dir düzlemsel.[1] Bu grafiğe genellikle yardımcı grafik sorunla ilgili olarak;[2] aynı zamanda Thomsen grafiği.[3]

Tarih

Üç yardımcı program sorununun geçmişine ilişkin bir inceleme, Kullman (1979). Soruna ilişkin yayınlanan çoğu referansın sorunu "çok eski" olarak nitelendirdiğini belirtiyor.[4]Kullman tarafından bulunan ilk yayında, Henry Dudeney  (1917 ) buna "su, gaz ve elektrik" adını verir. Ancak Dudeney, sorunun "tepeler kadar eski ... elektrikli aydınlatma, ya da gaz ".[5] Dudeney aynı bulmacayı daha önce de yayınladı. Strand Dergisi 1913'te.[6]

Sorunun bir başka erken versiyonu, üç evin üç kuyuya bağlanmasını içeriyor.[7]Üç çeşmenin tümü ve bir evin dikdörtgen bir duvara dokunduğu üç ev ve üç çeşmeyi de içeren farklı (ve çözülebilir) bir bulmacaya benzer şekilde belirtilir; Bulmaca yine kesişmeyen bağlantıların yapılmasını içerir, ancak modernde olduğu gibi yalnızca belirlenmiş üç ev ve kuyu veya çeşme çifti arasında numberlink bulmacalar.[8]

Matematiksel olarak problem şu şekilde formüle edilebilir: grafik çizimleri of tam iki parçalı grafik K3,3. Bu grafik, Henneberg (1908).[9]Üç köşeden oluşan iki alt kümeye bölünmüş altı köşesi ve bir alt kümeden bir köşeyi diğer alt kümeden bir tepe ile eşleştirmenin dokuz yolunun her biri için dokuz kenarı vardır. Üç yardımcı program sorunu, bu grafiğin sorusudur. bir düzlemsel grafik.[1]

Çözüm

Thomsen grafiği olarak da bilinen yardımcı grafik veya K3,3

Genellikle sunulduğu gibi (düz, iki boyutlu bir düzlemde), yardımcı program bulmacasının çözümü "hayır" dır: herhangi bir çizginin kesişmesi olmadan dokuz bağlantının tümünü yapmanın bir yolu yoktur. Başka bir deyişle, grafik K3,3 düzlemsel değil. Kazimierz Kuratowski 1930'da belirtildi ki K3,3 düzlemsel değildir,[10] buradan sorunun çözümü olmadığı sonucu çıkar. Bununla birlikte Kullman, "Yeterince ilginç bir şekilde, Kuratowski [ K3,3 "düzlemsel olmayan".[4]

Bir düzlemsel gömme bulmanın imkansızlığının bir kanıtı K3,3 aşağıdakileri içeren bir vaka analizi kullanır: Jordan eğri teoremi. Bu çözümde, grafiğin 4 döngüsüne göre köşelerin konumları için farklı olasılıklar incelenir ve bunların hepsinin düzlemsel bir yerleştirme ile tutarsız olduğunu gösterir.[11]

Alternatif olarak, herhangi bir köprüsüz iki parçalı düzlemsel grafik V köşeler ve E kenarlar var E ≤ 2V − 4 birleştirerek Euler formülü V − E + F = 2 (nerede F yüzlerin sayısının en fazla kenar sayısının yarısı olduğu gözlemiyle (her yüzün etrafındaki köşeler evler ve araçlar arasında değişmelidir, bu nedenle her yüzün en az dört kenarı vardır ve her biri kenar tam olarak iki yüze aittir). Fayda grafiğinde, E = 9 ve 2V − 4 = 8, bu eşitsizliği ihlal ediyor, dolayısıyla fayda grafiği düzlemsel olamaz.[12]

Genellemeler

K3,3 tek geçişle çizilmiş.

Düzlemsel grafiklerin iki önemli karakterizasyonu, Kuratowski teoremi düzlemsel grafiklerin tam olarak hiçbirini içermeyen grafikler olduğunu K3,3 ne de tam grafik K5 alt bölüm olarak ve Wagner teoremi düzlemsel grafiklerin tam olarak hiçbirini içermeyen grafikler olduğunu K3,3 ne de K5 olarak minör, düzlemsel olmayışından yararlanın ve genelleştirin K3,3.

Bir simit üzerindeki üç yardımcı program sorununun çözümü.

K3,3 bir toroidal grafik bu, bir üzerinde geçişler olmadan gömülebileceği anlamına gelir. simit. Üç kulübe problemi açısından bu, problemin düzlem (veya küre) boyunca iki delik açılarak ve bunları bir tüp ile birleştirilerek çözülebileceği anlamına gelir. Bu, topolojik özellikler Yüzeyin ve tüpün kullanılması, üç kulübenin çapraz çizgiler olmadan bağlanmasına izin verir. Eşdeğer bir ifade şudur: grafik cinsi Fayda grafiği birdir ve bu nedenle birden az cinsin yüzeyine gömülemez. Birinci cinsin bir yüzeyi simit ile eşdeğerdir. Bir toroidal yerleştirme K3,3 yukarıda açıklandığı gibi, tüpün düzleme bağlandığı iki deliğin geçişin her iki tarafındaki kesişen kenarlardan biri boyunca yerleştirildiği bir tüp ile geçişin değiştirilmesi ile elde edilebilir. Bulmacanın kurallarını değiştirmenin bir başka yolu, hizmet hatlarının kulübelerden veya hizmetlerden geçmesine izin vermektir; bu ekstra özgürlük, bulmacanın çözülmesine izin verir.

Pál Turán 's "tuğla fabrikası sorunu "daha genel olarak bir formül ister minimum geçiş sayısı bir çizimde tam iki parçalı grafik Ka,b köşe sayısı açısından a ve b iki bölümün iki tarafında. Fayda grafiği K3,3 sadece bir geçişle çizilebilir, ancak sıfır geçişle çekilemez, dolayısıyla geçiş numarası birdir.[13]

Diğer grafik teorik özellikler

Fayda grafiği K3,3 bir dolaşım grafiği.O (3,4) -kafes, en küçük üçgen içermez kübik grafik.[3]Diğerleri gibi tam iki parçalı grafikler, bu bir iyi kaplı grafik yani her biri maksimum bağımsız küme aynı boyutta. Bu grafikte, yalnızca iki maksimum bağımsız küme, iki bölümün iki tarafıdır ve açıkça eşittirler. K3,3 sadece yedi taneden biri 3-normal 3 bağlantılı iyi kaplı grafikler.[14]

Aynı zamanda bir Laman grafiği minimum düzeyde oluşturduğu anlamına gelir katı sistem düzleme gömüldüğünde (geçişlerle). Diğer minimum düzlemsel olmayan grafik gibi, düzlemsel olmayan bir Laman grafiğinin en küçük örneğidir, K5, minimum düzeyde katı değildir.

Referanslar

  1. ^ a b Bóna, Miklós (2011), Kombinatorikte Bir Yürüyüş: Numaralandırma ve Grafik Teorisine Giriş, World Scientific, s. 275–277, ISBN  9789814335232. Bóna bulmacayı (üç kuyuya bağlanan üç ev şeklinde) s. 275 ve s. 277 "çizim problemine eşdeğerdir" K3,3 geçişleri olmayan bir düz yüzeyde ".
  2. ^ Fayda Grafiği itibaren mathworld.wolfram.com
  3. ^ a b Coxeter, H. S. M. (1950), "Kendi kendine ikili konfigürasyonlar ve düzenli grafikler", Amerikan Matematik Derneği Bülteni, 56: 413–455, doi:10.1090 / S0002-9904-1950-09407-5, BAY  0038078.
  4. ^ a b Kullman, David (1979), "Kamu Hizmetleri Sorunu", Matematik Dergisi, 52 (5): 299–302, JSTOR  2689782.
  5. ^ Dudeney, Henry (1917), "Sorun 251 - Su, Gaz ve Elektrik", Matematikte eğlenceler, Thomas Nelson
  6. ^ Dudeney, Henry (1913), "Şaşkınlıklar, yeni başlayanlar için bazı kolay bulmacalar", Strand Dergisi, cilt. 46, p. 110.
  7. ^ "Bulmaca", Başarılı Tarım, cilt. 13, p. 50, 1914; "Bir kuyu ve ev bulmacası", Gençlerin Arkadaşı, cilt. 90 hayır. 2, s. 392, 1916.
  8. ^ "32. Çeşme bulmacası", Sihirbazın Kendi Kitabı Veya Tüm Büyüleme Sanatı, New York: Dick ve Fitzgerald, 1857, s. 276.
  9. ^ Henneberg, L. (1908), "Die graphische Statik der starren Körper", Encyklopädie der Mathematischen Wissenschaften, 4.1, s. 345–434. Alıntı yaptığı gibi Coxeter (1950). Özellikle bakın s. 403.
  10. ^ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fon, sermaye. Matematik. (Fransızcada), 15: 271–283.
  11. ^ Trudeau Richard J. (1993), Grafik Teorisine Giriş (Düzeltilmiş, genişletilmiş cumhuriyet. Ed.), New York: Dover Pub., S. 68–70, ISBN  978-0-486-67870-2, alındı 8 Ağustos 2012
  12. ^ Kappraff, Jay (2001), Bağlantılar: Sanat ve Bilim Arasındaki Geometrik Köprü Knots and Everything hakkında K & E Serisi, 25, World Scientific, s. 128, ISBN  9789810245863.
  13. ^ Pach, János; Sharir, Micha (2009), "5.1 Geçişler - Tuğla Fabrikası Sorunu", Kombinatoryal Geometri ve Algoritmik Uygulamaları: Alcalá Dersleri, Matematiksel Araştırmalar ve Monograflar, 152, Amerikan Matematik Derneği, s. 126–127.
  14. ^ Campbell, S.R .; Ellingham, M.N.; Royle, Gordon F. (1993), "İyi kaplanmış kübik grafiklerin bir karakterizasyonu", Kombinatoryal Matematik ve Kombinatoryal Hesaplama Dergisi, 13: 193–212, BAY  1220613.

Dış bağlantılar