Что такое смежные вершины
Ключевые термины
Дата добавления: 2015-06-12 ; просмотров: 7194 ; Нарушение авторских прав
Вес (длина) ребра – это число или несколько чисел, которые интерпретируются по отношению к ребру как длина, пропускная способность.
Вес вершины – это число (действительное, целое или рациональное), поставленное в соответствие данной вершине.
Взвешенный граф – это граф, каждому ребру которого поставлен в соответствие его вес.
Граф – это совокупность двух конечных множеств: множества точек и множества линий, попарно соединяющих некоторые из этих точек.
Вершины (узлы) графа – это множество точек, составляющих граф.
Замкнутый маршрут – это маршрут в графе, у которого начальная и конечная вершины совпадают.
Кратные ребра – это ребра, соединяющие одну и ту же пару вершин.
Маршрут в графе – это конечная чередующаяся последовательность смежных вершин и ребер, соединяющих эти вершины.
Матрица инцидентности – это двумерный массив, в котором указываются связи между инцидентными элементами графа (ребро и вершина).
Матрица смежности – это двумерный массив, значения элементов которого характеризуются смежностью вершин графа
Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.
Неориентированный граф (неорграф) – это граф, у которого все ребра неориентированы, то есть ребрам которого не задано направление.
Обход графа (поиск на графе) – это процесс систематического просмотра всех ребер или вершин графа с целью отыскания ребер или вершин, удовлетворяющих некоторому условию.
Ориентированный граф (орграф) – это граф, у которого все ребра ориентированы, то есть ребрам которого присвоено направление.
Открытый маршрут – это маршрут в графе, у которого начальная и конечная вершины различны.
Петля – это ребро, соединяющее вершину саму с собой.
Поиск в глубину – это обход графа по возможным путям, когда нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными).
Поиск в ширину – это обход графа по возможным путям, когда после посещения вершины, посещаются все соседние с ней вершины.
Простой граф – это граф, в котором нет ни петель, ни кратных ребер.
Путь – это открытая цепь, у которой все вершины различны.
Ребра (дуги) графа – это множество линий, соединяющих вершины графа.
Связный граф – это граф, у которого для любой пары вершин существует соединяющий их путь.
Смежные вершины – это вершины, соединенные общим ребром.
Смешанный граф – это граф, содержащий как ориентированные, так и неориентированные ребра.
Список ребер – это множество, образованное парами смежных вершин
Тупик – это вершина графа, для которой все смежные с ней вершины уже посещены
Цепь – это маршрут в графе, у которого все ребра различны.
Цикл – это замкнутая цепь, у которой различны все ее вершины, за исключением концевых.
Не нашли то, что искали? Google вам в помощь!
Теория Графов. Часть 2 Смежность, инцидентность, петли
Ничего не сделано, если что-то осталось недоделанным. – Иоганн Гаусс
Смежность и инцидентность
Смежность и инцидентность
Давайте рассмотрим самый обыкновенный неориентированный граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК.
Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.
Рисунок 1
Смежностью вершин графа – называется отношение между двумя вершинами, в котором существует ребро их соединяющее.
Инцидентность – это когда вершина a является началом или концом ребра t. Если мы добавим еще одну вершину b, то мы скажем, что вершина a и b инцидента ребру t.
Кроме вершин, смежность присутствует и у рёбер. Рёбра просто должны иметь общую вершину. В нашем случаи мы можем сказать, что ребро ДК является смежным ребру РК, так как у них есть общая вершина К.
Смежностью рёбер графа – называется отношение между двумя рёбрами, в котором существует вершина соединяющая их.
В связи с тем, что выше мы рассматривали неориентированный граф, то было неважно, с какого направления определять смежность и инцидентность. Вершина Р могла быть смежна вершине К, но также мы могли сказать, что вершина К смежна вершине Р.
В ориентированном графе все немного по-другому (Рисунок 2), так у нас имеется направление, которое мы не в силах поменять. Если вершина 1 смежна вершине 2, то вершина 2 не может быть смежна вершине 1. То же самое касается и инцидентности. Вершины 1 и 2 инцидентны ребру 12, наоборот не работает.
Рисунок 2
Петли
Петля – это ребро инцидентное одной и той же вершине. То есть вершина которая соединена сама с собой. На рисунке ниже мы видим, как это выглядит.
Петли
Заключение
В следующей статье я покажу, как с помощью матрицы задавать графы, а также покажу, что такое вес ребра.
Многоугольник
Определение 1. Многоугольник − замкнутая ломаная линия.
Объединение многоугольника и ограниченной им части плоскости также называют многоугольником. Поэтому представим другое определение многоугольника:
Определение 2. Многоугольник − это геометрическая фигура, которая является частю плоскости, ограниченная замкнутой ломаной.
Вершины ломаной называются вершинами многоугольника. Звенья ломаной называются сторонами многоугольника.
Любой многоугольник разделяет плоскость на две части, одна из которых называется внутренней областью многоугольника, а другая внешней областью многоугольника.
Виды многоугольников
Многоугольник с тремя вершинами называется треугольником, с четыремя вершинами − четырехугольником, с пяти вершинами − пятиугольником, и т.д. Многоугольник с \( \small n \) вершинами называется \( \small n- \)угольником.
    |
На рисунке 1 представлены различные виды многоугольников.
Обозначение многоугольника
Обозначают многоугольник буквами, стоящих при его вершинах. Называют многоугольник чередовав буквы при его вершинах по часовой стрелке или против часовой стрелки. Например, многоугольник на рисунке 2 называют \( \small A_1A_2A_3A_4A_5A_6 \) или \( \small A_6A_5A_4A_3A_2A_1 \).
Соседние вершины многоугольника
Вершины многоугольника называются соседними, если они являются концами одной из его сторон.
 |
На рисунке 2 вершины \( \small A_2 \) и \( \small A_3 \) являются соседними, так как они являются концами стороны \( \small A_2A_3. \)
Смежные стороны многоугольника
Стороны многоугольника называются смежными, если они имеют общую вершину.
На рисунке 2 стороны \( \small A_4A_5 \) и \( \small A_5A_6 \) являются смежными, так как они имеют общую вершину \( \small A_5. \)
Простой многоугольник. Самопересекающийся многоугольник
Многоугольник называется простым, если его несмежные стороны не имеют общих точек (внутренних или концевых).
  |
На рисунке 3 изображен простой многоугольник так как стороны многоугольника не имеют самопересечений. А на рисунке 4 многоугольник не является простым, так как стороны \( \small A_1A_4 \) и \( \small A_2A_3 \) пересекаются. Такой многоугольник называется самопересекающийся многоугольник.
Выпуклый многоугольник
Многоугольник называется выпуклым, если она лежит по одну сторону от прямой, проходящей через любую его сторону.
 |
На рисунке 5 многоугольник лежит по одну сторону от прямых \( \small m, \ n, \ l, \ p, \ q, \ r\) проходящих через стороны многоугольника.
 |
На рисунке 6 прямая \( \small m\) делит многоугольник на две части, т.е. многоугольник не лежит по одну сторону от прямой \( \small m\). Следовательно многоугольник не является выпуклым.
Правильный многоугольник
Простой многоугольник называется правильным, если все его стороны равны и все углы равны. Например равносторонний треугольник является правильным многоугольником, поскольку все его стороны равны, и все его углы равны 60°. Квадрат является правильным многоугольником, так как все его стороны равны и все его углы равны 90°.
  |
На рисунке 7 изображен правильный многоугольник (пятиугольник), так как у данного многоугольника все стороны равны и все углы равны. Многоугольник (ромб) на на рисунке 8 не является правильным, так как все стороны многоугольника равны, но все углы многоугольника не равны друг другу. Прямоугольник также не является правильным многоугольником, так как несмотря на то, что все углы прямоугольника равны, но все четыре стороны прямоугольника не равны друг другу.
Звездчатый многоугольник
Самопересекающийся многоугольник, все стороны которого равны и все углы равны, называется звездчатым или звездчато-правильным.
 |
На рисунке 9 представлен звездчатый пятиугольник поскольку все углы \( \small A_1, \ A_2, \ A_3, \ A_4, \ A_5 \) равны и равны все стороны: \( \small A_1A_2=A_2A_3=A_3A_4=A_4A_5=A_5A_1. \)
Периметр многоугольника
Сумма всех сторон многоугольника называется периметром многоугольника. Для многоугольника \( \small A_1A_2. A_
Угол многоугольника
Углом (внутренним углом) многоугольника при данной вершине называется угол между двумя сторонами многоугольника, сходящимися к этой вершине. Если многоугольник выпуклый, то все углы многоугольника меньше 180°. Если же многоугольник невыпуклый, то он имеет внутренний угол больше 180° (угол \( \small A_3 \) на рисунке 2).
Внешний угол многоугольника
Внешним углом многоугольника при данной вершине называется угол смежный внутреннему углу многоугольника при данной вершине.
На рисунке 10 угол 1 является внешним углом данного многоугольника при вершине \( \small E. \)
Диагональ многоугольника. Количество диагоналей
Диагоналями называют отрезки, соединяющие две несоседние вершины многоугольника.
Выведем форулу вычисления количества диагоналей многоугольника. Пусть задан \( \small n \)-угольник. Выберем одну вершину многоугольника и проведем мысленно все отрезки, соединяющие эту вершину с остальными вершинами. Получим \( \small n-1 \) отрезков. Но поскольку две вершины для выбранной вершины являются соседними, а по определнию диагональ − это отрезок соединяющий несоседние вершины, то из \( \small n-1 \) вычтем 2. Получим \( \small n-3 \). Всего \( \small n \) вершин. Следовательно количество вычисленных диагоналей будет \( \small n(n-3). \) Учитывая, что каждый диагональ − это отрезок соединяющий две вершины, то получится, что мы вычислили каждый диагональ дважды. Поэтому полученное число нужно делить на два. Получим количество диагоналей \( \small n- \)мерного многоугольника:
Сумма углов выпуклого многоугольника
Выведем формулу вычисления суммы углов выпуклого многоугольника. Для этого проведем из вершины \( \small A_1 \) все диагноали многоугольника \( \small A_1A_2. A_
 |
Количество диагоналей, проведенной из одной вершиы, как выяснили из предыдующего параграфа равно \( \small n-3 \). Следовательно, эти диагонали разделяют многоугольник на \( \small n-3+1=n-2 \) треугольников. Поскольку сумма углов треугольника равна 180°, то получим, что сумма углов выпуклого многоугольника равна: \( \small 180°(n-2). \)
где \( \small n \) −количество сторон (вершин) выпуклого многоугольника.
Угол правильного многоугольника
Поскольку у правильного многоугольника все углы равны, то используя формулу (1) получим угол правильного многоугольника:
где \( \small n \) −количество сторон (вершин) правильного многоугольника.
смежные вершины
1 adjacent vertices
2 adjacent nodes
3 adjacent nodes
4 adjacent vertices vertex
5 adjacent vertices
6 adjacent nodes
Тематики
7 chromatic number
хроматическое число
Число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется хроматическим порядка р. Минимальное число р, при котором граф является хроматическим порядка р, называется хроматическим числом данного графа. Оно находится с помощью аналитического метода, основанного на обычных приемах линейного программирования.
[ http://slovar-lopatnikov.ru/]
Тематики
8 баланс вершины
9 высота вершины
10 глубина вершины
11 затупление вершины трещины
12 звезда вершины
13 наклон вершины импульса
14 номер вершины
15 обозначение вершины
16 перекос вершины
17 радиус закругления вершины
18 смежные деревья
19 смежные дуги
20 смежные здания
См. также в других словарях:
смежные вершины (узловые точки) — — [http://slovarionline.ru/anglo russkiy slovar neftegazovoy promyishlennosti/] Тематики нефтегазовая промышленность EN adjacent nodes … Справочник технического переводчика
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Подграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Простой путь в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Путь в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Теория графов. Основные понятия и виды графов
Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Курсы обучения математике помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
