Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 45
Текст из файла (страница 45)
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. Тогда в силу предположения индукции вектору б соответствует единственное плоское дерево А. Сопоставим вектору а плоское дерсво, изображенное на рис. 6.10, д. Код плоского корневого дерева можно получить также с помощью обхода; при обходе дерева, начиная с корня, мы проходим каждое ребро дважды (см. рис. 6.11, б).
Первый проход вдоль ребра отмечаем нулем, в б в Рис. 6.12 а второй единицей. В результате получаем тот же самый код дерева,что и при индуктивном способе построения. 3.1. Построить коды плоских корневых деревьев, изображенных на рис. 6.12. 3.2. Построить плоское корневое дерево по его коду сс 1)а = 0010100111; 2) Й = 00110101000111; 3)а = 0000010011011111; 4) П = 01001000110111; 5)а = 00100010110111, 6)а = 000101110100001011. 3.3. По вектору а установить, является ли он кодом какого-либо плоского дерева: 1) а = 001011; 2) а = 0110; 3) о = 001001; 4) а = 010011; 5) а = 001 11001; 6) а = 0001100111. 3.4. Множество векторов А разбить на классы так, чтобы каждый класс состоял из кодов попарно изоморфных плоских корневых деревьев: 1) А = (аз = 0100101101, Пз = 0101000111, оз = 0001110101, сц = 0101001011, оз = 0100011101); 2) А = (аз — — 0100010110111, оз = 000110011101, Оз = 001001011 101, Оч = 01001001011 1, ав = 01000110011 Ц; 3) А = (аз = 0011010011, Нз = 0100110011, оз = 0010110101, оя = 0100101101, оз = 0011001101).
222 Га. 17. Графы и сети 3.5. Доказать по индукции, что для всякого корневого дерева Р с лл, ребрами его код а = (ллл...а „) обладает свойствами 1 и 2, сформулированными в рассмотренном выше примере. 3.6. Показать, что для числа ф(и) попарно различных плоских корневых деревьев справедливы неравенства: Ц л)(п) ( 4', 2) ф(л) ( Сза, 3) ф(п) ( С"'( ' П . З.л. Ц Показать,что для числа ф(и) попарно различных плоских корневых деревьев справедливо рекуррентное соотношение ф(и) = ~~ ул(л — Ц лр(гл — л), лс(0) = лр(Ц = 1.
~=л 1 2') Доказать, что ф(п) = С,"„. ие 1 Яп' 3.8. 11оказать эквивалентность двух определений корневого дерева: Ц корневое дерево есть однополюсная сеть, граф которой связен и не имеет циклов; 2) корневое дерево есть сеть, которую можно получить с помолцью индуктивного построения, описанного выше (см. индуктивное определенив корневого дерева). 3.9. Опираясь на индуктивное определение корневого дерева, доказать следуклщие свойства корневых деревьев: Ц число вершин корневого дерева на единицу больше числа его ребер; 2) любая пара вершин корневого дерева соединена единственной цепью; 3) добавление любого ребра к корневому дереву приводит к появлению цикла.
3.10. Вершину корневого дерева будем называть висячей., если она отлична от корня и имеет степень, равную 1. Ц Пусть корневое дерево имеет й висячих вершин и не имеет вершин степени 2, отличных от корня. Доказать, что при и > 2 общее количество вершин не превосходит 2Й. 2) Пусть кажда» вершина корневщлл дерева, отличная от корня, имеет степень, нс превосходящую 3, а степень корня не превосходит 2. Доказать, что число висячих вершин не превосходит плл2, где п число вершин корневого дерева.
Напомним. что расстоянием между вершинами и и и связного графа С называется минимальное число рсл(и, и) ребер в цепи, соеди- няющей вершины и и и. Диаметрам связного графа С = ('л', Х) называется число Р(С) = шах ро(и, и). Пентлром связного грач,сЕХ фа С = (1л, Х) называется вершина ис такая, что шакро(ие и) = ш1пшахра(лл., и), ал Х акал ееи Ь'М. Яеревьл и сети 223 а величина Л(С) = п1ахра(ио, о) называется его радиусом. Цепь в юеи графе С назовем диаметральной, если она соединяет вершины и и о такие, что ро(и, и) = Р(С), и имеет длину, равную Р(С). 3.11. Найти количество центров г(Т), радиус ЙТ) и диаметр Р(Т) для каждого корневого дерева Т из тех, что изображены на рис.
6.12. 3.12. 1) Доказать, что радиус Л(С) и диаметр Р(С) графа С связаны неравенствами Л(С) < Р(С) < 2Л(С). 2) Показать, что обе оценки достижимы. з Р(С) 3) Доказать, что если С вЂ” дерево, то Л(С) = ) [. 2 4) Доказатзь что всякий центр дерева принадлежит каждой его диаметральной цепи. 5) Доказать, что дерево обладает единственным центром в случае, когда его диаметр --. число четное, и обладает двумя центрами, когда его диаметр число нечетное.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
