Деревья — это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.
Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.
дерево
Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.
Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .
Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.
Пример 1
График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.
Примечание. Каждое дерево имеет как минимум две вершины первой степени.
Пример 2
В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.
лес
Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.
пример
Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.
Охватывающие деревья
Пусть G — связный граф, тогда подграф H в G называется остовным деревом в G, если —
- H это дерево
- H содержит все вершины 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 = m – (n – 1) = 7 – (5 – 1) = 3
пример
Пусть ‘G’ — связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».
По сумме теоремы о степени вершин
6 × 3 = 2 | E |
| E | = 9
Схема ранг = | E | — (| V | — 1)
= 9 — (6 — 1) = 4
Теорема Кирхгофа
Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.
пример
Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».