Задача Турана про цегельний завод
Зада́ча Ту́рана про цеге́льний заво́д (англ. Turan's brick factory problem) — задача теорії графів, пов'язана зі знаходженням найменшого числа схрещувань при зображанні на площині повного двочасткового графа[1].
Названа на честь угорського математика Пала Турана, який сформулював задачу, працюючи на цегельному заводі під час Другої світової війни.
Польський математик Казімеж Заранкевич[en] висловив гіпотезу, що деяке просте зображення графа має найменше число схрещень, проте, за винятком окремих випадків, його оптимальність залишається недоведеною[2].
Під час Другої світової війни угорського математика Пала Турана відправили на примусову роботу на цегельну фабрику, де він возив вагонетки з цеглою від печей на склади. На заводі між кожною піччю та кожним складом було прокладено залізничні колії, при цьому вагонетку було складніше штовхати там, де ці колії перетиналися. Це надихнуло Турана на питання про те, як можна перемістити шляхи, щоб мінімізувати число схрещень[1].
З погляду математики це задача про зображання графа на площині: печі та склади задають вершини графа, а залізничні колії — його ребра. Оскільки між кожною піччю та кожним складом прокладено рівно один шлях, такий граф є повним двочастковим. Якщо печей , а складів , такий граф позначають . Задача Турана полягає в тому, щоб розташувати вершини та ребра графа на площині так, щоб жодна вершина не лежала на ребрі, кінцем якого вона не є, і при цьому ребра графа мали найменше число схрещень, відмінних від вершин. При цьому ребра не обов'язково мають бути прямолінійними, хоча у розв'язку, який припускають мінімальним, це так[2].
Задачу Турана вважають однією з перших задач про найменше число схрещень графів[3]. Частковим випадком є класична математична задача «Вода, газ та електрика», в якій роль печей та складів відіграють будинки та ресурси, кожних — по три штуки.
Заранкевич та Казімеж Урбанік були присутні на доповідях Турана в Польщі 1952 року[4] і незалежно опублікували спроби розв'язання задачі[5].
В обох випадках вони пропонували намалювати повний двочастковий граф так (див. зображення на початку статті): намалювати вершини одного кольору («печі») вздовж вертикальної осі, вершини іншого кольору («склади») — вздовж горизонтальної осі, а точку перетину осей вибрати так, щоб з кожного боку було порівну (якщо число вершин даного кольору парне) або майже порівну (якщо їх число непарне). В результаті обидва отримали таке число схрещень ребер графа:
Цей приклад дає обмеження на число схрещень зверху, проте обидва доведення його мінімальності, що дають обмеження знизу, виявилися хибними: 1965 року їх майже одночасно спростували Герхард Рінгель[en] і Пол Кайнен[en][6].
Хоча в загальному випадку питання мінімальності досі залишається гіпотезою, окремі випадки успішно доведено: випадок при (довів сам Заранкевич), а пізніше при [7]. Оскільки для будь-яких двох доведення мінімальності вимагає скінченного числа перевірок, його зроблено за досить малих [8]. Також доведено, що найменше число схрещень становить принаймні 83 % оцінки Заранкевича[9].
- ↑ а б Turan, P. (1977), A note of welcome, Journal of Graph Theory, 1: 7—9, doi:10.1002/jgt.3190010105.
- ↑ а б Pach, Janos; Sharir, Micha (2009), 5.1 Crossings—the Brick Factory Problem, Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures, Mathematical Surveys and Monographs, т. 152, American Mathematical Society, с. 126—127.
- ↑ Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, с. 71, ISBN 9781461209331.
- ↑ Beineke, Lowell; Wilson, Robin (2010), The early history of the brick factory problem, The Mathematical Intelligencer, 32 (2): 41—48, doi:10.1007/s00283-009-9120-4, MR 2657999.
- ↑ Urbanik, K. (1955), Solution du probleme pose par P. Turan, Colloq. Math., 3: 200—201. Як процитовано в Hazewinkel, Michiel, ред. (2001), Задача Турана про цегельний завод, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4
- ↑ Guy, Richard K. (1969), The decline and fall of Zarankiewicz's theorem, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, с. 63—69, MR 0253931.
- ↑ Kleitman, Daniel J. (1970), The crossing number of K5,n, Journal of Combinatorial Theory, 9: 315—323, doi:10.1016/s0021-9800(70)80087-4, MR 0280403.
- ↑ Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), Zarankiewicz's conjecture is finite for each fixed m, Journal of Combinatorial Theory, Series B, 103 (2): 237—247, doi:10.1016/j.jctb.2012.11.001, MR 3018068.
- ↑ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. (2006), Improved bounds for the crossing numbers of Km,n and Kn, SIAM Journal on Discrete Mathematics, 20 (1): 189—202, doi:10.1137/S0895480104442741, MR 2257255.
- Weisstein, Eric W. Гіпотеза Заранкевича(англ.) на сайті Wolfram MathWorld.