Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[30]

Задачи к главе 5

99

Упражнения

5.5-1 Нарисуйте все деревья (без выделенного корня), содержащие три вершины А, В и С. Нарисуйте все корневые деревья с вершинами А, В и С и корнем А. Нарисуйте все (корневые) деревья с порядком на детях с вершинами А, В и С и корнем А. Нарисуйте все двоичные деревья с вершинами А, В и С и корнем А.

5.5-2 Покажите, что для любого га 7 существует дерево с га вершинами, из которого можно получить га различных корневых деревьев, объявив корнем одну из га вершин.

5.5-3 Пусть G = (V, Е) - ориентированный ациклический граф, в котором существует вершина г>о, из которой в каждую другую v G V ведёт единственный путь. Покажите, что неориентированный вариант графа G является деревом.

5.5-4 Докажите по индукции, что в любом двоичном дереве число вершин степени 2 на единицу меньше числа листьев.

5.5-5 Покажите, что двоичное дерево с га вершинами имеет высоту не меньше [lg raj.

5.5-6* Определим внутреннюю сумму длин (internal path length) для двоичного дерева, в котором каждая вершина имеет степень О или 2, как сумму глубин всех внутренних вершин. Определим внешнюю сумму длин для этого же дерева как сумму глубин всех его листьев. Пусть га - число внутренних вершин такого дерева, г и е - внутренняя и внешняя суммы длин. Докажите, что е = г + 2га.

5.5-7* Определим «вес» листа в двоичном дереве как 2 d, где d - его глубина. Докажите, что сумма весов всех листьев в двоичном дереве не превосходит 1 (неравенство Крафта, Kraft inequality)

5.5-8* Покажите, что в любом двоичном дереве с L листьями можно найти поддерево, число листьев в котором находится на отрезке [L/3,2L/3J.

Задачи

5-1 Раскраска графа

Назовём /г-раскраской неориентированного графа (V, Е) функцию с: V -т- {0,1,..., к - 1}, для которого с(и) ф с[у) для любых двух смежных вершин и и v. (Концы любого ребра должны иметь разные цвета.)

а. Покажите, что любое дерево имеет 2-раскраску.


б.Покажите, что следующие свойства неориентированного графа G равносильны:

1.Граф G двудольный.

2.Граф G имеет 2-раскраску.

3.Граф G не имеет циклов нечётной длины.

в.Пусть d - максимальная степень вершин неориентированного графа G. Покажите, что G имеет (d + 1)-раскраску.

г.Покажите, что если граф G имеет 0(V) рёбер, то G имеет 0(-\/ Г")-раскраску.

5-2 Графы и люди

Переведите на язык неориентированных графов следующие утверждения и докажите их. (Предполагается, что отношение «быть другом» симметрично, и человек не включается в число своих друзей.)

а.В любой компании из га 2 человек найдутся два человека с одинаковым числом друзей (среди присутствующих).

б.В любой группе из 6 человек можно найти либо трёх человек, являющихся друзьями друг друга, либо трёх человек, никакие двое из которых не являются друзьями.

в.Любую компанию людей можно развести по двум комнатам так, что для каждого человека как минимум половина его друзей окажутся в другой комнате.

г.Если в компании из га человек у каждого не менее га/2 друзей, то эту компанию можно рассадить за круглым столом так, чтобы каждый сидел между двумя своими друзьями.

5-3 Разбиение деревьев на части

Многие алгоритмы на графах, действующие по принципу «разделяй и властвуй», делят граф на две части, при этом желательно удалять как можно меньше рёбер и получить две части по возможности близкого размера.

а.Покажите, что в любом двоичном дереве с га вершинами можно найти ребро, после удаления которого получатся две части размера не больше Зга/4 каждая.

б.Покажите, что константу 3/4 в пункте (а) нельзя улучшить, приведя пример двоичного дерева, для которого после удаления любого ребра в одной из частей остаётся не менее Зга/4 вершин.

в.Покажите, что множество вершин любого двоичного дерева с га вершинами можно разбить на две части А и В таким образом, что А\ = [п/2\, \В\ = [га/2], а число рёбер, соединяющих вершины из разных частей, есть О (lgra).


Замечания

Основатель символической логики Буль (G. Boole) ввёл многие из нынешних теоретико-множественных обозначений в книге, опубликованной в 1854 году. Современная теория множеств (прежде всего теория мощностей бесконечных множеств) была создана Кантором (С. Cantor) в 1874-1895 годах. Термин «функция» использовал Лейбниц (G.W. Leibnitz) в применении к некоторым математическим формулам. Определение функции впоследствии многократно обобщалось. Теория графов восходит к 1736 году, когда Эйлер (L. Euler) показал, что невозможно пройти по всем семи мостам города Кенигсберга по одному разу и вернуться в исходную точку.

Полезным справочником по определениям и результатам теории графов является книга Харари [94].



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]