Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 44
Текст из файла (страница 44)
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) Доказать, что дерево обладает единственным центром в случае, когда его диаметр --.
число четное, и обладает двумя центрами, когда его диаметр число нечетное. 3.13. Показать, что в дереве с нечетным диаметром любые две простые цепи наибольшей длины имеют хотя бы одно общее ребро. 3.14. Доказать, что дерево (некорневое) однозначно с точностью до изоморфизма восстанавливается, если заданы все попарные расстояния между его висячими вершинами. Подграф Н связного графа С называется остовным деревом графа С, если Н дерево, содержащее все вершины графа Н. 3.15. 1) Для каждого Н ) 2 указать граф, диаметр которого равен д, а любой связный остовный подграф имеет диаметр, равный 2д. 2) Доказатгь что в любом связном графе С существует остовное дерево, диаметр которого не более чем в два раза превосходит диаметр графа. 2. Двухполюсные сети.
Двухполюсная сеть Г = (~а, Ь), С) будет обозначаться кратко чероз Г(а, Ь). Подграфом сети Г будем называть произвольный подграф графа С. Пусть С подграф сети Г(а, Ь), содержащий хотя бы одно ребро. Тогда вершина подграфа С называется граничной, если она либо является полюсом, либо инцидентна некоторому ребру сети, не принадлежащему подграфу С. Подграф сети называется опьростком, осли он обладает единственной граничной вершиной. Подсетью двухполюсной сети называется ее подграф, имеющий ровно две граничные вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
