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

Научный форум 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 писал(а):
Что такое эти циклы? Типа что нельзя в тот же узел вернуться?

Страница 1 из 1 [ Сообщений: 8 ]

Кто сейчас на конференции

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

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

Деревья

Граф G = (V,E) называется деревом, если он связный и не содержит циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. Вершины степени 1 в дереве называют его листьями. Другие вершины называются внутренними вершинами.

Подграф G₁ = (V₁,E₁) графа G = (V,E) называется остовным деревом, если G₁ — дерево и V₁ = V.

Для (p, q)- графа G следующие утверждения эквивалентны:

• 1) G — дерево;
• 2) G — ациклическим и q = p-1;
• 3) G — связный и q = p-1;
• 4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;
• 5) G — без циклов, но при добавлении любого нового ребра на тех же вершинах появляется цикл.

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

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

Если подвесить его за вершину v₃, получится дерево, представленное на рис. 10, а). Если подвесить дерево за вершину v₄, оно будет выглядеть так, как показано на рис. 10, б).

Вершина в самой верхней части каждого из изображений называется корнем дерева. Если корень дерева определен, дерево называется корневым деревом. При необходимости можно заменить корневое дерево Т на ориентированное Т, при этом дерево на рис.11, в) будет заменено деревом на рис.11,г).

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

Если корень выбран, уровень вершины v определяется длинной единственного пути из корня в эту вершину. Высотой дерева называется длинна самого длинного маршрута от корня дерева до листа.

Если рассматривать корневое ориентированное дерево Т, порожденное данным корневым деревом Т, тогда вершина u называется родителем вершины v, а v называется сыном вершины u, если существует ориентированное ребро из u в v.

Если u — родитель v и v‘, тогда v и v‘ называются братьями. Если существует ориентированный маршрут из вершины u в вершину v, тогда u называется предком вершины v, а v называется потомком вершины u.

Если наибольшая из степеней выхода для вершин дерева равна m, тогда дерево называется m-арным деревом. В частном случае, когда m=2, дерево называется бинарным деревом.

Взвешенный граф — это граф, каждому ребру которого приписано действительное число, называемое весом ребра.[1]

Деревья и лес в теории графов

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

Лес — упорядоченное множество упорядоченных деревьев.

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

Фомина Нюргуяна Владимировна

Содержимое разработки

Определение. Н–граф называется неориентированным деревом (или просто деревом) если он связен и не содержит циклов, а значит петель и кратных ребер. Дерево – это минимальный связный граф в том смысле, что при удалении хотя бы одного ребра он теряет связность. Наличие этих двух свойств (связность и отсутствие циклов) позволяет жестко связать число вершин и число ребер: в дереве с вершинами всегда ребер. Пример графа–дерева приведен на рисунке 3.13. В этом графе 8 вершин и 7 ребер. Ни одно ребро нельзя удалить из графа без того, чтобы он не потерял связность.

Вершина графа называется концевой или висячей, если В графе на рис. 3.13 концевыми являются вершины .

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

В каждую вершину ориентированного дерева (за исключением корня) входит только одно ребро. Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину.

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

Определение. Лес – несвязный н–граф без циклов. Связные компоненты леса являются деревьями. Любая часть леса также является лесом или деревом. В неориентированном дереве между любыми двумя вершинами существует цепь и притом только одна.

Рассмотрим пример использование графа–дерева для решения задачи поиска гамильтоновых путей на взвешенном по ребрам графе, приведенном на рис. 3.14. Веса можно рассматривать как некоторый эквивалент затрат, связанных с переходом по ребру из одной вершины в другую. Будем считать, что коммивояжер отправляется из вершины , с тем, чтобы посетить вершины и вновь вернуться в .

Для решения задачи удобно воспользоваться вспомогательным графом–деревом, который позволяет не только получить все гамильтоновы пути, но и отслеживать вес каждого пути. Методика построения следующая: выделяется исходная вершина и ей присваивается нулевой вес. На вспомогательном графе такая вершина помечается как . Из исходной вершины проводятся ребра во все смежные вершины, по которым маршрут еще не проходил. Новым вершинам присваиваются веса, равный затратам, которые необходимо понести для их достижения из исходной вершины. Для рассматриваемого примера результатом первого шага станут вершины . Далее точно таким же образом производятся шаги из вновь полученных вершин, пока эти пути не приведут в исходную вершину. Часть путей могут быть тупиковыми, так как не позволяют завершить маршрут не заходя дважды в одну и ту же вершину. В данном примере, в частности, последовательность вершин является тупиковой.

Рис. 3.15. Граф–дерево, соответствующий полному перебору вариантов построения гамильтонового цикла в исходном графе рис. 3.14.

Приведенный на рис. 3.15 граф–дерево построен для решения задачи поиска кратчайшего гамильтонового пути с использованием метода полного перебора вариантов.

Проблема, однако, в том, что при большом числе вершин полный перебор вариантов, это работа, требующая огромных вычислений. В частности, для полного графа с вершинами число маршрутов равно . Если 5!=120, то 10!=3 628 800. И все-таки перебор маршрутов иногда бывает полезен. Известен метод решения задачи, в соответствии с которым шаг за шагом строится не полное, а «усеченное» дерево – часть ветвей в процессе его «выращивания» отсекаются, а оставшиеся ветви ведут к решению. Этот метод называется методом ветвей и границ.

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

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

-80%

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

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

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

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

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

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

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

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

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

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