Теория графов – деревья
Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.
Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.
дерево
Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.
Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .
Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.
Пример 1
График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.
Примечание. Каждое дерево имеет как минимум две вершины первой степени.
Пример 2
В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.
лес
Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.
пример
Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.
Охватывающие деревья
Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –
Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.
пример
В приведенном выше примере G является связным графом, а H является подграфом G.
Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.
Circuit Rank
Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.
Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.
Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.
Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.
пример
Посмотрите на следующий график –
Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.
пример
Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».
По сумме теоремы о степени вершин
Теорема Кирхгофа
Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.
пример
Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».
Источник
Глава 9 методы теории графов
Основоположником теории графов является швейцарский математик Л. Эйлер (1736). В дальнейшем теории графов уделялось малое внимание. Начало бурного развития и практического применения теории графов было положено венгерским математиком Д. Кенигом, который опубликовал в 1936 г. монографию «Теория конечных и бесконечных графов». Российский академик Л. В. Канторович разработал метод решения транспортных задач для их сетевой постановки. В настоящее время имеется большое количество работ по теории графов, включая прикладное направление.
Теория графов используется в исследованиях по экономической географии с целью глубокого познания внутренних взаимосвязей в пространственных структурах и закономерностей их развития.
Простые и лаконичные формы графов неразрывно связаны с глубинной сущностью отображаемых явлений и процессов, позволяют вскрыть неточности, допущенные в ходе теоретических построений. Их можно использовать в классификации объектов.
9.1. Элементы теории графов
Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом (рис. 9.1). Вершины А ·—· В называются смежными (связанными). Граф называется связным, если любая пара его вершин связаны. Граф может состоять только из вершин (нуль-граф). Расположению вершин, длине и форме ребер или дуг не придается значения. Существенно лишь то, какие вершины соединены. Ребра (дуги) графов указывают на соответствие между вершинами в графе. Граф может быть представлен геометрически в виде определенной фигуры или в виде матрицы, в которой для каждой вершины записывается число связанных с ней ребер (дуг).
Нумерованные кружки (см. рис. 9.1) в графах служат его вершинами, которые соединены ребрами – неориентированными линиями (h, i). Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в нем ребер нечетное.
Ориентированное ребро называют дугой (a,e, f, g, j – ), которая может быть входящей в вершину (1 – g) и выходящей из нее (1 – a, e, f). Ребра могут быть инцидентны вершине, если они являются одним из ее концов, а вершина – инцидентна каждому из входящих в нее ребер.
Каждое ребро (дуга) может соединять только две вершины. Если ребро соединяет вершину с ней же самой, то его называют петлей (b, c, d, k). Она имеет овальную форму (0). Это цикл (контур) единичной длины, т.е. образованный одним ребром (дугой), связывающим вершину саму с собой.
Вершины 3 и 5 изолированы, так как они не имеют ни одного инцидентного ей ребра (дуги). Ни одно ребро не соединяет такую вершину с другой. Вершину 3 можно назвать голой, желая подчеркнуть, что при ней нет даже петель, как в вершине 5. Рассмотренный граф содержит конечное множество вершин, но бесконечное множество (континуум) ребер (дуг).
Рис. 9.1.Элементы теории графов
Маршрут представлен в ориентированном графе путем, в неориентированном – цепью (∟), если каждое ребро графа, встречается в нем не более одного раза. Вершины и цепи могут повторяться несколько раз.
Цепь, начальная и конечная вершины которой совпадают, называется контуром (ориентированный граф) и циклом (⌂) (неориентированный граф). Они имеют форму треугольника, многоугольника.
Элементарные пути, цепи, циклы и контуры называют гамильтоновыми, простые – называются эйлеровыми. В элементарные формы графов вершины не включаются более одного раза, в простые – дуги (ребра) не включаются более одного раза. Длина цепи (пути) или цикла (контура) есть число ребер (дуг), которые их образуют.
Число ребер, сходящихся в вершине графа, называется степенью (порядком) s (G, x) вершины х в графе G = (X, U), или число ребер инцидентных этой вершине. При изоморфизме двух графов соответствующие друг другу вершины должны иметь одинаковую степень вершин. Упорядоченную систему степени его вершин называют вектором степеней графа G и кратко обозначают s (G).
Обыкновенным графом G = (X, U) называется упорядоченная пара множеств: конечного непустого Х, элементы которого называют вершинами графа G, и подмножества U , элементы которого называются ребрами этого графа. Граф называется конечным, если множество его ребер конечно. Граф интерпретируется как сеть, а его вершины – узлы. Если линии, соединяющие вершины, не имеют ориентации, то граф называется неориентированным (рис. 9.2, а), при наличии стрелок на линиях граф считают ориентированным, или орграфом (см. рис. 9.2, б, в). Может быть и смешанный граф.
Рис. 9.2.Виды графов:а – неориентированный граф-дерево; б – входящее дерево; в – исходящее дерево; г – псевдограф
Псевдограф содержит петли и кратные ребра (рис. 9.2, г).
Важный класс графов составляют «деревья». Это связный граф, который имеет не менее двух вершин и не имеет циклов (см. рис. 9.2). Ребра графа-дерева называют ветвями. Дерево, все ветви которого имеют общую вершину, называют лагранжевым деревом. Корнем дерева может быть любая вершина, которую выбирают за начальную точку.
Среди ориентированных деревьев различают входящее и выходящее дерево (см. рис. 9.2, б, в). Входящее дерево может быть моделью производственной системы, показывающей, что при изготовлении одного конечного продукта используются несколько видов промежуточной продукции, получаемой из различных видов сырья. Выходящее дерево может быть моделью пространственной системы производства, где за начальную точку принимается стадия добычи комплексного сырья, при переработке которого получают несколько конечных продуктов. Лесом называется несвязный граф, все связные компоненты которого являются деревьями.
Сумма степеней всех вершин неориентированного графа является четным числом, так как каждое ребро соединяет две вершины. Следовательно, число ребер m в графе G (X) равно половине суммы степеней всех его вершин: m = 1 / 2 , где i – индекс вершины, n – число вершин. Эта формула справедлива в случае наличия петель, если они рассматриваются как двойные ребра.
Граф G (X) называется однородным, если степень всех его вершин одинакова. Понятие «однородный граф степени r» означает, что каждая вершина данного графа имеет степень, равную r. В однородных графах степени r число ребер равно: m = (1 / 2) n · r. Примером однородных графов являются правильные многогранники: тетраэдр, куб, октаэдр.
Под цикломатическим числом понимается число независимых циклов графе. К независимым относятся циклы, не имеющие ни одного общего ребра с другими циклами графа. К зависимым относятся циклы, у которых имеются общие ребра.
Матрица графов строится следующим образом. Ряды и столбы матрицы представлены вершинами графа. В каждый рядок или столбец вносится количество инцидентных ребер для каждой вершины или кратчайших расстояний между вершинами и т. д. Затем производятся соответствующие расчеты степеней, индексов.
Источник