Построить дерево по последовательности степеней его вершин

Обновлено: 18.09.2024

Выход: код Прюфера длины n – 2.

Повторить n – 2 раза

Выбрать вершину v – лист дерева с наименьшим номером;

Добавить номер единственного соседа v в последовательность кода Прюфера;

Удалить вершину v из дерева;

Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.

1.Выписываем висячие вершины, всего вершин на 2 больше чем значений в коде дерева.

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

3. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.

4. находим следующее число.

Рассмотрим применение данного алгоритма на примере.

Пример 1. Постройте дерево, которому соответствует код

1. Выписываем висячие вершины. Всего вершин на 2 больше чем значений в коде дерева, в данном случае такими будут 3,4,5,6,7.

2. Вершину с минимальным номером (3) соединяем с первым значением кода (1).

3. Поскольку вершина (1) еще встречается в коде , то соединяем следующую висячую вершину (4) с вершиной из кода (2).

Повторяем для 5-2.

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

Степень вершины (англ. degree , также валентность, англ. valency ) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды. [1] Степень вершины обозначается как (в западных источниках — ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Содержание

Лемма о рукопожатиях

По формуле суммы степеней для графа ,

$\sum_<v \in V></p> <p> \deg(v) = 2|E|\, ,$

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

Последовательность степеней вершин

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность d_i (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство

$\sum_<i=1></p> <p>^d_i \leq k(k-1) + \sum_^n \min(d_i,k) \quad \ k \in \ \, .$

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, 2 или 4, но не при k равном 3.

С. Л. Хакими доказал, что (d₁, d₂, …, d_n) есть последовательность степеней простого графа только если существует (d₂ − 1, d₃ − 1, …, d_d₁+1 − 1, d_d₁+2, d_d₁+3, …, d_n). Этот факт позволил разработать простой алгоритм нахождения простого графа с заданной реализуемой последовательностью:

Изначально граф не имеет рёбер.
Составляется список вершин, для которых требования по степеням пока не удовлетворены. Оставшиеся требования располагаются в порядке невозрастания.
Первая вершина соединяется со следующими d₁ вершинами из списка. После этого первая вершина удаляется, список пересортируется. Действие повторяется до тех пор, пока все требования не будут удовлетворены.

Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов.

Частные значения

Вершина степени 0 называется изолированной.
Вершина степени 1 называется концевой (англ.end vertex ), висячей (англ.pendant vertex ) или листом графа (англ.leaf vertex ). Ребро, инцидентное такой вершине называется висячим (англ.terminal (pendant) edge, end-edge ). На рис. 3 висячим ребром является . Подобная терминология используется в изучении деревьев в общем и как структур данных.
Вершина степени n-1 графа порядка n называется доминирующей (англ.dominating vertex ).

Общие свойства

Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k. В этом случае сам граф имеет степень k. существует в неориентированном, связном графе если и только если граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом. является псевдолесом только если полустепень захода каждой вершины не больше 1. Функциональный граф — частный случай псевдолеса, в котором полустепени захода всех вершин равны 1.
Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1.
k-вырожденным графом называется граф, в котором каждый подграф имеет вершину степенью не больше k.

См. также

Полустепень захода и полустепень исхода вершин ориентированных графов
Распределение степеней

Примечания

Источники

Wikimedia Foundation . 2010 .

Полезное

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

Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия

Графов теория — раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих … Большая советская энциклопедия

Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

Практическое применение раскраски графов — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Раскраска графов практически применяется (постановку задачи различиных раскрасок здесь обсуждаться не будет) дл … Википедия

Теоремы теории графов — Здесь собраны теоремы из теории графов. Содержание 1 Лемма о рукопожатиях 2 Существование эйлерова пути и цикла … Википедия

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.

Рис. 1 Бинарное дерево

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

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

Рис. 3 Сбалансированное бинарное дерево поиска

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

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

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

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

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

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

Рис. 5 Вспомогательный рисунок для обходов

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

Надеюсь Вы не уснули, и статья была полезна. Скоро надеюсь последует продолжение ~~банкета~~ статьи.

Рассмотрим граф , Имеющий P вершин и Q ребер.

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

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

Например, на рис. 20 представлено остовное дерево графа, диаграмма которого изображена на рис. 1.

Рис. 20. Остовное дерево графа

Всякое дерево является двудольным графом.

Теорема 23.

1) Граф является деревом тогда и только тогда, когда .

2) Граф является деревом тогда и только тогда, когда Любые Две его вершины соединены единственной Простой цепью.

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

Решение. Рассмотрим граф, соответствующий клетчатому полю M на N, M = 50, N = 600. Число вершин графа равно
= . Число ребер графа равно
= . Сетка не распадётся до тех пор, пока соответствующий ей граф с вершинами и рёбрами будет связным. По условию задачи , а уменьшается. Пока связный граф содержит циклы, можно, не нарушая связности, удалять любое ребро цикла. Процесс продолжается до тех пор, пока не получится связный граф без циклов, то есть дерево. Дерево с вершинами имеет рёбер. Значит, можно удалить верёвочек. □

Теорема 24. Число Различных деревьев, которые можно построить на P занумерованных вершинах непустого графа, имеющего не менее двух вершин, равно .

Например, число различных деревьев, которые можно построить на четырёх занумерованных вершинах графа, представленного на рис. 1, равно 16.

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

Каждая компонента связности леса является деревом.

Например, на рис. 21 представлена диаграмма леса, имеющего две компоненты связности.

Рис. 21. Диаграмма леса

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

Такой граф называется нагруженным. Вес графа равен сумме весов его ребер.

Например, на рис. 22 представлены нагруженный граф и его остовное дерево наименьшего веса.

Рис. 22. Нагруженный граф и его остовное дерево наименьшего веса

Задачи и упражнения

54. Постройте диаграммы графов, заданных следующими матрицами смежности. Установите, являются ли эти графы деревьями.

1) ; 2) .

55. Дерево имеет три вершины степени 3 и четыре вершины степени 2. Остальные вершины дерева имеют степень 1. Сколько вершин дерева имеет степень 1?

56. Найдите все различные деревья графа .

57. Постройте диаграмму леса с семью вершинами и двумя компонентами связности. Найдите число его рёбер.

58. Найдите цикломатическое число дерева задачи 55.

59. В шахматном турнире по олимпийской системе участвуют 8 человек. Сколько всего встреч будет проведено?

Читайте также: