Чем дерево отличается от графа
Перейти к содержимому

Чем дерево отличается от графа

  • автор:

Деревья — Теория графов

В этом уроке мы изучим еще один вид графов — древовидные. Именно этот вид графов активно используется в программировании — он связан с алгоритмами сортировки и поиска.

Деревья

Деревья — это связные графы без циклов. Их часто применяют в математике и информатике. Вот так они выглядят:

Как видно из примера, у деревьев определенная древовидная ветвистость, откуда они и получили свое название.

Благодаря связности и отсутствию циклов у деревьев есть ряд свойств:

  • В любом дереве есть ровно один путь из каждой вершины в каждую другую. Например, если есть два пути к вершине, то их можно объединить, чтобы получить цикл
  • У деревьев наименьшее количество ребер, которое только может быть у графа. При этом они остаются связными. Каждое ребро дерева — режущее, значит, не лежит в цикле
  • У деревьев наибольшее число ребер, которое может быть у графа без циклов. Добавление любого ребра к дереву создает ровно один цикл. Например, если добавить ребро между вершинами и , то получится цикл, включающий ребро и путь. Он гарантированно существует между и

Листья и индукция

С древовидными графами работает механизм индукции — это значит, что по каждому дереву с

вершинами можно перемещаться с шагом

Для этого нам понадобится лист в дереве — вершина, которая находится на концах каждого дерева.

Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.

Рассмотрим любой путь максимальной длины в дереве. Поскольку у дерева две вершины и оно связное, этот путь должен существовать. У обеих конечных точек этого пути степень

в дереве. Их единственные соседи — вершины, которые располагаются перед ними на пути.

Обсудим, почему это работает именно так:

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

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

Научный форум dxdy

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

Re: Чем граф от дерева отличается?
08.07.2011, 17:38

Заслуженный участник

Последний раз редактировалось caxap 08.07.2011, 17:40, всего редактировалось 2 раз(а).

Дерево тоже граф; это граф без циклов. Проще не скажешь.
Re: Чем граф от дерева отличается?
08.07.2011, 17:40

Дерево — граф, обратное не всегда верно. По-моему, у дерева всегда лишь один вход в каждый узел — и вообще это имеет смысл говорить лишь для направленных графов (у которых на каждом ребре указано направление).
С уважением, Gortaur.
А вообще, граф его по воротнику гармошкой видно и входа у него два снизу (ноги), а у дерева один (ствол).

Re: Чем граф от дерева отличается?
08.07.2011, 17:47

Заслуженный участник

Gortaur в сообщении #466525 писал(а):
С уважением, Gortaur.

Тренируетесь?
Re: Чем граф от дерева отличается?
08.07.2011, 17:55

Итак, дерево — граф без циклов.

Что такое эти циклы? Типа что нельзя в тот же узел вернуться?

Re: Чем граф от дерева отличается?
08.07.2011, 18:06
bigarcus в сообщении #466520 писал(а):
Спасибо Вам за Ваше время.
Re: Чем граф от дерева отличается?
08.07.2011, 18:10

Заслуженный участник

Ещё связность забыли, и циклы рассматриваются без учёта направления рёбер.
Re: Чем граф от дерева отличается?
08.07.2011, 18:19

Заслуженный участник

Последний раз редактировалось caxap 08.07.2011, 18:36, всего редактировалось 3 раз(а).

bigarcus в сообщении #466535 писал(а):
Что такое эти циклы? Типа что нельзя в тот же узел вернуться?

$\begin</p>
<p>Нет (например, тогда у вас граф \draw (0,0)—(.6,0); \fill [color=black] (0,0) circle (2.5pt); \fill [color=black] (.6,0) circle (2.5pt); \end$» /> имеет цикл). Позвольте спросить: к чему все эти колхозно-бытовые упрощения? Вы собираетесь 5-летнему ребёнку рассказать основы теории графов?</p><div class='code-block code-block-9' style='margin: 8px 0; clear: both;'>
<!-- 9joomlaumnik -->
<script src=

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

Страница 1 из 1 [ Сообщений: 8 ]
Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Кружок по программированию, 2017-2018

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

rooted_tree1

Итак, отмеченную вершину называют корнем. Как известно, в дереве между любыми двумя вершинами существует ровно один путь. Возьмём любую вершину и соединим её путём с корнем. Все вершины в этом пути, кроме исходной, называются её предками (ancestor). Вершина, следующая в этом пути за исходной, называются её родителем (parent). Корень — это единственная вершина в дереве, у которой нет ни родителей, ни предков вообще.

На этой картинке Grace, Alice и Jake являются предками Luca, Caitlin и Jake — предками Ben. Jake является общим предком Luca и Ben (а заодно и общим предком вообще всех вершин).

rooted_tree2

Если вершина А является предком вершины Б, то Б называется потомком (descendant) А. Для данной вершины А множеством её потомков являются все вершины, не совпадающие с А, путь из которых к корню проходит через А. Аналогично, если вершина А — родитель вершины Б, то вершина Б называется сыновьей (child) для А.

Здесь уже всё понятно, у каждой вершины, кроме корня, есть единственный родитель.

rooted_tree3

Luca — единственный потомок Grace. У Caitlin четыре потомка — Ben, Megan, Eva и Harry. И наконец у Sean нет потомков.

rooted_tree4

Вершины, у которых общий родитель, называются братьями (sibling).

И наконец вершины, у которых нет потомков, называются листьями.

Последнее изменение: Суббота, 15 Август 2020, 02:35

Дерево, эквивалентные определения

Пример дерева

Для графа [math]G[/math] эквивалентны следующие утверждения:

  1. [math]G[/math] — дерево.
  2. Любые две вершины графа [math]G[/math] соединены единственным простым путем.
  3. [math]G[/math] — связен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
  4. [math]G[/math] — ацикличен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
  5. [math]G[/math] — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  6. [math]G[/math] — связный граф, отличный от [math] K_p [/math] для [math] p \gt 3 [/math] , а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  7. [math]G[/math] — граф, отличный от [math] K_3 \cup K_1 [/math] и [math] K_3 \cup K_2 [/math] , а также [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

Доказательство эквивалентности

[math] 1 \Rightarrow 2 [/math]

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

[math] 2 \Rightarrow 3 [/math]

Очевидно, что граф связен. Докажем по индукции, соотношение [math]p = q + 1[/math] . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает граф [math] G [/math] несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, [math] p = q + 1 [/math] .

[math] 3 \Rightarrow 4 [/math]

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

[math] 4 \Rightarrow 5 [/math]

[math]G[/math] — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то [math] p = q + k [/math] , где [math]k[/math] — число компонент связности. Поскольку [math] p = q + k [/math] , то [math] k = 1 [/math] , а значит [math]G[/math] — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

[math] 5 \Rightarrow 6 [/math]

Поскольку [math] K_p [/math] для [math] p \gt 3 [/math] содержит простой цикл, то [math]G[/math] не может им являться. [math]G[/math] связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

[math] 6 \Rightarrow 7 [/math]

Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку [math] 2 \Rightarrow 3 [/math] , получим [math] p = q + 1 [/math] . Любые две вершины соединены простой цепью, так как [math]G[/math] — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться [math] K_3 [/math] , так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. [math] K_3 [/math] является собственным подграфом [math]G[/math] , поскольку [math]G[/math] не является [math] K_p [/math] для [math] p \gt 3 [/math] . [math]G[/math] — связен, а значит есть вершина смежная с [math] K_3 [/math] . Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф [math]G[/math] является [math]K_p[/math] для [math] p \gt 3 [/math] , и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

[math] 7 \Rightarrow 1 [/math]

Если [math]G[/math] имеет простой цикл, то он является отдельной компонентой [math]K_3[/math] по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения [math] p = q + 1 [/math] должно быть не более одной компоненты отличной от [math]K_3[/math] , так как в [math]K_3[/math] [math] p = q = 3 [/math] . Если это дерево содержит простой путь длины 2, то в [math]G[/math] можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является [math]K_1[/math] или [math]K_2[/math] . Значит [math]G[/math] является [math]K_3 \cup K_1[/math] или [math]K_3 \cup K_2[/math] , которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если [math]G[/math] ациклический и [math] p = q + 1 [/math] , то из [math] 4 \Rightarrow 5 [/math] и [math] 5 \Rightarrow 6 [/math] верно, что [math]G[/math] — связен. В итоге получаем, что [math]G[/math] является деревом по определению.

См. также

  • Алгоритмы на деревьях
  • Двоичное дерево поиска

Источники информации

  • Харари Ф. Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • Википедия — дерево(теория графов)
  • Алгоритмы и структуры данных
  • Основные определения теории графов

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *