Реберные пересечения в полных графах

Предположим, что на плоскости задана некоторая плоская триангуляция G, содержащая v вершин (v >2). Если соединить ребрами все пары вершин, не инцидентные в графе G, то получим полный граф G' являющийся сверхграфом для G и имеющий столько же вершин, что и G. Так как полный граф с v вершинами имеет ребер ₂ (v-l)v.

е' = С_п =—-, а для плоской триангуляции с тем же количеством вершин е = 3(v — 2), то для того, чтобы из графа G получить полный граф G' необходимо добавить.

(v-l)v (v-3)(v-4).

Ае-е — е = —-— - 3(v — 2) =—- ребер.

Если исходная триангуляция G являлась полным графом, то она совпадает со своим пополнением G' и Ае = 0. Последнее равенство возможно лишь для п=3 и п-4. Другими словами, лишь полные графы с тремя и четырьмя.

Рис. 91 Рис. 92

Заметим, что полные графы с одной (изолированная точка) и двумя вершинами (отрезок) также являются плоскими, но не являются плоскими триангуляциями.

Так как при добавлении хотя бы одного ребра к плоской триангуляции G мы получим уже не плоский граф G', то его изображение на плоскости станет «неправильным» (т.е. появятся реберные пересечения). Ясно, что минимальное количество R (v) реберных пересечений в полном графе с v вершинами не меньше числа Ае :

Так, например, минимальное количество реберных пересечений для полного графа с 5 вершинами равно 1, а для полного графа с 6 вершинами равно 3 (см. рис. 93 и 94). Это согласуется с неравенствами R (5) > 1 и Л (6) > 3.

Рис 93 Рис 94

Важно отметить, что минимальное количество реберных пересечений R (v) для v>6 будет строго больше числа Де. Это связано с тем, что каждое новое ребро, добавляемое к графу, может иметь не одно, а несколько пересечений с другими ребрами. Более точную оценку количества реберных пересечений в полных графах для v>6 дают следующие выражения, полученные Т. Саати (см. [2]):

Попытаемся теперь оценить минимальное число реберных пересечений в полных двудольных графах. Для этого предварительно заметим, что если двудольный граф является графом из многоугольников, то каждая его грань ограничена четным числом ребер. Это связано с тем, что любой цикл в двудольном графе имеет четное число ребер (каждое ребро цикла соединяет вершины из разных «долей»). Пусть нам задан плоский двудольный граф G, в первой «доле» которого содержится V; вершин, а во второй «доле» — V2 вершин (v;, V2 >1). Будем его называть максимально плоским, если добавление ребра между любой парой вершин из разных «долей» приводит к нарушению его планарности. Ясно, что такой максимально плоский двудольный граф G является графом из четырехугольников. Поэтому, используя формулу (2.3.6) для v=v/+V2 и п=4, получим, что е= 2(v, + v₂ — 2). Соединив теперь ребрами все пары не инцидентных вершин из разных «долей» получим полный двудольный граф G', являющийся сверхграфом для G. Так как количество ребер графа G' равно е' =V/ v₂, то для превращения максимально плоского двудольного графа G в полный двудольный сверхграф G' необходимо добавить ровно Де = е' - е = v, v₂ — 2(v, + v₂ — 2) = (v, — 2Xv₂ — 2) ребер. Следовательно, количество реберных пересечений /?(v,, v₂) для полного двудольного графа с v,+v₂ вершинами (v_;, V2>1) не меньше числа Де:

Из вышесказанного следует, что любой полный двудольный граф, хотя бы одна из «долей» которого содержит ровно 2 вершины, является плоским (см. рис. 95). Очевидно, что если хотя бы одна из долей полного двудольного графа содержит всего одну вершину, то этот граф не будет графом из четырехугольников, но он также является плоским (см. рис. 96). Если же обе «доли» полного двудольного графа содержат более чем по 2 вершины, то такой граф плоским не является и минимальное количество его реберных пересечений /?(v, v₂) удовлетворяет неравенству (2.3.10). Например, полный двудольный граф, содержащий по 3 вершины в каждой «доле», не будет плоским и всегда будет иметь как минимум одно реберное пересечение (так как Л (3,3) > (3−2)(3−2) = 1, см. рис.

• 97). Точно так же, применяя неравенство (2.3.10) для v/=3 и v₂=4, получим, что /?(3,4) > (3 — 2)(4 — 2) = 2 (см. рис.
• 98) .

Рис. 95 Рис- 96

Рис. 97.

Рис. 98.

Заметим, что для больших значений V/ и V2 выражение (2.3.10) является слишком грубым. Для того, чтобы найти точную оценку для /?(v, v₂), рассмотрим сначала случай, когда в одной из «долей» графа содержится три вершины.

Лемма. Справедливы следующие равенства:

Доказательство. Как было показано выше, /?(3,1) = R (3,2) =0, /?(3,3)=1. Рассмотрим граф G, во второй «доле» которого содержится v>3 вершин В/, В2, …, В_у, а в первой «доле» — три вершины A_t, А₂, А₃. Этот граф содержит в себе полный двудольный подграф G/ с множествами вершин (A_t, А₂, А₃} и (B_h В₂}, и полный двудольный подграф G₂ с множествами вершин {А/, Л₂, А₃} и {В₃, В_у }. Три ребра, выходящие из каждой из вершин В₃,…, Ву, имеют, как минимум, одно пересечение с ребрами графа G], т. е. ребра графа G₂ имеют не менее (v-2) пересечений с ребрами графа G/. Но, кроме того, ребра графа G₂ имеют не менее /?(3,у — 2) внутренних пересечений. Поэтому минимальное количество реберных пересечений /?(3,у)в графе G складывается из (v-2) пересечений ребер из G₂ с ребрами из G/ и минимального количества R(3, V — 2) внутренних пересечений в графе G₂. Таким образом, приходим к следующей рекуррентной формуле:

Представляя Л (3,у)в виде степенной функции от v и используя рекуррентную формулу, методом неопределенных коэффициентов находим, что.

v² v.

/?(v) = —— —+ С, где С — некоторая постоянная. Для четного v=2r эту постоянную найдем из условия R (3,2) =0, а для нечетного v=2r+l — из условия R (3,3) =1. В результате получим, что С=0 для четного v и.

С= — для нечетного v. Т. е.,.

4

Доказательство этих формул (см. [2]) проводится методом математической индукции по V/ и vj и существенно опирается на доказанные в лемме равенства (2.3.11).

Геометрическую реализацию двудольного графа с минимальным числом реберных пересечений, соответствующим равенствам (2.3.12), дает следующая конструкция [2]. Зафиксируем на плоскости некоторую прямоугольную декартову систему координат. Если v/=2r, возьмем на оси х точки с абсциссами.

а если v/=2r+7, то возьмем на оси х точки с абсциссами.

— г, — (г — 1),… ,-2, — 1,1, 2,… (г — 1), г, г + 1.

Если V2=2s, возьмем на оси у точки с ординатами а если v?=2s+7. то возьмем на оси v точки с ошшнатами.

aside class="viderzhka__img" itemscope itemtype="http://schema.org/ImageObject">

Рис. 99.

Точную оценку минимального количества реберных пересечений в полных двудольных графах общего вида дают выражения:

Полный двудольный граф, первая «доля» которого состоит из выбранных вершин на оси х, а вторая «доля» — из выбранных вершин на оси у, будет иметь R (v/, v2) реберных пересечений.

Ребрами этого графа являются прямолинейные отрезки. Пример подобной реализации для v_t=v₂=4 и Щ4,4)=4 представлен на рис. 99.

Подсчет числа реберных пересечений в полных двудольных графах связан с классической задачей об авариях на кирпичном заводе. На кирпичном заводе имеется v, печей для обжига кирпичей. После обжига кирпичи грузятся на специальную вагонетку и перевозятся к одной из V2 платформ, с которых их погружают на автотранспорт. Каждая печь должна быть связана рельсовым путем с каждой погрузочной платформой. Если рельсовые пути пересекаются, то это создает вероятность аварии. Для того, чтобы свести к минимуму вероятность аварий, требуется установить минимальное количество пересечений рельсовых путей. Ясно, что ответом к задаче является формула (2.3.12), а рассмотренная выше геометрическая реализация дает конкретный пример проекта расположения печей и погрузочных платформ.