Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 46
Текст из файла (страница 46)
11. Используя индукцию, докажите теорему 6.40, которая утверждает, что если у дерева Т имеется е ребер и и вершин, то и = е+ 1. 6.4. МГНОВЕННОЕ БЕЗУМИЕ В игру мгновенное безумие играют с помощью четырех кубиков, каждая из шести граней которых окрашена в один нз четырех цветов: красный, синий, зеленый или желтый (набор четырех цветов может быть произвольным). Цель игры— составить из кубиков столбик так, что каждая сторона столбика будет окрашена в один из четырех цветов. Решения (если они существуют) зависят от выбора цветов для граней кубика. Решение может быть одно, их может быть несколько, или решение может вообще не существовать. Обозначим грани кубика, показанные на "развертке" на рис. 6.48, как фронтальную (ф), заднюю (з), верхнюю (в), нижнюю (н), левую (л) и правую (п).
в пфп з Рис. 6.48 Части кубика, которые должны образовывать сторону столбика, назовем Левой, Правой, Фронтальной и Задней (чтобы отличать их от граней кубика, первоначально фигурирующих в головоломке). Таким образом, Фронтальная и Задняя, а также Левая и Правая части кубика — противоположны друг другу. Предположим, что для заданной игры имеются кубики, показанные на рис. 6.49.
з с к [к1 кжзк кжсз жкжж кжсз Риа 6.49 Теперь покажем относительно простой способ нахождения решения, основанный на использовании графов. Перед началом, однако, важно уяснить, что выбор противоположных граней кубика как Фронтальной и Задней никоим образом не определяет, какая другая пара граней может быть Левой и Правой, или какая сторона выбранной пары будет Левой, а какая — Правой. Возможно, в этом легче убедиться, если захватить кубик за противоположные стороны (Фронтальную и Заднюю) и вращать его. Как легко убедиться, четыре вращения реализуют все возможные, упомянутые выше ситуации для других двух сторон (Левой и 288 ГПАВА б.
Графы, ориентированные графы и деревья Правой). Таким образом, если Фронтальная и Задняя грани для каждого кубика определены, имеется полная свобода выбора пары противоположных граней как Левой и Правой, соответственно. Создаваемый нами граф имеет в качестве вершин четыре цвета. Ребра графа связывают цвета на противоположных гранях кубика. Для первого блока необходимо иметь по одному ребру с к Рис. 6,50 от зеленого к синему, от зеленого к красному и от красного к желтому, что изображено на рис.
6.50. Граф для совокупности четырех блоков показан на рис. 6.51. Рис. 6.51 Переупорядочение вершин на диаграмме зачастую позволяет привести граф к более аккуратному виду. Теперь построим подграф, чтобы иметь возможность выбрать фронтальную и заднюю грань для каждого кубика. Нам нужен такой подграф, что (1) каждая вершина графа является вершиной подграфа; (2) грань каждого кубика присутствует в подграфе; (3) порядок каждой вершины равен 2. Каждая вершина должна присутствовать, потому что все четыре цвета появляются на фронтальной и задней сторонах.
Ребро от каждого кубика должно присутствовать, чтобы мы получили фронтальную и заднюю сторону каждого кубика. Порядок каждой вершины равен двум, потому что каждый цвет появляется один раз на фронтальной поверхности и один раз — на Задней. Примеры возможных подграфов показаны на рис. 6.52. Рис.
6.52 (Попытайтесь найти и другие такие подграфы.) Итак, начинаем с испытания первого из показанных подграфов. Изображая его как ориентированный граф, образуюший цикл, можно рассматривать начальную вершину как фронтальную грань, а конечную грань — как заднюю. Таким образом, получаем таблицу РЯЗДЕЛ 6.4. Мгновенное оеэумие 299 Теперь нам нужен другой подграф с такими же свойствами. Единственное ограничение для второго подграфа — он не должен содержать ребра первого подграфа. Эти ребра уже были использованы как Фронтальные и Задние грани для блоков, поэтому не могут фигурировать как боковые.
Для упрошения графа удалим использованные ребра, после чего получаем рис. 6.54. По этому графу строим подграф, показанный на рис. 6.53, который можно использовать. Рис, б.БЗ Рис. 6.54 В результате получаем цвета для Левой и Правой частей, показанные в таблице, что и приводит нас к решению. Если граф, выбранный для Фронтальной и Задней частей, не дает результата, или желательно найти другое решение, то необходимо испытать другие варианты выбора Фронтальных и Задних частей. Для поиска иных вариантов полезным будет замечание о том, что такие подграфы должны иметь одну из базисных форм, показанных на рис.
6.55. О О Рис. б.бб 270 ГЛКГзд б, Графы, ориантороаанныа графы и оарааья ° УПРАЖНЕНИЯ 1. Найдите решение (если оно существует) для следующих наборов кубиков: а) с З К З КЖВС К КЗСКСЖКСКЗСК С ж З З 6) с в ж С кжксжксввжсзжзкк в З к ж в) ж З в к вжск скак ссвкквсс ж ж ж Ж г) ж З к и ккжккжкзкжсвзс савв в с в к д) кжсз жс зк жжвс кккж 6.5. ПУТИ И ЦИКЛЫ ЭЙЛЕРА ОПРЕДЕЛЕНИЕ 6.44. Пусть С = (Р;Е) — граф. Цикл, который включает все ребра и вершины графа С, называется айлеровым циклом. Если это условие выполняется, говорят, что граф С имеет эйлеров цикл.
Если теперь вернуться к задаче о кенигсбергских мостах, легко убедиться, что она сводится к попытке определить, содержит ли граф, изображающий задачу, эйлеров цикл. Для этой цели нам потребуется приведенная ниже теорема. Эта теорема справедлива также для мультиграфов и псевдографов, исключая тот случай, когда псевдограф имеет только одну вершину. Более того, доказательство теоремы остается тем же.
Для ясности будем использовать термин граф, понимая, что каждое утверждение справедливо для мультиграфов и псевдографов. ТЕОРЕМА 6.45. Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет четную степень. РАЗДЕЛ 6.5. Пути и иикпы Эйпара 271 ДОКАЗАТЕЛЬСТВО.
Предположим, что граф С имеет эйлеров цикл. Граф является связным, т.к. каждая вершина принадлежит циклу. Для всякой вершины и графа С каждый раз, когда эйлеров цикл проходит через и, он вносит 2 в степень и. Поэтому степень и четная. Обратно, нужно показать, что каждый связный граф, у которого степени вершин четные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию по числу вершин. Поскольку теорема тривиально справедлива при и < 3, начнем индукцию с и = 3. Предположим, что каждый связный граф, имеющий менее й вершин, и все вершины которого обладают четной степенью, содержит эйлеров цикл. Пусть С вЂ” связный граф, содержащий 7с вершин, степени которых четные. Допустим, что и1 и ьа — вершины графа С.
Поскольку граф С— связный, существует путь из и1 в из. Поскольку степень из — четная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в иы и эйлеров цикл С1 можно считать построенным. Если С1 является эйлеровым циклом для С, тогда доказательство закончено. Если нет, то пусть С' — подграф графа С, полученный удалением всех ребер, принадлежащих Сы Поскольку С1 содержит четное число ребер, инцидентных каждой вершине, каждая вершина подграфа С' имеет четную степень. Пусть е — ребро графа С', пусть С, — компонента графа С', содержащая е.
Поскольку С' имеет менее, чем й, вершин, и у каждой вершины графа С' четная степень, граф С' имеет эйлеров цикл. Пусть это Сз. Далее, у С1 и Сз имеется общая вершина, скажем, а. (Почему?) Теперь можно продолжить эйлеров цикл, начиная его в а, пройти Сы вернуться в а, затем пройти Сз и вернуться в а.
Если новый эйлеров цикл не является эйлеровым циклом для С, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для С. ПРИМЕР 6.46. Граф на рис. 6.56 имеет эйлеров цикл, поскольку степень каждой его вершины четная. П ПРИМЕР 6.47. Граф на рис. 6.57 не имеет эйлерова цикла, поскольку степени вершин иг и и4 — нечетные. П У Рис. 6.56 Рис. 6.57 Возвращаясь к задаче о кенигсбергских мостах, обнаруживаем, что муль- тиграф на рис. 6.58, построенный Эйлером для описания кенигсбергских мостов, 272 ГЛАВА б. Графы, ориентированные графы и деревья имеет нечетные степени всех его вершин.
Итак, этот мультиграф не имеет эйлерова цикла, поэтому невозможно пройти каждый мост по одному разу и вернуться в исходную точку пути. Необходимо также отметить, что хотя задача была решена с использованием мультиграфа, ее можно решить, используя простой граф. Когда имеется более одного Г Рис.
6.58 ребра между вершинами, нужно к исходному мультиграфу просто добавить вершину для представления середины каждого моста. Тогда получится простой граф, показанный на рис. 6.59, который также описывает задачу о кенигсбергских мостах. Рис. 6.59 Что касается кенигсбергских мостов, можно также задать вопрос: "Возможно ли не проходить каждый мост по одному разу и не возвращаться обязательно в исходную точку маршрута?". Это предположение приводит к следующему определению и теореме. ОПРЕДЕЛЕНИЕ 8.48. Пусть С = (Тг, Е) — граф.
Путь, который включает каждое ребро графа С только один раз называется эйлеровым лунгам. В этом случае говорят, что граф С имеет эйлеров путь. Теперь нас будет интересовать случай, когда эйлеров путь не является эйлеровым циклом. Такой путь будем называть собственным эйлеровым путем. Предоставляем читателю доказать следуюшую теорему. ТЕОРЕМА 8.49. Граф (мультиграф или псевдограф) имеет собственный эйлеров путь тогда и только тогда, когда он связный и ровно две его вершины имеют нечетную степень. Поскольку граф для кенигсбергских мостов имеет четыре вершины с нечетными степенями, можно сделать вывод о невозможности пройти каждый мост по одному разу, даже если не нужно возвращаться в исходную точку маршрута.
ПРИМЕР 8.50. Граф на рис. 6.60 имеет собственный эйлеров путь, т,к, ровно две его вершины имеют нечетную степень. П ПРИМЕР 8.51. Граф на рис. 6.61 не имеет собственного эйлерова пути, т.к. четыре его вершины имеют нечетную степень. П РАЗДЕЛ б.б. Пути и циклы Эйлера 273 Ь с Рис. 6.61 Рис. 6.60 ОПРЕДЕЛЕНИЕ 6.52. Пусть С = ($;Е) — ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту же вершину без повторения ребер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
