Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 44
Текст из файла (страница 44)
Пля хроматического индекса мультиграфа С = ()г, Х) имеют место следующие оценки: 1) у'(С) > Ь(С), где Ь(С) = шахд(е); 2) Х'(С) < [ — Ь(С)! (теорема К. Шеннона); 3) Х'(С) < Ь(С) + д(С), где д(С) = шах д(е, ш) и д(е, ш) от«) число ребер, соединяющих в С вершины е и ю, т. е. д(С) мощность наибольшей из совокупностей кратных ребер в мультиграфе С; эта оценка получена В.Г. Визингом.
Если С граф (без петель и кратных ребер), то Ь(С) < Х'(С) < < Ь(С) + 1. 2.1. Применяя критерий Понтрягина — Куратоижого, выяснить, планарны ли графы, изображенные; 1) на рис. 6.5, а, б; 2) на рис. 6.6, а, б, в. 218 Га. $1 Графы и сети 2.9. Какое наибольшее число граней может быть у плоского 5-вершинного графа, не имеющего петель и кратных ребер? Изобразите такой граф. 2.10. 1) Существует ли плоский 6-вершинный граф (без петель и кратных ребер), у которого 9 граней? 2) Построить все попарно неизоморфные плоские 6-вершинные графы (без петель и кратных ребер), имеющие 8 граней.
2.11. Графы Сз и Сз плоские, б-вершинные, с одинаковым числом граней. У графа Сз четыре вершины степени 4 и две вершины степени 3. У графа Сз две вершины степени 5, а остальные имеют степени меньше 5. Какие степени могут быть у остальных вершин графа Сз? Изобразите все такие графы С1 и Сз. 2.12. Доказать, что в каждом планарном графе без потель и кратных ребер есть вершина степени, не большей чем 5. 2.13.
Плоский связный граф без висячих вершин, каждая грань которого, включая и внешнюю, ограничена циклом длины 3, называется шрианеуляаией. Показать, что триангуляция с п > 3 вершинами имеет Зп — 6 ребер и 2п — 4 граней. 2.14. Доказать, что если у связного планарного графа (без петель и кратных ребер), имеющего и вершин и т ребер, каждый простой цикл содержит не менее й ребер (й > 3), то т < й(п — 2)/(й — 2). 2.15. Доказать, что в любом планарном графе (без петель и кратных ребер), имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше 5.
2.16. Показать, что 6-связных планарных графов (без петель и кратных ребер) не существует. 2.17. 1) Показать, что плоский кубический граф, граница каждой грани которого имеет не менее 5 вершин, содержит по крайней мере 20 вершин. Привести пример такого графа. 2) Пусть С -" плоский связный кубический граф (без петель и кратных ребер). Через у, (г > 3) обозначим число тех граней графа.
С, каждая из которых ограничена 1 ребрами. Доказать, что ~ ~(6 — г)1, = 12. е>з 2.18. Найти хроматические числа и хроматические индексы графов, изображенных на рис. 6.1, рис. 6.3, рис. 6.5 и рис. 6.6. 2.19. Найти хроматическое число и хроматический индекс графа С; 1) С = В" (и > 1); 2) С = К„ (и > 2); 3) С = К „ (и > т > 1). 2.20. Граф (без петоль и кратных ребор) называется еамильтлоновым, осли в нем существует простой остовный цикл (т.е. простой цикл, содержащий все вершины графа).
Такой цикл называют еамильтоноеььи. Доказать, что если С вЂ” кубический гамильтонов граф, то 1'(С) = 3. 2.21. Пусть | длина самой длинной простой цепи в графе С, не имеющем петель и кратных ребер. Показать, что Х(С) < 1+ 1. 219 1'М. Яеревьл и сетпи 2.22. Пусть С граф без петель и кратных ребер и Ь(С) наибольшая из степеней его вершин. Показать, что г(С) < Ь(С) + 1. 2.23. Показать, что вершины всякого плоского графа (без петель и кратных ребер) можно правильно окрасить в о < 6 цветов.
2.24. Показать, что для правильной раскраски ребер всякого кубического мультиграфа достаточно 4 цветов. 2 3. Деревья и сети 1. Корневые деревья. Пусть С = ($; Е) граф с множеством вершин И и множеством ребер Е и Иг С И некоторое подмножество вершин. Пару Г = (И", С) будем называть сетью. Ребра и вершины графа С называются ребрами и вершинами сети Г = (С, И').
Элементы множества И' называются полюсами. Сеть называется й-полюсной, если ~И'~ = Ь. Сеть Г = (С., И') является связной (планарной), если связным (планарным) является граф С. Лвс Ь-полюсные сети изоморфны, если их графы изоморфны и при этом полюса одной сети взаимно однозначно соответствуют полюсам другой. Корневым деревом (деревом, с корнем) называется однополюсная сеть, граф которой является деревом. Корневое дерево можно определить также по индукции.
Базис индукции. Однополюсная сеть с одним ребром является корневым деревом (рис. 6.10, а). Индуктивный переход. Пусть А (рис. 6 10, й) . -дерево с корнем а и В (рис. 6.10, в) дерево с корнем Ь. Тогда сеть С (рис. 6.10, г), ~11Ъ~ й в г Рис. 6.10 полученная отождествлением полюсов а и Ь, является деревом с корнем с = а = Ь.
Палее, деревом является сеть Р (рнс. 6.10, д), полученная добавлением нового ребра (а, с), где с не является вершиной сети А, и выбором вершины с в качестве нового корня. Укладкой корневого дерева или плоским корневым деревом называется изображение дерева на плоскости. Укладку корневого дерева можно провести в соответствии с процедурой индуктивного построения корневого дерева.
При этом мы будем считать, что корневое дерево укладывается на плоскости с разрезом, представляющим собой полупрямукд исходящую из корня. Ребра укладки дерева, инцидентные корню, можно пронумеровать по часовой стрелке числами 1, ..., т, где т — степень корня. Такая нумерация является однозначной в 220 Гж 17. Графы и сети случае расположения укладки на плоскости с разрезом. Если из плоской укладки удалить ребро, инцидентное корню и имеющее номер т', 1 < з < щ, то образуются две компоненты связности. Ту из компонент, которая не содержит корня, назовем 1-й ветвью укладки дерева.
Будем рассматривать ветвь как плоское корневое дерево с корнем в вершине, инцидентной 1-му ребру (в исходном дереве). Если ветвь но содержит ребер, то будем называть ее пустой. Два плоских корневых дерева А и В будем называть одинаковыми, если; 1) А и В однореберные деревья; 2) А и В плоские корневые деревья с более чем одним ребром и равными степенями корней и такие, что г,-е ветви деревьев А и В, имеющие один и тот же номер, либо пусты, либо являются одинаковыми плоскими корневыми деревьями.
Деревья, не являющиеся одинаковыми, называются различными. Каждому плоскому корневому дереву с т ребрами можно взаимно однозначно сопоставить двоичный вектор длины 2пз, называемый ког)ом дерева. Код плоского корневого дерева определим по индукции. Базис индукции. Дереву с одним ребром (см. рис. 6.10, а) сопоставим вектор 01. Индуктивный переход. Если дереву А (см. рис 6.10, б) сопоставлен вектор а, а дереву В (см, рис, 6.10, в) — вектор В, то дереву С (см. рис, 6.10, г) сопоставляется вектор а11, а дереву Р (см. рис.
6.10, д) сопоставлен вектор Оа1. Пример. Дереву, изображенному на рис. 6.11, а, сопоставляется вектор 001001010111. Отметим, что код дерева с т. ребрами является двоичным вектором, обладающим следующими двумя свойствами. 1. Число нулей в векторе а совпадает с числом единиц. 2. Для любого Й < 2щ числоединиц среди первых Й координат набора а не превосходит числа нулей среди тех же й координат.
и б Восстановить дерево по коду Рис. 6.11 можно следующим образом. Базис индукции. Вектору 01 сопоставляем дерево с одним ребром (см. рис. 6АО, а). Такое плоское дерево единственно, поскольку все однореберные плоские корневые деревья одинаковы. Индуктивный переход. Пусть дан вектор а с 2ш координатами (пз ) 1), обладающий свойствами 1 и 2. Пусть к — наименыпее четное число такое,что вектор ~3, состояьций из первых Й координат набора о, удовлетворяет свойству 1. Если й < 2т, рассмотрим еще вектор 7, составленный из координат аьчг,...,а„ набора а. Тогда, поскольку плоские корневые деревья А и В, кодами которых являются 221 )'у.
яеревья в сепш соответственно наборы Д и у, определены однозначно в силу предположения индукции, то можно однозначно сопоставить вектору о дерево., показанное на рис. 6.10, г. Если же к = 2т, то пусть б -- вектор, полученный из а отбрасыванием первой и последней координат. Нетрудно убедиться,. что вектор 6 также обладает свойствами 1, 2. Тогда в силу предположения индукции вектору б соответствует единственное плоское дерево А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
