Проблема Турана о кирпичной фабрике // Numberphile

Проблема Турана о кирпичной фабрике (англ. Turan’s brick factory problem) — задача теории графов, связанная с нахождением минимального числа пересечений при изображении на плоскости полного двудольного графа. Во время Второй мировой войны венгерский математик Пал Туран был отправлен на принудительную работу на кирпичную фабрику, где он возил вагонетки с кирпичами из печей на склады. На фабрике между любой печью и любым складом были проложены железнодорожные пути, при этом вагонетку было сложнее толкать там, где эти пути пересекались. Это вдохновило Турана на вопрос о том, как можно перерасположить пути, чтобы минимизировать число пересечений. С точки зрения математики это задача изображения графа на плоскости: печи и склады задают вершины графа, а железнодорожные пути — его рёбра. Поскольку между каждой печью и каждым складом проложен ровно один путь, такой граф является полным двудольным. Если печей p, а складов s, то такой граф обозначается K{p,s}. Проблема Турана состоит в том, чтобы расположить вершины и рёбра графа K{p,s} на плоскости так, чтобы никакая вершина не лежала на ребре, концом которого она не является, и при этом у ребёр графа было минимальное число пересечений, отличных от вершин. При этом рёбра не обязательно должны быть прямолинейными, хотя в решении, которое предполагается минимальным, это так. Проблема Турана считается одной из первых задач о минимальном числе пересечений графов. Частным случаем является классическая математическая задача «Домиков и колодцев», в которой роль печей и складов играют дома и колодцы, каждых — по три штуки. Польским математиком Казимежем Заранкевичем была высказана гипотеза, что некоторое простое изображение графа имеет минимальное количество пересечений, однако, за исключением частных случаев, его оптимальность остаётся недоказанной. Перевод и озвучка: @MadAstronomer Оригинал: