Свободные деревья. Основные свойства деревьев.
Деревья заслуживают отдельного и подробного рассмотрения по двум причинам.
Деревья являются в некотором смысле простейшим классом графов. Для них вы-полняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Выдвигая какие-то гипотезы при решении задач теории графов, целесообразно сначала их проверять на деревьях.
Деревья являются самым распространенным классом графов, применяемых в про-граммировании, причем в самых разных ситуациях. Более половины объема этой главы посвящено рассмотрению конкретных применений деревьев в программировании.
Свободные деревья. Изучение деревьев целесообразно начать с самых общих определений и установления основных свойств. Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Таким образом, компонентами связности леса являются деревья. Замечание: Прилагательное "свободное" употребляется в том случае, когда нужно подчеркнуть отличие деревьев от других объектов, родственных деревьям: ориентированных деревьев, упорядоченных деревьев и т. д.
В связном графе G выполняется неравенство q(G) ³ p(G) – 1. Граф G, в котором q(G) = p(G) – 1, называется древовидным. В ациклическом графе G z(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 - связный, субциклический и неполный.
Следствие: В любом нетривиальном дереве имеются по крайней мере две висячие вершины.
Дата добавления: 2021-07-22; просмотров: 349;