Turán'ın tuğla fabrikası sorunu - Turán's brick factory problem
 |
Matematikte çözülmemiş problem : Zarankiewicz tarafından verilen sayıdan daha az kesişme ile tam iki taraflı grafik çizilebilir mi?
(matematikte daha fazla çözülmemiş problem)
|
Gelen matematik bir grafik çizimi , turan en tuğla fabrikası sorunu sorar geçişlerinin az sayıda bir bir çizim tam ikili grafik . Sorunun adı , II.Dünya Savaşı sırasında bir tuğla fabrikasında çalışmaya zorlanırken formüle eden Pál Turán'dan geliyor .
Kazimierz Zarankiewicz tarafından bulunan bir çizim yönteminin her tam iki parçalı grafiğe doğru cevabı verdiği varsayıldı ve bunun doğru olduğu ifadesi Zarankiewicz geçiş sayısı varsayımı olarak bilinmeye başladı . Sadece bazı özel durumlar çözülürken varsayım açık kalır.
Kökeni ve formülasyon
Sırasında Dünya Savaşı , Macar matematikçi Pál Turan dan tuğla vagon yükleri iterek bir tuğla fabrikasında işe zorunda kaldı fırınlarda depolama sitelerine. Fabrikanın her bir fırından her bir depolama alanına giden yolları vardı ve vagonların birbirini kesiştiği noktalarda itilmesi daha zordu. Turán, bu hatlar arasındaki geçiş sayısını en aza indirgemek için fabrikanın nasıl yeniden tasarlanabileceğini sormak için bu durumdan ilham aldı.
Matematiksel olarak, bu problem , köşeleri fırınları ve depolama alanlarını temsil eden ve kenarları her bir fırından her bir depolama alanına giden yolları temsil eden tam bir çift taraflı grafiğin bir grafik çizimini istemek olarak resmileştirilebilir . Grafik, her köşe noktası bir nokta olarak, her kenar iki uç noktasını birleştiren bir eğri olarak ve rastlantısal olmadığı bir kenara tepe noktası yerleştirilmeyecek şekilde düzlemde çizilmelidir. Grafikte ayrık olan iki kenar düzlemde boş olmayan bir kesişme noktasına sahip olduğunda bir kesişme sayılır. Öyleyse soru, böyle bir çizimdeki minimum geçiş sayısı nedir?
Turán'ın bu problemi formülasyonu, genellikle grafiklerin kesişen sayılarının ilk çalışmalardan biri olarak kabul edilir . (Aynı kavramın sosyolojide, sosyogramları çizme yöntemlerinde başka bir bağımsız formülasyonu ve çok daha eski bir bulmaca olan üç hizmet sorunu , üç fırın ve üç depolama tesisi ile tuğla fabrikası sorununun özel bir durumu olarak görülebilir.) Geçiş sayıları, o zamandan beri, grafik çiziminde merkezi bir çalışma nesnesi ve VLSI tasarımında ve ayrık geometride önemli bir araç olarak daha büyük önem kazanmıştır .
Üst sınır
Hem Zarankiewicz hem de Kazimierz Urbanik , Turán'ın 1952'de Polonya'daki farklı görüşmelerde tuğla fabrikası sorunu hakkında konuştuğunu gördü ve geçiş sayısı için eşdeğer formüllerle sorunun çözümüne yönelik girişimlerini bağımsız olarak yayınladı. Her ikisinin de gösterdiği gibi, tam bir ikili grafik K m, n (bir tarafta m köşeli bir grafik , diğer tarafta n köşeli ve iki tarafı birleştiren mn kenarları olan bir grafik ) bir dizi kesişme ile çizmek her zaman mümkündür. eşittir
Yapısı basittir: m köşelerini düzlemin x eksenine yerleştirin, başlangıç noktasından kaçının , y ekseninin solunda ve sağında eşit veya neredeyse eşit sayıda nokta olacak şekilde yerleştirin . Benzer şekilde, başlangıç noktasından kaçınarak, x ekseninin üstünde ve altında eşit veya neredeyse eşit sayıda nokta olacak şekilde n köşeyi düzlemin y eksenine yerleştirin . Ardından, x eksenindeki her noktayı y eksenindeki her noktaya düz bir çizgi parçasıyla bağlayın .
Bununla birlikte, bu formülün optimal olduğuna, yani daha az kesişen çizim olamayacağına dair kanıtları hatalıydı. Boşluk, yayınlandıktan on bir yıl sonra neredeyse aynı anda Gerhard Ringel ve Paul Kainen tarafından keşfedilmedi . Bununla birlikte, Zarankiewicz ve Urbanik'in formülünün optimal olduğu varsayılmaktadır. Bu, Zarankiewicz geçiş sayısı varsayımı olarak bilinir hale geldi. Bazı özel durumlarının doğru olduğu bilinmesine rağmen, genel durum açık kalmaktadır.
Alt sınırlar
Yana K m, n ve K n, m izomorf olan, davaya yeterlidir m ≤ n . Buna ek olarak, m ≤ 2 için Zarankiewicz'in yapısı hiçbir kesişme sağlamaz, bu da elbette en iyisi olamaz. Yani önemsiz olmayan durumlar, m ve n'nin her ikisinin de ≥ 3 olduğu durumlardır .
Zarankiewicz'in varsayımı kanıtlama girişimi, K m , n genel durumu için geçersiz olmasına rağmen , m = 3 durumu için işe yarar . O zamandan beri diğer küçük m değerlerine genişletildi ve Zarankiewicz varsayımının, m ≤ 6 ile K m, n tam iki parçalı grafikler için doğru olduğu bilinmektedir . Varsayımın K 7,7 , K 7,8 ve K 7,9 için de doğru olduğu bilinmektedir . Bir karşı-varsa, olduğu, bir grafiktir K m, n Zarankiewicz bağlanan daha sonra her iki karşı-en küçük, daha az geçişlerini gerektiren m ve n, tek olmalıdır.
Her sabit m seçeneği için, tüm K m, n için varsayımın doğruluğu, yalnızca sınırlı sayıda n seçeneği test edilerek doğrulanabilir . Daha genel olarak, her iki parçalı grafiğin, Zarankiewicz sınırı tarafından verilen sayının en az% 83'ü (yeterince büyük grafikler için) olan bir dizi kesişim gerektirdiği kanıtlanmıştır. Bu alt sınır ile üst sınır arasındaki boşluğun kapatılması açık bir sorun olmaya devam etmektedir.
Doğrusal geçiş numaraları
Kenarların rastgele eğriler yerine düz çizgi parçaları olarak çizilmesi gerekiyorsa, bazı grafiklerin kavisli kenarlarla çizildiğinden daha fazla kesişme olması gerekir. Ancak, Zarankiewicz tarafından tam iki parçalı grafiklerin kesişen sayıları için oluşturulan üst sınır, yalnızca düz kenarlar kullanılarak elde edilebilir. Bu nedenle, Zarankiewicz varsayımı doğruysa, tam iki parçalı grafiklerin kesişen sayılarına eşit doğrusal geçiş sayıları vardır.