Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 45
Текст из файла (страница 45)
Предположим, что С не является деревом. Тогда либо С не является связным, либо содержит цикл. Если граф С не связный, то существуют вершины а, Ь 6 С, для которых не существует пути из а в Ь. В таком случае, очевидно, не существует и единственного пути из а в Ь. Если С содержит цикл еоогозезе4 .
еь гею то как еэоз юь-зпьоо так и езогоо являются путями из ез в ео. Положив а = пз и 6 = ео, видим, что путь между вершинами а и Ь не является единственным. 262 ГЛАВА б. Графы, ориантироаанныа графы и деревья Предположим, что дерево представляет собой физический объект, подвижный в вершинах, и подвесим дерево за одну из его вершин так, что остальная его часть повиснет ниже этой вершины. Например, пусть задано дерево на рис. 6.39. г Рис. 6,39 Если подвесить его за вершину из, получим дерево, представленное на рис. 6.40. Если подвесим дерево за вершину и4, оно будет выглядеть так, как показано на рис.
6.41. "г г гг Рис. 6.40 Рис. 6.44 Вершина в самой верхней части каждого из изображений называется корнем дерева. Если корень дерева определен, дерево называется корневым деревом. При необходимости можно заменить корневое дерево Т на ориентированное Т', при этом дерево на рис. 6.42 будет заменено деревом на рис. 6.43. гг Рис. 6.4З Рис.
6.42 Такое дерево называется корневым ориентированным деревом, Т' лорожденны.н корневым деревом Т. При этом следует помнить, что это дерево отличается от неориентированного дерева и что вид ориентированного дерева зависит от выбора корня. Если корень выбран, уровень вершины и определяется длиной единственного пути из корня в вершину в. Высотой дерева называется длина самого длинного пути от корня дерева до листа. Если рассматривается корневое ориентированное дерево Т', порожденное данным корневым деревом Т, тогда вершина и называется родителем вершины и, а ю называется сыном вершины и, если существует РАЗДЕЛ В.З.
Деревья 263 ориентированное ребро из и в и. Если и — родитель и и и', тогда и и и' называются братьями. Если существует ориентированный путь из вершины и в вершину и, тогда и называется предком вершины и, а и называется потомком вершины н. Если наибольшая из степеней выхода для вершин дерева равна т, тогда дерево называется гп-арным деревом. В частном случае, когда т = 2, дерево называется бинарным деревом.
В каждом бинарном дереве каждый сын родителя обозначается либо как левый сын, либо как правый сын (но не то и другое одновременно). ПРИМЕР 6.39. Граф на рис. 6.44 — бинарное дерево. Уровень вершины ие равен 2, уровень вершины иа равен 3. Высота дерева — 3, поскольку длина пути иоизизиа равна 3 и не существует более длинного пути от корня к листу. Вершина и~ является родителем для из и и4. з Риа 6.44 Вершины из и ил — братья. Таковыми же являются вершины иг и из, из и ие и ит и из.
Вершина иг — предок вершин из, ит, иа, а из, ит и из — потомки вершины иы Вершина из — левый сын вершины из, а ил — правый сын вершины иь П Теперь докажем, что в каждом дереве число вершин на единицу больше числа ребер. Предположим, что имеется дерево Т. Ранее уже показано, что любое дерево можно представить как корневое дерево, и это никоим образом не меняет нн числа ребер, ни числа вершин.
Рассмотрим теперь ориентированное дерево Т', порожденное деревом Т. У каждого ребра Т одна и только одна конечная вершина. Следовательно, число ребер и вершин одно и то же, исключая корневую вершину. Если учесть корневую вершину, получим, что вершин на одну больше, чем ребер. Таким образом, нами доказана следующая теорема.
ТЕОРЕМА 6.40. Если у дерева Т имеется е ребер и и вершин, тогда и = е+ 1. Справедлива также и обратная теорема. ТЕОРЕМА 6.41. Если в связном графе С, содержащем е ребер и и вершин, имеем и = е+ 1, тогда С вЂ” дерево. ДОКАЗАТЕЛЬСТВО. Если С содержит цикл, то, как было установлено при доказательстве теоремы 6.38, если ребро (и„ и ) входит в цикл, существуют два пути из и, в и . Таким образом, ребро (и;,из) можно из цикла удалить, а путь из вершины и, в вершину и, будет существовать. Пусть а и Ь вЂ” любые точки в С.
Поскольку граф С вЂ” связный, существует путь из а в Ь. Если ребро 1и;, и ) удалено, все равно существует путь из а в Ь, поскольку ребро 1и;,и ), входящее в путь, можно заменить альтернативным путем из и; в и . Удалим ребро 1и;,иу) из С и, если оставшийся граф все еще содержит цикл, удалим другое ребро, используя ту же процедуру. Будем продолжать, пока все циклы не будут удалены. В 264 ГЛЯ8Я б. Графы, ориентированные графы и деревья результате получим связный граф, скажем, С', без циклов. Поэтому С' является деревом, и по теореме 6.40 число вершин и = е'+ 1, где е' — число ребер графа С'. Поскольку ни одна из вершин не была удалена, число вершин остается таким, которое было раньше.
Если было удалено и ребер, тогда е = е'+ и. Но поскольку и = е+ 1 и о = е'+ 1, то е = е' и и = О. Следовательно, ни одно ребро не было удалено, поэтому С вЂ” дерево. Дерево С', построенное из С в процессе приведенного выше доказательства, называется оставным (или каркасным) деревом графа С. Дадим более формальное определение. ОПРЕДЕЛЕНИЕ 6.42. Дерево Т называется остовным деревом графа С, если Т вЂ” подграф графа С и каждая вершина в С является вершиной в Т. Итак, доказана следующая теорема.
ТЕОРЕМА 6.43. У каждого связного графа существует подграф, который является остовным деревом. До сих пор рассматривались ориентированные деревья, образованные из корневых (неориентированных) деревьев. Ориентированное дерево называется корневым ориентированным деревом, если существует единственная вершина ио такая, что )пс)ея(ио) = О, и существует путь из ио в каждую другую вершину дерева. Заметим, что ориентированные деревья, которые были рассмотрены до сих пор, в действительности соответствуют этому определению.
Рассмотрим, однако, ориентированное дерево на рис. 6.45. "о оо "о 'о Рис 64б Это ориентированное дерево, но оно не является корневым ориентированным деревом. Большинство ориентированных деревьев, которые мы рассмотрим в дальнейшем, будут, тем не менее, корневыми ориентированными деревьями. ° УПРАЖНЕНИЯ 1.
Которые из приведенных ниже графов являются деревьями? а) б) "о оо "о РАЗДЕЛ а.3. Деревья 265 в) г) "о оо 2. Для каждого дерева из предыдущего упражнения а) используйте в качестве корня вершину ез и нарисуйте корневое дерево; б) нарисуйте порожденное корневое ориентированное дерево; в) используйте в качестве корня вершину ез и нарисуйте корневое дерево; г) нарисуйте порожденное корневое ориентированное дерево. 3. Которые из приведенных ниже графов являются деревьями? а) б) в) г) д) "о о 4. Для каждого дерева из предыдущего упражнения а) используйте в качестве корня вершину ез и нарисуйте корневое дерево; б) нарисуйте порожденное корневое ориентированное дерево; в) используйте в качестве корня вершину ез и нарисуйте корневое дерево; г) нарисуйте порожденное корневое ориентированное дерево. 5.
Покажите, что если лес содержит гп компонент, то е = е+ т. 6. Которые из приведенных ниже графов являются корневыми ориентированными деревьями? 266 ГЛАВА 6. Графы, ориенглироеанньбе графы и деревья а) б) в) Уб 5 б 7 б г) д) Л'Л ° ° ° ° ° ° б б б б б б "б Л'Л ° ° я б бб 1~ "б ° ° 7 б "б Рис. 6.46 Рис. 6.41 показанного на рис. 6.47, 8. Для корневого ориентированного дерева а) найдите потомков вершины юз, б) найдите предков вершины юз, в) найдите родителя вершины ог, 7.
Для корневого ориентированного дерева, показанного на рис. 6.46, а) найдите потомков вершины оз, б) найдите предков вершины юз, в) найдите родителя вершины юз, г) определите уровень вершины ое, д) найдите сыновей вершины оз, е) найдите высоту дерева; ж) найдите листья дерева; з) определите, является ли это дерево бинарным? РАЗДЕЛ б.4. Мгновенное безумие 267 г) определите уровень вершины ив, д) найдите сыновей вершины из, е) найдите высоту дерева; ж) найдите листья дерева. 9. Нарисуйте генеалогическое дерево, начиная с одного из своих прадедушек. 10. Нарисуйте генеалогическое дерево, начиная с одной из своих прабабушек (но не с жены прадедушки из предыдущей задачи).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
