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

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

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

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

Таким образом, граф — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.

Граф G = (V, Е) задается парой конечных множеств V и Е. Элементы первого множества v1, v2. vM называются вершинамиграфа. Элементы второго множества el, e2, . eN называются ребрами.Каждое ребро определяется парой вершин.

Если ребра графа определяются упорядоченными парами вершин, то такой граф называют ориентированным (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указывающую его направление).

Рис.7 — Ориентированный граф с пятью вершинами и семью ребрами

Степенью вершины графа называется количество выходящих из нее ребер. Граф называется связным, если любая пара его вершин связана.

Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (ребра е4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей(ребро e7). Граф без петель и параллельных ребер называется простым.

Маршрут, в котором все определяемые им ребра различны, называют цепью.Цепь считаютзамкнутой, если ее концевые вершины совпадают. Замкнутая цепь, в которой все вершины различны, называется циклом.

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

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

Дерево — это связный граф без циклов.

Дерево — это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

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

С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся.

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

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

Читайте также:  Написать в директ это куда

Пример 10. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9419 — | 7463 — или читать все.

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

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

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

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

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

Свойства

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

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

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

для числа Tn неизоморфных корневых деревьев с n вершинами удовлетворяет функциональному уравнению .

  • Производящая функция

для числа tn неизоморфных деревьев с n вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

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

где C и α определённые константы, C = 0,534948. , α = 2,95576. .

Кодирование деревьев

Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 0 при движении по ребру в первый раз и 1 при движении по ребру второй раз (в обратном направлении). Если m — число ребер дерева, то через 2m шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 и 1 (код дерева) длины 2m позволяет однозначно восстанавливать не только само дерево D , но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с n вершинами:

Читайте также:  Монитор benq q7c3 характеристики

См. также

Книги

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

Wikimedia Foundation . 2010 .

Смотреть что такое "Дерево (граф)" в других словарях:

граф — Графическое изображение электрической цепи, в котором ветви электрической цепи представлены отрезками, называемыми ветвями графа, а узлы электрической цепи — точками, называемыми узлами графа. [ГОСТ Р 52002 2003] граф Основное понятие и… … Справочник технического переводчика

Граф — [graph] основное понятие и объект изучения теории графов, математически определяется двояко. С одной стороны как совокупность двух множеств: множества элементов x Î X и множества соответствий, отношений между этими элементами t Î T. С другой… … Экономико-математический словарь

Дерево — [tree] в теории графов, связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n 1 ребро, не имеет циклов; если добавить… … Экономико-математический словарь

дерево (в теории графов) — В теории графов ? связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n 1 ребро, не имеет циклов; если добавить ребро,… … Справочник технического переводчика

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

дерево целей — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] дерево целей В программно целевых методах планирования и управления — граф, схема, показывающая членение общих (генеральных) целей плана или… … Справочник технического переводчика

Дерево целей — [relevance tree] в программно целевых методах планирования и управления граф, схема, показывающая членение общих (генеральных) целей плана или программы на подцели, последних на подцели следующего уровня и т.д. (дерево это связный граф,… … Экономико-математический словарь

Граф Кэли (теория групп) — Граф Кэли граф, который строится по группе с выделенной системой образующих. Назван в честь Кэли. Определение Пусть дана дискретная группа G и система образующих S. Предположим S = S − 1, то есть, для каждого . Графом Кэли группы G по системе… … Википедия

Читайте также:  Как установить уведомление о прочтении в outlook

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

Дерево решений — [decision tree] граф, схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Применяется в динамическом программировании и в других областях для анализа решений, структуризации проблем. Ветви дерева отображают… … Экономико-математический словарь

4.3. Деревья и лес

Свойства деревьев

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

Среди различных деревьев выделяют два важных частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево (или куст), в котором одна из вершин (центр) смежна со всеми остальными вершинами.

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

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

Теорема 4.9. Каждое дерево с вершинами имеет в точности ребро.

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

Теорема 4.11. У каждого дерева найдется висячая вершина.

Теорема 4.12. При удалении любого ребра дерева оно распадается на связные компоненты, являющиеся либо изолированными вершинами, либо деревьями. При добавлении в дерево любого нового ребра в нем образуется простой цикл, и оно перестает быть деревом.

Дерево на рис. 4. 35 при удалении ребра распадается на лес из двух деревьев и , а после добавления ребра превращается в циклический граф .

другой его вершиной (рис. 4. 3 6). Прадерево может иметь только один корень.

Рассмотрим дерево с вершинами. Назовем его концевые вершины вершинами типа 1. Теперь удалим все вершины типа 1 и концевые ребра. В результате получим связный граф без циклов , то есть опять дерево, но с уже меньшим количеством вершин. Концевые вершины дерева назовем вершинами типа 2 в дереве . Аналогично определяются вершины типов 3, 4 и т. д. Легко видеть, что дерево может иметь либо одну вершину максимального типа, либо две таких вершины. Типы вершин дерева , изображенного на рис. 4. 3 7, записаны рядом с соответствующими вершинами. Здесь же показаны последовательные этапы процедуры, позволяющей их определить. Это дерево имеет две вершины максимального типа. Если у дерева удалить одну из вершин типа 2 и ребра, ей инцидентные, то получившееся при этом дерево будет иметь уже только одну вершину максимального типа.

Ссылка на основную публикацию
Экран из фильма аватар
Джейк Салли — бывший морской пехотинец, прикованный к инвалидному креслу. Несмотря на немощное тело, Джейк в душе по-прежнему остается воином....
Что такое vpn на планшете
Каждый из пользователей интернета хоть раз да слышал о VPN, но мало кто задумывался о его необходимости и роли для...
Что такое ussd сообщение
Содержание статьи Что такое ussd запрос Как отключить GPRS-интернет Какие есть USSD-коды и полезные номера у Мегафона USSD является сокращением...
Экран ноутбука стал синим что делать
Большинство пользователей ноутбуков сталкиваются с ситуацией, когда компьютер выдает так называемый синий экран смерти или BSOD. Для начала необходимо знать:...
Adblock detector