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

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

Подобные же исследования можно провести [35], [45], [80] для -вершинного обобщения другого основного графа Понтрягина — Куратовского, полного графа из пяти вершин. Приведем основные результаты [80].

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

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

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

Подобное построение выполнено для на рис. 6.16. Заметим, что число пересечений ребер равно 4 для и 11 для

Рис. 6.16.

В общем случае, если означает число пересечений ребер в некоторой линейной модели графа то можно показать (предлагаем сделать это в качестве упражнения), что

Таким образом, полученное выше значение является оценкой сверху для В [80] показано, что несколько лучшая, оценка сверху для дается следующими выражениями:

Заметим, что для четных Для нечетных, составляет относительно коэффициентов при

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

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

Значения равны 3 и 9 соответственно. Сплошные линии на рис. 6.17 показывают представление которое реализует

Рис. 6.17.

Добавив пунктирные линии, мы получим представление которое реализует Полезно попробовать найти прямолинейные конструкции для всех

Упражнения

(см. скан)

(см. скан)