ФPAГMEHTЫ УЧЕБНИКА (...)
Плоские графы
Рассказ о задаче, в которой требовалось выяснить, можно ли вычертить печатную схему для данного набора вершин, был нами не закончен. Задача была только поставлена.
Рассмотрим несколько теоретических положений, необходимых для полного ее решения.
Определение 4. Плоским называется граф G, который можно нарисовать на плоскости так, что никакие два его ребра не имеют других общих точек, кроме их общей вершины.
Например, всякое дерево есть плоский граф;
граф, содержащий цикл, из вершин которого выходят деревья (рис. 88), является плоским.
На рисунке 89 изображен один и тот же плоский граф. (Рисунок справа показывает: слева изображен действительно плоский граф, поскольку его удалось нарисовать на плоскости так, что ни одна пара ребер не пересекается).
Еще один аналогичный пример показан на рисунке 90. (Рисунки справа называются плоскими изображениями плоского графа).
Определение 4.1. Гранью в плоском изображении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Например, на рисунке 91 изображен граф с семью гранями; на рисунке 92 представлены графы, у первого из которых заштрихованная область не является гранью, а незаштрихованная является; на втором рисунке 92 изображена грань (внутри дерево).
Иногда полезно рассматривать и бесконечные грани — то есть часть плоскости, расположенную вне плоского изображения графа. Пример показан на рисунке 93 (заштрихована бесконечная грань, которая уже не может содержать других циклов).
Остановимся на двух графах, которые в ряде вопросов играют особенно важную роль. Речь идет о полном графе с пятью вершинами и о графе, который требовалось начертить в задаче о печатной схеме (три точки А, В и С соединились с тремя другими на этой же схеме). Рисунок 94 напоминает этот граф. При разборе задачи было показано, что этот граф не является плоским.
Теорема 4.1. Полный граф с пятью вершинами не является плоским.
Для доказательства воспользуемся формулой Эйлера: (...)
3. Составить схему автомата-отгадчика. Для угадывания предлагается 15 фамилий, размещенных в четырех столбцах. (Это одновременно задание на конструирование дешифратора у которого 4 входа и 15 выходов).
4. На рисунке 96 изображена функциональная схема устройства. Выяснить, какую работу выполняет устройство.
5. Утверждается, что устройство, схема которого изображена на рисунке 97, осуществляет сложение двух-разрядных целых чисел (т. е. чисел положительных и отрицательных). Так ли это?
6. Известно, что вместо трех различных логических элементов «И», «ИЛИ», «НЕ» можно использовать один комплексный элемент, так называемый «штрих Шеффера». Обозначается он так, как показано на рисунке 98, и выполняет со значениями А и В операцию АВ — «отрицание произведения», то есть работает в соответствии с таблицей 24:
Составьте, пользуясь только элементами «штрих Шеффера», устройство, эквивалентные элементам «И», «ИЛИ», и «НЕ». Этим будет доказано, что он один заменяет их все.
8. Коммивояжер из пункта А отправляется в поездку и намерен, посетив по одному разу пункты Б, С и D, вернуться в А. Схема расположения пунктом задана неориентированным графом (рис. 99).
Утверждается, что ему безразлично в каком порядке объезжать эти пункты. Так ли это? Почему?
9. В розыгрыше футбольного кубка участвует 11 команд. Система соревнований — «олимпийская»: проигравшая один матч команда выбывает из дальнейших соревнований.
Составить расписание игр в виде граф-дерева так, чтобы после первого тура остались команды, которые за три тура определят победителя.
Какой вид будет иметь граф-расписание матчей?
Сколько матчей будет проведено с начала розыгрыша кубка?
10. Требуется обойти «ходом коня» все 12 клеток доски, изображенной на рисунке 100, причем в каждой клетке побывать по одному разу. Начинать и завершать обход можно на любой клетке, но обязательно на одной и той же.
11. Дана часть шахматной доски (рис. 101). На верхних угловых полях расположено по одному черному коню, на нижних — по одному белому.
Каким образом и за сколько ходов их можно поменять местами?
Дан граф (рис. 102). Положите шашку на любую из вершин графа и затем сдвиньте ее на любую из соседних. После того как ход закончен, прикасаться к этой шашке уже нельзя. Затем следует положить вторую шашку на любую еще не занятую вершину графа и вновь передвинуть ее в любую из соседних незанятых вершин.
Так следует действовать до тех пор, пока все семь имеющихся к началу игры шашек не займут своего места в вершинах графа.
В чем секрет успеха?
13. Четыре человека взялись выполнять работу маляра, слесаря, кузнеца и штукатура — каждый будет делать что-то одно.
Выяснилось, что:
Андреев не будет маляром и не будет слесарем;
Владимиров не будет кузнецом и не будет маляром;
Сергеев не будет слесарем и не будет маляром;
Дмитриев не будет слесарем и не будет кузнецом.
Известно также, что если Андреев не будет кузнецом, то Дмитриев не будет маляром.
Кто какую работу выполнял, если эти условия были выполнены? Задачу решить графически, составить граф-дерево.
|
