Зада ча Ту рана про цеге льний заво д англ Turan s brick factory problem задача теорії графів пов язана зі знаходженням

Зада́ча Ту́рана про цеге́льний заво́д (англ. Turan's brick factory problem) — задача теорії графів, пов'язана зі знаходженням найменшого числа схрещувань при зображанні на площині повного двочасткового графа.

Оптимальне розташування для графа $K 4,7$ має 18 схрещень

Названа на честь угорського математика Пала Турана, який сформулював задачу, працюючи на цегельному заводі під час Другої світової війни.

Польський математик ^[en] висловив гіпотезу, що деяке просте зображення графа має найменше число схрещень, проте, за винятком окремих випадків, його оптимальність залишається недоведеною.

Походження та формулювання

Під час Другої світової війни угорського математика Пала Турана відправили на примусову роботу на цегельну фабрику, де він возив вагонетки з цеглою від (печей) на склади. На заводі між кожною піччю та кожним складом було прокладено залізничні колії, при цьому вагонетку було складніше штовхати там, де ці колії перетиналися. Це надихнуло Турана на питання про те, як можна перемістити шляхи, щоб мінімізувати число схрещень.

З погляду математики це задача про зображання графа на площині: печі та склади задають вершини графа, а залізничні колії — його ребра. Оскільки між кожною піччю та кожним складом прокладено рівно один шлях, такий граф є повним двочастковим. Якщо печей $p$ , а складів $s$ , такий граф позначають $K_{p,s}$ . Задача Турана полягає в тому, щоб розташувати вершини та ребра графа $K_{p,s}$ на площині так, щоб жодна вершина не лежала на ребрі, кінцем якого вона не є, і при цьому ребра графа мали найменше число схрещень, відмінних від вершин. При цьому ребра не обов'язково мають бути прямолінійними, хоча у розв'язку, який припускають мінімальним, це так.

Задачу Турана вважають однією з перших задач про найменше число схрещень графів. Частковим випадком є класична математична задача «Вода, газ та електрика», в якій роль печей та складів відіграють будинки та ресурси, кожних — по три штуки.

Спроби розв'язання

Заранкевич та Казімеж Урбанік були присутні на доповідях Турана в Польщі 1952 року і незалежно опублікували спроби розв'язання задачі.

В обох випадках вони пропонували намалювати повний двочастковий граф так (див. зображення на початку статті): намалювати вершини одного кольору («печі») вздовж вертикальної осі, вершини іншого кольору («склади») — вздовж горизонтальної осі, а точку перетину осей вибрати так, щоб з кожного боку було порівну (якщо число вершин даного кольору парне) або майже порівну (якщо їх число непарне). В результаті обидва отримали таке число схрещень ребер графа:

{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m-1}{2}}{\biggr \rfloor }.

Цей приклад дає обмеження на число схрещень зверху, проте обидва доведення його мінімальності, що дають обмеження знизу, виявилися хибними: 1965 року їх майже одночасно спростували ^[en] і ^[en].

Хоча в загальному випадку питання мінімальності досі залишається гіпотезою, окремі випадки успішно доведено: випадок $K_{p,s}$ при $p\leqslant 3$ (довів сам Заранкевич), а пізніше $K_{p,s}$ при $p\leqslant 6$ . Оскільки для будь-яких двох $p,s$ доведення мінімальності вимагає скінченного числа перевірок, його зроблено за досить малих $p,s$ . Також доведено, що найменше число схрещень становить принаймні 83 % оцінки Заранкевича.

Див. також

Задача Заранкевича

Примітки

Turan, P. (1977), A note of welcome, , 1: 7—9, doi:10.1002/jgt.3190010105.
; (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 .
; (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), Задача Турана про цегельний завод, Математична енциклопедія, , ISBN
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.
(1970), The crossing number of $K 5, n$ , , 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$ , , 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 $K m,n$ and $K n$ , SIAM Journal on Discrete Mathematics, 20 (1): 189—202, doi:10.1137/S0895480104442741, MR 2257255.

Посилання

Weisstein, Eric W. Гіпотеза Заранкевича(англ.) на сайті Wolfram MathWorld.

[turan-1] Turan, P. (1977), A note of welcome, , 1: 7—9, doi:10.1002/jgt.3190010105.

[ps-2] ; (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-3] Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, с. 71, ISBN .

[early-4] ; (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-5] Urbanik, K. (1955), Solution du probleme pose par P. Turan, Colloq. Math., 3: 200—201. Як процитовано в Hazewinkel, Michiel, ред. (2001), Задача Турана про цегельний завод, Математична енциклопедія, , ISBN

[fall-6] 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-7] (1970), The crossing number of $K 5, n$ , , 9: 315—323, doi:10.1016/s0021-9800(70)80087-4, MR 0280403.

[crs-8] Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), Zarankiewicz's conjecture is finite for each fixed $m$ , , Series B, 103 (2): 237—247, doi:10.1016/j.jctb.2012.11.001, MR 3018068.

[kmprs-9] Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. (2006), Improved bounds for the crossing numbers of $K m,n$ and $K n$ , SIAM Journal on Discrete Mathematics, 20 (1): 189—202, doi:10.1137/S0895480104442741, MR 2257255.