XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 48
Текст из файла (страница 48)
ДЕйСтВИтЕЛЬНО, ПУСТЬ ВЕРШИНа 7Ьа ПРИНаДЛЕжИт КОМПОНЕНТЕ Ср вместе с вершинами е; и е7. Тогда либо вершина еп1 достижима из вершины е;, либо, наоборот, ю; достижима из о„„и, следовательно, е,в Е К;. Иэ аналогичных рассуждений вытекает, что о,„Е К7. Таким образом, вершина о,„принадлежит пересечению множеств К; и К .
Пусть теперь вершины и; и е принадлежат компоненте С~ и 7ьа Е К,ПК . ТогДа веРшина е,„также пРинаДлежит компоненте Сю поскольку либо вершина иб достижима из о,в, либо е„, Достижима из еб, и Дла веРшин ку и 7ьв ситУаЦиЯ аналогична. Начнем строить компоненты, содержащие вершину еп Рассмотрим множество К1. Так как вершина е2 принадлежит множеству К7, найдется по крайней мере одна компонента, в которую входят обе эти вершины.
Обозначим ее через С7. Вершина оз будет принадлежать этой компоненте в том и только в том случае, если еэ Е К7 ОК2. Непосредственная проверка показывает, что последнее условие выполняется. 297 З.З. деревьв Можно заметить, что КтпКзйКзйК4ПКз Кь поэтому компонента Ст (см. рис. 5.9) есть подграф, порожденный множеством Кь и вершина от не может входить в какую-либо другую компоненту, отличную от Сь Поскольку в компоненту Ст вошли все вершины из множеств Кз и Кз, то вершины оз и оз также не входят ни в какие другие компоненты.
Перейдем к поиску компонент, отличных от Сь в которые входит вершина ое. В множестве Ке содержится вершина оз. Пересечению множеств К4 и Кз принадлежат вершины ов и ет, не вошедшие в выделенную компоненту Сь Рассуждая аналогично и учитывая, что о4 и оз принадлежат бикомпоненте Вз, а ов и от — бикомпоненте В4, получаем, что компонента Сз порождается множеством вершин К4ПКзПКвПКт =Кт, и других компонент в рассматриваемом ориентированном гра- фе нет. 5.3. Деревья Определение 5.5.
Неориентпированным деревом называют свлзный и ацинлический неориентпированный граф. Определение 5.6. Ориентпированным деревом называют бесконтурный ориентированный граф, у которого полустпепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентпированного дерева, полустпепень захода которой равна О. Опираясь на данное определение, можно доказать, что в ориентированном дереве любая вершина достижима нз корня. 298 3.
ТЕОРИЯ ГРАФОВ Отметим, что из определения 5.5 не- "1 4 льзя убрать требование бесконтурности ориентированного графа, поскольку бесконтурность не вытекает из других условий. Например, на рис. 5.18 изображен ориентированный граф, не нвлнющийсн Рис. 3.13 ориентированным деревом, хотя полу- степени захода всех вершин не больше 1 и ровно одна вершина имеет полустепень захода, равную О. Определение 5.Т. Вершину е ориентированного дерева называют попьомком (подликкым попьомком) вершины и, если существует путь из и в е (путь ненулевой длины иэ и в е).
В этом же случае вершину и называют предком (подлинным предком) вершины е, а если длина пути из и в е равна 1, то вершину е называют смком вершины и, которал при этом вполне естественно именуется опщом вершины е. Вершину, не имеющую потомков, называют листком. На рис. 5.14 вершины е4 и еа есть сыновья вершины ез, которве, в свою очередь, является сыном вершины се — корня дерева. Вершины о4 и ез явллются подлинными потомками вершин вень 3 вень 3 вень 0 Рис. 6.14 299 5.3. Деревья оо и ез, которые соответственно будут вх подлинными предками.
Вершины еь е4, еь ее, ее, ев — листья дерева. Взаимно недостижимые вершины ориентированного дерева (например, такие, как эз и эз) не являются ни предком, ни потомком одна другой. Каждая вершина будет сама для себя предком и потомком, но не подлинным. Определение 5.8, Произволъный ациклический граф называют неорненгпнрованным лесом. Если каждая слабая коззпоненша ориентированного графа является ориентированным деревом, то такой граф называют орнениизрованным лесом.
На рис. 5.15, а даны примеры неориентированного леса, а на рис. 5.15, б — примеры орентированного леса. г'г оз огз о Фз "гз "гз ггз оо "гз "гз Рис. 6.1б Зро 5. ТЕОРИЯ ГРАФОВ Определение ~.9. Подграф неориентированного (ориентированного) дерева, являющийся неориентированным (ориентированным) деревом, называют поддеревом исходного дерева. Иэ определения следует, что неориентированный леев это неориентированный граф, каждая компонента которого является неориентированным деревом. На рис.
5.14 подграф, порожденный множеством вершин (ез, ив, ст, ов, ов1, является поддеревом изображенного на рисунке ориентированного дерева. Определение 5.10. Ориентированное дерево, у которого каждая вершина, отличнал от корня, есть лист, называют нрстом. На рис. 5.13 граф, изображенный слева, является кустом. Рассмотрим теперь некоторые числовые параметры, которыми характеризуется ориентированное дерево. Определение 5.11. Высота ориентированного дерева — это наибольшая длина пути из корня в лист; глубина й(о) вершины ориентированного дерева о — это длина пути иэ корня в эту вершину; высота Й(о) вершины ориентированного дерева о — это наибольшая длина пути из данной вершины в лист и, наконец, вровень вершины ориентированного дерева — это разность между высотой ориентированного дерева и глубиной данной вершины. Уровень корня равен высоте ориентированного дерева, но уровни различных листьев, так же как и их глубины, могут быть различными; высота любого листа равна нулю (см.
рис. 5.14). Определение 5.12. Ориентированное дерево называют бинарным, если полустепень исхода любой его вершины не больше 2; бинарное ориентированное дерево называют пол«ым, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а уровни всех листьев совпадают. Примеры различных бинарных ориентированных деревьев приведены на рис. 5.16: ориентированные деревья на рис. 5.16, а и б неполные, а ориентированное дерево на рис. 5.16, е полное.
В~ Эд ею "з Ф~ Э~ Од а б е Рие. 5.16 Используя индукцию по высоте ориентированного дерева, можно показать, что в полном бинарном ориентированном дереве высоты Ь ровно 2" листьев. Действительно, ориентированное дерево высоты 0 имеет 2е = 1 лист. Полное бинарное ориентированное дерево высоты 1 имеет 2~ = 2 листа. Пусть полное бинарное ориентированное дерево имеет высоту й и соответственно 2~ листьев. Рассмотрим полное бинарное ориентированное дерево высоты й+ 1. Поскольку в полном бинарном ориентированном дереве уровни всех листьев совпадают, легко видеть, что ориентированное дерево высоты й+ 1 можно получить из полного бинарного ориентированного дерева высоты й, если из каждого листа последнего провести по две дуги.
Тогда количество листьев в ориентированном дереве высоты й+ 1 будет в 2 раза больше, чем в ориентированном дереве высоты й, т.е. 2" 2 = 2"+~. Отсюда следует, что в произвольном бинарном дереве высоты Ь не более 2л листьев. Таким образом, мы получаем следующий простой, но важный результат. 302 5. ТЕОРИЯ ГРАФОВ Теорема 5.2 (теорема о высоте бинарного ориентированного дерева с заданным числом листьев). Бинарное ориентированное дерево с и листьями имеет высоту, не меньшую 1ояз и.
Эта теорема имеет одно весьма интересное приложение. Предположим, что необходимо расположить строго по возрастанию элементы конечного линейно упорядоченного множестива (а1, ..., а ). Эту задачу называют эадачей соргивровкв, а любой алгоритм, ее решающий, — аяеоритмол4 сортировки. С математической точки зрения алгоритм сортировки должен найти такую перестановку (а;„..., а;„) элементов множества, которая была бы согласована с заданным на нем отношением < линейного порядка, т.е.
для любых Й, 1 из справедливости неравенства 1ь < ц должно следовать сн < а;,. Первоначально сортируемые элементы могут быть расположены в произвольном порядке, т.е. исходной может быть любал перестановка элементов сортируемого множества, и мы не имеем никакой априорной информации об этой перестановке. Единственный способ получить такую информацию— проводить попарные сравнения элементов а; (относительно рассматриваемого линейного порядка) в какой-либо последовательности.
Заметим, что при этом совершенно не обязательно проводить все возможные сравнения, т.е. сравнивать а; с а для всех 1 ф у. Например, можно использовать транзитивность отношения порядка. Все сравнения, которые в принципе могут быть проведены в процессе работы некоторого алгоритма, изображаются наглядно в виде ориентированного дерева, называемого деревом решеивй. На рис. 5.17 приведено дерево решений для трехэлементного множества (а, Ь, с).
Вершины ориентированного дерева, не являющиеся листьями, помечены проверяемыми неравенствами, а множество листьев находится во взаимно одвоэначиом соотиветсшвин с множеством всех перестановок исходного множества. зоз 5.3. Деревья а< а<с<Ь с<а<Ь Ь<с<а с<Ь<а Рис. б.17 Поскольку в результате сортировки может получиться любая перестановка исходного множества и каждой такой перестановке соответствует лист дерева решений, в общем случае количество листьев будет равно и! — количеству перестановок и-элементного множества. Следовательно, сортируя входную последовательность, алгоритм обшательно пройдет какой-то путь от корня дерева решенийкодномукэлистьев,и,такимобразом, числоопераций сравнения ( шсло шагов алгоритма сортировки) будет величиной, пропорциональной высоте дерева решений, не меньшей чем 1обэ и!, в силУ теоРемы 5.2. Используя для оценки факториэла при больших п формулу Сщирлинга и! и ~/2яи (-) получаем, что дерево решений имеет высоту порядка п 1оаг и.
Таким образом, в общем случае задачу сортировки с помощью попарных сравнений нельзя решить быстрее, чем за указанное число шагов. Безусловно, конкретный путь в дереве решений из корня к одному нз листов зависит от исходной перестановки. Например, в дереве решений, приведенном на 304 5. ТЕОРИЯ ГРАФОВ рис. 5.17, есть два „коротких" пути длины 2, однако остальные пути имеют длину 3. Заметим, что в общем случае ориентированное дерево— зто не связный ориентированный граф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
