6.6. Минимальное число аварий на кирпичном заводе

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

рельсовым путем с каждой погрузочной платформой, то пути имеют большое число пересечений. Когда вагонетки проходят пересечения, они часто сходят с рельсов. В результате возникают потери кирпичей вследствие их боя и транспортные пробки. Задача заключается в проведении железнодорожных путей от печей к местам назначения с минимальным числом пересечений, чтобы уменьшить опасность схода вагонеток с рельсов.

Рис. 6.15.

Эту задачу можно решить в рамках теории графов, приняв железнодорожные пути за ребра графов, связывающие вершины (соответствующие погрузочным платформам). При этом накладывается условие, запрещающее трем (или более) ребрам пересекаться в одной точке, которая не является вершиной. Два ребра, однако, могут пересекаться в промежуточной точке. Например, в случае четырех печей и четырех платформ имеется четыре таких пересечения, отмеченных знаком на рис. 6.15.

Теорема 6.6. Минимальное число внутренних пересечений ребер, соединяющих каждую из точек с каждой из точек на плоскости (предполагается, что два ребра пресекаются не более чем в одной точке), не меньше чем

Прежде чем доказать теорему, определим понятие веера и докажем одну лемму.

Определение. Веер в вершине состоит из всех ребер, инцидентных и, без граничных точек. Таким образом, также исключается из веера.

Замечание. Заметим, что если взять на плоскости два множества из трех вершин каждое и образовать три

веера в вершинах одного множества так, чтобы три вершины второго множества являлись конечными для каждого веера, то получим граф Понтрягина — Куратовского, который не является плоским, и следовательно, вееры должны иметь, по крайней мере, одну точку пересечения, которая не является вершиной.

Лемма 6.7. Рассмотрим плоский граф, состоящий из трех вееров в вершинах каждый которых имеет одни и те же граничные точки вместе с соответствующими вершинами. Число внутренних пересечений при условии, что в одной точке пересекаются, по крайней мере, не более двух ребер,

Доказательство. Доказательство проведем по индукции. Согласно предыдущему замечанию лемма справедлива, если Предположим, что лемма справедлива для и докажем, что она справедлива В последнем случае число пересечений должно быть, по крайней мере,

Рассмотрим подграфы состоящие из вершин вееров в определяемых вершинами и вершин Если бы каждая пара таких подграфов имела общую точку, отличную от конечных точек вееров, то число пересечений получалось бы при рассмотрении всех сочетаний подграфов по два. В этом случае число пересечений равно

Но если то а если то В этом случае лемма была бы доказана.

Пусть теперь некоторая пара подграфов не имеет ни одной общей точки кроме Рассмотрим подграф состоящий из объединения Сми Согласно замечанию каждый другой подграф должен

иметь, по крайней мере, одну внутреннюю точку пересечения с С. Так как число оставшихся подграфов разно то имеется, по крайней мере, пересечений с С, и все точки пересечения различны, поскольку никакие три линии не могут пересечься в одной точке, если она не является граничной точкой. Добавим к этому числу получаемое, по предположению индукции, минимально возможное число пересечений в нашем графе без ими и вееров . Получим

Заметим, например, что если число вершин равно имеется, по крайней мере, пересечений, которые мы добавляем к пересечениям с С. Лемма доказана.

Доказательство теоремы. Снова применим индукцию. Согласно сделанному замечанию теорема справедлива для случая Докажем, что если теорема справедлива для то она также справедлива для комбинаций Предположим, что имеется печей и платформа Граф взаимосвязей печей и платформ можно получить из графа задачи с и добавив вершину и связав ее ребрами с Граф можно рассматривать как множество вееров в вершинах с одними и теми же граничными точками . Пусть четное, т. е. будем рассматривать минимальное число пересечений веера в с веерами в взятыми вместе, затем с веерами взятыми вместе и т. д. Имеем таких пар, и согласно лемме, если то существует, по крайней мере, пересечений с каждой парой, и следовательно, общее число пересечений равно, по крайней мере, если же то число пересечений разно, по крайней мере, Если нечетное, т. е. то можно пренебречь единственным веером, оставшимся в и получить те же самые числа Согласно предположению индукции граф имеет, по крайней мере, пересечений. Добавив это число к полученным выше

результатам, получаем выражение для наименьшего возможного числа пересечений

из которого имеем

Аналогично получаем, что наименьшее число пересечений равно,

откуда

Теорема доказана.

Построение путей с минимальным числом пересечений можно выполнить следующим образом. Рассмотрим прямоугольные координаты на плоскости. Если возьмем на оси х точки с абсциссами

а если то возьмем на оси х точки с абсциссами

Если возьмем на оси у точки с ординатами

а если возьмем на оси у точки с ординатами

Затем соединим отрезками каждую точку оси х с каждой точкой оси у. Все пересечения в данном случае могут быть легко подсчитаны.

Замечание. С помощью индукции можно также доказать, что минимальное число областей на

плоскости получаемое при построении рассмотренного графа путей, равно

Упражнения

(см. скан)