что такое теория графов
Теория Графов. Часть 1 Введение и классификация графов
«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена
Введение
Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.
Схема Московского метро
Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.
Отмечу, что число вершин обозначается буквой n:
Число рёбер обозначается буквой m:
Таким образом граф задается и обозначается парой V,E:
Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)
Неформально граф является совокупностью точек и линий. Линии в котором задаются парой вершин, расположенных не важно в каком порядке.
Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.
Нулевой граф
Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.
Множество E задается парой неупорядоченных вершин множества V.
Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =
Граф будет выглядеть следующим образом:
Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.
Степень записывают, как:
Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:
Формула суммы степеней для G = V,E выглядит так:
То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!
А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:
Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?
Классификации графов
Первым признаком классификации является отсутствие или наличие ориентации у ребер.
Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.
Неориентированный граф
Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.
Ориентированный граф
Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.
Смешанный граф
Вторым признаком является отсутствие или наличие кратных ребер.
Мультиграф
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.
Теория графов: основные понятия и задачи. Графы как структура данных
Что такое теория графов и что такое граф?
А теперь строгие математические определения графа.
Определение 1. Графом называется система объектов произвольной природы (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов.
Слово граф греческого происхождения, от слов «пишу», «описываю». Из начала этой статьи известно, что именно описывает граф: описывает он отношения. То есть, любой граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Основные понятия теории графов
А многие виды графов определяются тем, какие виды рёбер и/или вершин эти графы содержат. На этом основаны и понятия ориентированного и неориентированного графов, которыми обязан владеть каждый освоивший дискретную математику вообще и теорию графов. Есть также графы, которые определяются некоторыми специфическими принципами построения, например, двудольные графы, которые разобраны на этом уроке в параграфе с задачами, а также на всё том же уроке о видах графов.
Понятие инцидентности необходимо и при составлении алгоритмов решения многих практических задач с графами. Например, можно ознакомиться с программной реализацией обхода в глубину графа, представленного матрицей инцидентности. Идея проста: можно двигаться лишь через вершины, соединённые рёбрами. А уж если рёбрам приписаны какие-то значения («весы», чаще всего в виде чисел, такие графы называются взвешенными или помеченными), то можно решать сложные прикладные задачи, некоторые из которых упомянуты в завершающем параграфе этого урока.
Классические задачи теории графов и их решения
Задачу можно смоделировать следующим образом: к каждому участку суши прикрепляется одна точка, а две точки соединяются линией тогда и только тогда, когда соответствующие участки суши соединены мостом (рисунок ниже, соединительные линии начерчены пунктиром). Таким образом, построен граф.
Ответ Эйлера на вопрос задачи состоит в следующем. Если бы у этой задачи было положительное решение, то в получившемся графе существовал бы замкнутый путь, проходящий по рёбрам и содержащий каждое ребро только один раз. Если существует такой путь, то у каждой вершины должно быть только чётное число рёбер. Но в получившемся графе есть вершины, у которых нечётное число рёбер. Поэтому задача не имеет положительного решения.
В 1847 г. Кирхгоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом контуре электрической цепи. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления, конденсаторы, индуктивности и т.д., он рассматривал соответствующие комбинаторные структуры, содержащие только вершины и связи (рёбра или дуги), причём для связей не нужно учитывать, каким типам электрических элементов они соответствуют. Таким образом, Кирхгоф заменил каждую электрическую цепь соответствующим графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый цикл графа электрической цепи.
Кэли в 1858 г., занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемых деревьями. Он стремился перечислить изомеры насыщенных углеводородов, с данным числом атомов углерода. Кэли прежде всего сформулировал задачу абстрактно: найти число всех деревьев с p вершинами, каждое из которых имеет вершины со степенями 1 и 4. Ему не удалось сразу решить эту задачу, и он стал изменять её формулировку таким образом, чтобы можно было решить новую задачу о перечислении:
Задачи с графами для закрепления основных понятий
Решение. В этом примере часть рёбер будут иметь направление, а некоторые не будут, то есть строим смешанный граф. Перечислим отношения на множестве: 4 делится нацело на 2, 6 делится нацело на 2, 14 делится нацело на 2, и ещё каждое число из этого множества делится нацело на само себя. Это отношение, то есть когда число делится нацело на само себя, будем отображать в виде рёбер, которые соединяют вершину саму с собой. Такие рёбра называются петлями. В данном случае нет необходимости давать направление петле. Таким образом, в нашем примере три обычных направленных ребра и четыре петли. Получаем следующий граф:
Пример 3. Пусть даны множества A = <α, β, γ>и B =
Решение. Как известно из определения декартова произведения множеств, в нём нет упорядоченных наборов из элементов одного и того же множества. То есть в нашем примере нельзя соединять греческие буквы с греческими и латинские с латинскими. Этот факт отображается в виде двудольного графа, то есть такого, в котором вершины разделены на две части так, что вершины, принадлежащие одной и той же части, не соединены между собой. Получаем следующий граф:
Пример 4. В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пётр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений «Игорь работает с объектами О4, О7», «Сергей работает с объектами О1, О2, О3, О5, О6», «Пётр работает с объектом О8».
Решение. Граф, отображающий данные отношения, будет так же двудольным, так как менеджер не работает с менеджером и объект не работает с объектом. Однако, в отличии от предыдущего примера, граф будет ориентированным. В самом деле, например, Игорь работает с объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость давать рёбрам направления может показаться «математической тупостью». Но всё же, и это вытекает из строгого характера математики, если отношение носит односторонний характер, то давать направления рёбрам нужно. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для планирования, где тоже применяются графы и маршрут по вершинам и рёбрам должен проходить строго в заданном направлении. Итак, получаем следующий ориентированный двудольный граф:
И вновь к примерам с числами.
Пример 5. Пусть задано множество C = <2, 3, 5, 6, 15, 18>. Построить граф, реализующий отношение, определяющее все пары чисел a и b из множества C, у которых при делении второго элемента на первый получаем частное, которое является целым числом больше 1.
Как мы уже знаем из теоретической вступительной части, теория графов не учитывает специфическую природу множеств и с помощью одного и того же графа можно задать отношения на множествах с самым разным содержанием. То есть, от этого самого содержания при моделировании задачи можно абстрагироваться. Перейдём к примерам, иллюстрирующим это замечательное свойство теории графов.
Пример 6. На кусочке шахматной доски размером 3 Х 3 размещены два белых коня и два чёрных коня так, как показано на рисунке ниже.
Можно ли переместить коней в состояние, которое изображено на следующем рисунке, не забывая, что две фигуры не могут находиться на одной клетке?
И всё же конструкция получилась громозкой. В ней видны клетки шахматной доски, а многие рёбра графа пересекаются. Нельзя ли абстрагироваться от физического вида шахматной доски и вообразить отношения проще? Оказывается, можно. В новом графе соседними вершинами будут те, которые связаны отношением «ход коня», а не соседние по шахматной доске (рисунок ниже).
Пример 7. Задача о волке, козе и капусте. На одном берегу реки находятся человек (Ч), лодка, волк (В), коза (Кз) и капуста (Кп). В лодке одновременно могут находиться человек и не более одного из перевозимых объектов. Человек должен перевезти на другой берег все объекты, соблюдая условие: нельзя оставлять без присмотра волка вместе с козой и козу вместе с капустой.
Разместим вершины графа так, чтобы рёбра не пересекались, а соседними были вершины, которые связаны отношением на графе. Тогда увидеть отношения будет намного проще (для увеличения рисунка щёлкните по нему левой кнопкой мыши):
Как видим, существуют два различных непрерывных маршрута из начальной конфигурации в конечную. Поэтому задача имеет два различных решения (и оба правильные).
Теория графов и важнейшие современные прикладные задачи
На основе теории графов разработаны методы решения прикладных задач, в которых в виде графов моделируются весьма сложные системы. В этих моделях узлы содержат отдельные компоненты, а рёбра отображают связи между компонентами. Обычно для моделирования транспортных сетей, систем массового обслуживания, в сетевом планировании используются взвешенные графы. Мы о них уже говорили, это графы, в которым дугам присвоены весы.
Графы-деревья применяются, например, для построения деревьев решений (служат для анализа рисков, анализа возможных приобретений и убытков в условиях неопределённостей). С применением теории графов разработаны и другие многочисленные математические модели для решения задач в конкретных предметных областях.
Графы и задача о потоках
Постановка задачи. Имеется система водопроводных труб, представленная графом на рисунке ниже.
Для решения задачи о потоках можно воспользоваться методом Форда-Фулкерсона. Идея метода: поиск максимального потока производится по шагам. В начале работы алгоритма поток полагается равным нулю. На каждом последующем шаге значение потока увеличивается, для чего ищется дополняющий путь, по которому поступает дополнительный поток. Эти шаги повторяются до тех пор, пока существуют дополнительные пути. Задача успешно применяется в различных распределённых системах: система электоснабжения, коммуникационная сеть, система железных дорог и других.
Графы и сетевое планирование
В задачах планирования сложных процессов, состоящих из множества работ, часть из которых выполняется параллельно, а часть последовательно, широкое применение получили взвешенные графы, известные под названием сети ПЕРТ (PERT).
Путь максимальной длины между этими вершинами графа (из начала в конец процесса выполнения работ), называется критическим путём. Для сокращения времени выполнения всего комплекса работ необходимо найти работы, лежащие на критическом пути, и уменьшить их продолжительность за счёт, например, привлечения дополнительных исполнителей, механизмов, новых технологий.
Теория графов. Основные понятия и виды графов
Статья находится на проверке у методистов 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
