Дискретно-непрерывная математика (стр. 70 )

А(х) = 1+х-+х2.

Подставляя А(хk) = 1+хk+х2k вместо каждого уk в со­ответствующий циклический индекс (определенный ра­нее), получим

Так, имеется, например, 8 различных графов рас­сматриваемого типа с четырьмя ребрами. Они показаны на рис. 5.14.

Рис. 5.14.

Изменяя определения фигур, объемов и Р, мы можем решить другие графотеоретпческпе задачи перечисления.

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

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

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

Pис. 5.15

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

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

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

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

Лемма 5.7. Рассмотрим плоский граф, состоящий из трех вееров в вершинах u1, и2. и3, каждый из которых имеет одни и те же граничные точки v1, v2, ..., vm вме­сте с соответствующими вершинами. Число внутренних пересечений при условии, что в одной точке пересекают­ся, по крайней мере, не более двух ребер,

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

Рассмотрим подграфы Ck (k=1, 2, .... т), состоя­щие из вершин vk

(k=1, 2, .... m), вееров в vk (k = 1, 2,..., /п), определяемых вершинами

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

Но если т = 2r+2, то а = 2r2+3r + 1>r2+r; а если т= 2r+3, то

а = 2r2+5r+3> (r+1)2. В этом случае лем­ма была бы доказана.

Пусть теперь некоторая пара подграфов Ck1 и Ck2 не имеет ни одной общей точки кроме u1, и2. и3. Рассмот­рим подграф С′, состоящий из объединения Ck1 и Ck2. Согласно замечанию каждый другой подграф должен иметь, по крайней мере, одну внутреннюю точку пересечения с С′. Так как число оставшихся подграфоз разно т—2, то имеется, по крайней мере, т—2 пересе­чений с С′, и все т—2 точки пересечения различны, по­скольку никакие три линии не могут пересечься в одной точке, если она не является граничной точкой. Добавим к этому числу получаемое, по предположению индукции, минимально возможное число пересечений в нашем графе без vk1 и vk2 и вееров Ck1 и Ck2. Получим

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

Доказательство теоремы. Снова применим индукцию. Согласно сделанному замечанию теорема справедлива для случая r=1, s=l. Докажем, что если теорема справедлива для т и п, то она также справед­лива для комбинаций (т, п+1), (m+1, n) и (m+1, п+1). Предположим, что имеется т печей О1, О2, ... ,.., От и (п + 1) платформа Р1, Р2, ..., Рп+1. Граф вза­имосвязей печей и платформ можно получить из графа G задачи с О1, О2, .... От и Р1, Р2, ..., Рп, добавив вершину Рп+1 и связав ее ребрами с О1, О2, ... ,.., От. Граф G можно рассматривать как множество вееров в вершинах Р1, Р2, ..., Рп с одними и теми же граничными точками О1, ..., От. Пусть п — четное, т. е. n=2s; бу­дем рассматривать минимальное число пересечении веера в Pn+1 с веерами в P1 и Р2, взятыми вместе, затем с веерами Р3 и Р4, взятыми вместе и т. д. Имеем s та­ких пар, и согласно лемме, если т=2r, то существует, по крайней мере, (r2— r) пересечений с каждой парой, и следовательно, общее число пересечений равно, по крайней мере, (r2—r)s; если же m=2r +l, то число пе­ресечений равно, по крайней мере, r2s. Если п — нечет­ное, т. е. n=2s+1, то можно пренебречь единственным веером, оставшимся в Рп, и получить те же самые числа (r 2—r)s и r2s. Согласно предположению индукции сам граф G имеет, по крайней мере, (r 2— r) (s2—s) пересе­чений. Добавив это число к полученным выше результатам, получаем выражение для наименьшего возможного числа пересечений

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

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

откуда

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

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

— r, —( r —1),...,—2, —1, 1,2,..., r,

а если т = 2r +1, то возьмем на оси х точки с абсцис­сами

Если n = 2s, возьмем на оси у точки с ординатами

-s, -(s-1), ...,-2, -1, 1, 2, ...,s,

а если n = 2s+l, возьмем на оси у точки с ординатами

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

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

Упражнения

8. Построить связи для задачи с пятью печами и четырьмя плат­формами согласно описанной выше процедуре.

9. Повторить упражнение 8 для задачи с пятью печами п шестью платформами.

5.7. Минимальное число пересечений в полных графах

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