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

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

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

Нам достаточно рассмотреть случай п≥5, так как очевидно, что для

п<5 In =0. Для того чтобы получить верхнюю границу Mn для In , рассмотрим следующее специфическое изображение Gn на плоскости, которое бу­дем называть чередующейся «линейной моделью». Выберем горизонтальный отрезок S на плоскости и разде­лим S на п—1 отрезков точками р1, ...., рп, которые со­ответствуют (слеза напразо) вершинам графа Gn. Сое­диним p1 с p3, p4, p 5, …, рп полуокружностями, лежащими выше S. Затем соединим р2 с p4, p5, .... рп полуокружности, лежащими ниже S. В общем случае, соединим рi с pi+2, pi+3, .... рп для i=1, 2, ..., п-2 при помощи полуокружностей, лежащих выше (ниже) S, если i— нечетное (четное).

Подобное построение зыполнено для п=6 и п = 7 на рис. 5.16.

Рис. 5.16.

Заметим, что число пересечений ребер рав­но 4 для G6 и 11 для G7. В общем случае, если Мп оз­начает число пересечений ребер в некоторой линейной модели графа Gn, то можно показать (предлагаем сде­лать это в качестве упражнения), что

Таким образом, полученное выше значение Мп явля­ется оценкой сверху для In. Показано, что не­сколько лучшая, оценка сверху Мn для In дается следу­ющими выражениями:

Заметим, что для п четных M′n=3/4Mn. Для п нечетных, М′п составляет 3/4Mn относительно коэффициентов при п4 и п3.

Предыдущий результат можно также получить, на­пример, для случая четного п путем выделения r—п/2 пар и образования всех полных графов G4 между пара­ми. Каждый такой граф G4 изображается без пересече­ний ребер. Тогда можно показать, что имеется, по край­ней мере, пеpесечений. Положив r=п/2, по­лучим прежний результат для М′п.

Если существует представление графа Gn с мини­мальным числом пересечений такое, что оно содержит представление с минимальным числом пересечений гра­фа Gn-k для каждого четного k<n (достаточно для k=2, 4, 6), то можно показать по индукции, что оценка М′п, определенная выше, совпадает с In.

Значения М′6 и М′7 равны 3 и 9 соответственно. Сплошные линии на рис. 5.17 показывают представление G6, которое реализует М′6 .

Рис. 5.17.

Добавив пунктирные линии, мы получим представление G7, которое реализует М′7.

Упражнения

10. Нарисуйте графы, сравнимые с графом рис. 5.17 для п = 8, 9.

11. Используйте два концентрических многоугольника с одина­ковым числом вершии для построения графа с минимальным числом пересечений при п= 10. Соедините вершины внешнего многоугольника симметрично во внешней области, вершины внутреннего многоуголь­ника — прямыми линиями во внутренней области и вершины двух многоугольников — симметрично в промежуточной области. Обобщите этот метод.

ГОЛОВОЛОМКИ И ИГРЫ

5.8. Задача соединения раскрашенных кубов

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

Пусть C1, C2, С3, С4 обозначают четыре одинаковые куба, и пусть Y, R, В и С обозначают цвета: желтый, красный, синий и зеленый соответственно. Предполо­жим, что каждая грань каждого куба окрашена одним из этих цветов таким образом, что каждый цвет имеется на каждом кубе (в остальном цвета назначаются гра­ням куба независимо). Рассмотрим следующую задачу: при заданной раскраске кубов поставить кубы друг на друга (образуя призму с квадратным основанием) так, чтобы четыре квадрата на каждой боковой стороне призмы имели различные цвета.

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

Для любой раскраски кубов определим следующий граф, имеющий 4 вершины и 12 ребер. Вершины соот­ветствуют цветам Y, R, В и G. Для каждого куба С, су­ществуют три ребра, обозначенные числом i. Эти ребра соответствуют трем парам противоположных граней и соединяют соответствующие вершины (цвета). Раскраска кубов иллюстрируется рис. 5.18 (заметим, что петля соответствует окраске противоположных граней в один цвет).

Pис. 5.18

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

С другой стороны, можно показать, что если граф задачи имеет два пографа без общих ребер с отмечен­ными свойствами, то решение задачи существует. На рис. 5.19 показаны два определенных выше подграфа для графа рис.5.18.

Рнс. 5.19.

Упражнение 12. Зафиксируйте положение призмы. Обозначьте переднюю грань, правую грань и верхнюю грань каждого куба x, у и z, а соответствующие противоположные стороны х', у' и z'. Исполь­зуя подграфы рис. 8.19, определите цвет каждой грани каждого куба.

Замечание. Заметим, что имеется 41 472 возмож­ных расположений кубов. Самый нижний куб имеет 3 возможных положения (3 существенно различных спосо­ба его расположения на столе). Каждый из остальных кубов имеет 24 возможных ориентации: 6 возможностей для выбора грани, на которой он стоит, и затем 4 воз­можных поворота.

5.9. Задачи изменения состояний системы

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

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

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

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

Для решения этой задачи рассмотрим в качестве си­стемы множество миссионеров и людоедов на берегу А. Пусть М, С и К обозначают миссионера, людоеда и умеющего грести людоеда соответственно. Тогда систе­ма имеет 24 возможности состояния (так как числа М, С и К находящихся на берегу А могут принимать соот­ветственно 4, 3 и 2 различных значения). Из них допу­стимыми являются следующие 16: