Главная » Деревья

Граф дерево свойство деревьев

Содержание
  1. Дерево (граф)
  2. Связанные определения
  3. См. также
  4. Книги
  5. Теория графов
  6. Ориентированные деревья
  7. Лекция 11
  8. Базовые понятия и утверждения
  9. 1. Определение и основные свойства деревьев.

Дерево (граф)

В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.

Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

Связанные определения

  • Степень узла — количество поддеревьев узла
  • Концевой узел (лист) — узел со степенью нуль.
  • Узел ветвления — неконцевой узел.
  • Уровень узла определяется рекурсивным образом:
  1. Уровень корня дерева T равен нулю
  2. Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T , содержащего данный узел.
  • Дерево с отмеченной вершиной назывется корневым деревом.
    • m -й ярус узла T — множество узлов дерева, на уровне m от корня дерева.
    • частичный порядок на вершинах: u \prec v, если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v .
    • корневое поддерево с корнем v — подграф \<v\ data-lazy-src=
  • Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
  • Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
  • Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».

Двоичное дерево

Термин двоичное дерево имеет несколько значений:

  • Двоичное (бинарное) дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят 3.
  • Двоичное (бинарное) дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
  • Двоичное дерево (структура данных) — это специальная абстрактная Структура данных используемая в программировании. На двоичном дереве основаны такие структуры данных, как Двоичное дерево поиска, Двоичная куча, Красно-чёрное дерево, АВЛ-дерево, Фибоначчиева куча и др.

N-арные деревья

N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.

  • N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
  • N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

Свойства

  • Дерево не имеет кратных ребер и петель.
  • Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1 , здесь B — число вершин, P — число рёбер графа.
  • Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.
  • Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
  • Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.

Подсчёт деревьев

  • Число различных деревьев которые можно построить на n нумерованных вершинах, равно nn − 2 (Теорема Кэли).
  • Производящая функция

T(z)=x\exp\sum_<r=1 data-lazy-src=

  • При n\to\inftyверна следующая ассимптотика

t_n\sim C\alpha^n/n^<5/2 data-lazy-src=

Книги

  • Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
  • Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.

Wikimedia Foundation . 2010 .

Источник

Теория графов

Следующая теорема устанавливает, что два из четырех свойств – связность, ацикличность, древовидность и субцикличность – характеризуют граф как дерево.

  1. Для – графа следующие утверждения эквивалентны:
    1. – дерево;
    2. Любые две несовпадающие вершины графа соединяет единственная простая цепь;
    3. – связный граф, и любое ребро есть мост;
    4. – связный граф и древовидный;
    5. – ациклический граф (лес) и древовидный;
    6. – ациклический граф (лес) и субцикличекий;
    7. – связный, субциклический и неполный, ;
    8. – древовидный и субциклический, исключая и ;
    (1->2): Если – дерево, то любые две его несовпадающие вершины соединяет единственная простая цепь. От противного. Пусть существуют две цепи (см. рис.). Тогда — простой цикл. (2->3): Если любые две несовпадающие вершины графа соединяет единственная простая цепь, то – связный граф, и любое ребро есть мост. Имеем: (число компонент связности). Далее от противного. Пусть ребро — не мост. Тогда в концы этого ребра связаны цепью. Само ребро в исходном графе – вторая цепь, что противоречит условию. (3->4): Если – связный граф, и любое ребро есть мост, то – связный и древовидный (). Индукция по (числу вершин). Если , то (число ребер). Пусть равенство выполняется для всех графов с числом вершин меньше . Докажем, что оно выполняется и для вершин. Удалим из ребро , являющееся мостом. Получим две компоненты связности и , для которых верно равенство . Т.е. , . Тогда . (4->5): Если – связный и древовидный (), то – ациклический граф (лес) и древовидный (). От противного. Пусть есть цикл с вершинами и ребрами. Остальные вершин связаны с этим циклом ребрами, т.к. граф связный. Следовательно, , что противоречит условию . Остальное без док-ва.

        1. Ориентированные деревья

    1. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
    • существует единственный узел, в который не входит ни один другой узел. Он называется корнем ордерева;
    • во все остальные узлы входит только по одному узлу;
    • каждый узел достижим из корня.
    1. Ордерево обладает следующими свойствами:

    1. ; 2. если в ордереве отменить ориентацию ребер, то получится обычное дерево; 3. для каждого узла существует единственный путь, ведущий в этот узел из корня; 4. подграф, определяемый множеством узлов, достижимых из узла , является ордеревом с корнем . Это ордерево называется поддеревом узла .

    1. Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние отт корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

    Источник

    Лекция 11

    Дерево. Лес (ациклический граф). Остовный подграф. Остов. Взвешенный граф. Минимальный остов. Кодирование деревьев.

    Базовые понятия и утверждения

    1. Определение и основные свойства деревьев.

    Определение. Граф называется деревом, если он связный и в нем нет циклов.

    Одноэлементный граф, т.е. граф, имеющий одну вершину и не имеющий ребер, также считается деревом.

    Граф называется лесом (или ациклическим графом), если в нем нет циклов. Очевидно, что каждая компонента связности леса — дерево.

    Пример 1. Граф (рис. 3.19) не является ни деревом, ни лесом. Граф (рис. 3.20) — дерево. Граф (рис. 3.21) — лес, состоящий из четырех деревьев.

    Пример 2. Представьте диаграммами все (с точностью до изоморфизма) деревья с пятью вершинами.

    ◄ Имеется три различных (с точностью изоморфизма) дерева с пятью вершинами (рис. 3.22 — 3.24). ►

    Деревья обладают рядом характеристических свойств, по наличию или отсутствию каждого их которых в рассматриваемом графе можно определить, является граф деревом или нет. Перечислим эти свойства:

    1) граф — дерево в том и только в том случае, когда в нем нет циклов и ;

    2) граф — дерево в том и только в том случае, когда он связный и ;

    3) граф — дерево в том и только в том случае, когда он связный, и каждое его ребро является мостом;

    4) граф — дерево в том и только в том случае, когда любые две вершины графа можно соединить простой цепью, притом единственной;

    5) граф — дерево в том и только в том случае, когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла.

    Также приведем одно из характеристических свойств леса: граф , имеющий компонент связности, является лесом в том и только в том случае, когда .

    2. Остовы графа. Подграф графа называется остовным подграфом, если множество его вершин совпадает с множеством вершин графа .

    Остовом обыкновенного графа называется его остовный подграф, являющийся деревом.

    Пусть — связный граф. Если содержит хотя бы один цикл, то удалив из графа некоторое ребро этого цикла, мы уменьшим число циклов графа по крайней мере на единицу, сохранив при этом его связность. Ясно, что, последовательно разрушая циклы данного графа, можно прийти к остову графа. Поскольку дерево с вершинами имеет ровно ребро, то для получения остова нужно удалить из графа ребро, т.е. число ребер, равное цикломатическому числу связного графа .

    Пусть теперь — произвольный граф с компонентами связности. Из каждой компоненты связности этого графа удалим ребро так, чтобы получился остов этой компоненты. В результате получим некоторый остовный подграф графа . Подсчитаем общее число ребер, которое нам пришлось для этого удалить. Сложив равенства , , получим:

    .

    Таким образом, чтобы получить остовный подграф, нужно, последовательно разрушая циклы графа, удалить из него число ребер, равное его цикломатическому числу.

    Пример 3. Построим остов графа , диаграмма которого изображена на рис. 3.25. Удалим из графа ребро ; получим граф (рис. 3.26). Из графа удалим ребро ; получим граф (рис. 3.27). Из графа удалим ребро ; получим граф (рис. 3.28), который является одним из остовов графа .

    Источник

    Читайте также:  Чем можно заменить наждачную бумагу при обработке дерева
Оцените статью
© 2024 Деревья и растения