лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
 Скачать 1.51 Mb.
|
Свободные деревья. Основные свойства деревьев.Деревья заслуживают отдельного и подробного рассмотрения по двум причинам. Деревья являются в некотором смысле простейшим классом графов. Для них вы-полняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Выдвигая какие-то гипотезы при решении задач теории графов, целесообразно сначала их проверять на деревьях. Деревья являются самым распространенным классом графов, применяемых в про-граммировании, причем в самых разных ситуациях. Более половины объема этой главы посвящено рассмотрению конкретных применений деревьев в программировании. Свободные деревья. Изучение деревьев целесообразно начать с самых общих определений и установления основных свойств. Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Таким образом, компонентами связности леса являются деревья. Замечание: Прилагательное "свободное" употребляется в том случае, когда нужно подчеркнуть отличие деревьев от других объектов, родственных деревьям: ориентированных деревьев, упорядоченных деревьев и т. д. В связном графе G выполняется неравенство q(G) p(G) – 1. Граф G, в котором q(G) = p(G) – 1, называется древовидным. В ациклическом графе Gz(G) = 0 Пусть и, v — несмежные вершины графа G, х = (u,v)  E. Если граф G + х имеет только один простой цикл, z(G + х) = 1, то граф G называется субциклическим.Пример: На рисунке показаны диаграммы всех различных (свободных) деревьев с 5 вершинами.  На рисунке - диаграммы всех различных (свободных) деревьев с 6 вершинами  Основные свойства деревьев. Следующая теорема устанавливает, что два из четырех свойств – связность, ацикличность, древовидность и субцикличность – характеризуют граф как дерево. Теорема: Пусть G(V, Е) – граф с р вершинами, q ребрами, k компонентами связности и z простыми циклами. Пусть далее х – ребро, соединяющее любую пару несмежных вершин в графе G, тогда следующие утверждения эквивалентны: 1. Граф G - дерево, то есть связный граф без циклов k(G) = 1 & z(G) = 0 ; 2. Любые две вершины соединены в G единственной простой цепью: G: u,v ! <u, v>; 3. Граф G - связный граф, и любое ребро есть связный мост G: k(G) = 1 & e Ek(G– e) > 1; 4. Граф G - связный и древовидный G: k(G) = 1 & q(G) = p(G) – 1; 5. Граф G - ациклический и древовидный G: z(G) = 0 & q(G) = p(G) – 1; 6. Граф G - ациклический и субциклический G: z(G) = 0 & z(G + x) = 1; 7. Граф G - связный, субциклический и неполный. Следствие: В любом нетривиальном дереве имеются по крайней мере две висячие вершины. Ориентированные, упорядоченные и бинарные деревьяОриентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и в программировании. Дерево (ориентированное) и иерархия – это равнообъемные понятия. Ориентированные деревья. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами: 1) Существует единственный узел, полустепень захода которого равна 0. Он называется корнем ордерева. 2) Полустепень захода всех остальных узлов равна 1. 3)Каждый узел достижим из корня. Пример: На рисунке приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рисунке 2 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.  __________ Теорема: Ордерево обладает следующими свойствами: 1) Число рёбер равно числу вершин-1(свойство древовидности): q = p – 1. 2) Если в ордереве отменить ориентацию ребер, то получится свободное дерево. 3) В ордереве нет контуров. 4) Для каждого узла существует единственный путь, ведущий в этот узел из корня. 5) Подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v). 6) Если в свободном дереве любую вершину назначить корнем, то получится ордерево. Замечание: Каждое свободное дерево определяет не более р ориентированных деревьев. Таким образом, общее число различных ордеревьев с р узлами не более чем в р раз превосходит общее число различных свободных деревьев с р вершинами. Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева. Замечание: Наряду с "растительной" применяется еще и "генеалогическая" терминология. Узлы, достижимые из узла и, называются потомками узла и (потомки образуют поддерево). Если в дереве существует дуга (u,v), то узел 0 называется отцом (или родителем) узла u, а узел v называется сыном узла u. Сыновья одного узла называются братьями. Эквивалентное определение ордерева. Ордерево T — это конечное множество узлов, таких что: 1) Имеется один узел v, называемый корнем данного дерева; 2) Остальные узлы (исключая корень) содержатся в k попарно непересекающихся множествах. Упорядоченные деревья. Множества в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев фиксирован, то ордерево называется упорядоченным. |