Концевые вершины и ребра
55. Дерево с корнем. Ветви.
Произвольно зафиксируем некоторую вершину дерева и назовем ее корнем дерева. Само дерево в этом случае будем называть деревом с корнем или корневым деревом.
Иногда полезно, руководствуясь какими–либо соображениями, выделять в дереве некоторую определенную цепь , которую обычно называют стволом дерева. Корень дерева обычно является одной из концевых вершин ствола. Каждая концевая вершина дерева связана с ближайшей вершиной ствола единственной цепью. Эту цепь называют ветвью дерева, выходящей из вершины в вершину . При отсутствии у дерева ствола, ветвями дерева называют цепи, связывающие концевые вершины дерева с его корнем.
56.Типы вершин дерева
Рассмотрим дерево с вершинами. Назовем его концевые вершины вершинами типа 1. Теперь удалим все вершины типа 1 и концевые ребра. В результате получим связный граф без циклов , то есть опять дерево, но с уже меньшим количеством вершин. Концевые вершины дерева назовем вершинами типа 2 в дереве . Аналогично определяются вершины типов 3, 4 и т. д. Легко видеть, что дерево может иметь либо одну вершину максимального типа, либо две таких вершины. Типы вершин дерева , изображенного на рис. 4. 37, записаны рядом с соответствующими вершинами. Здесь же показаны последовательные этапы процедуры, позволяющей их определить. Это дерево имеет две вершины максимального типа. Если у дерева удалить одну из вершин типа 2 и ребра, ей инцидентные, то получившееся при этом дерево будет иметь уже только одну вершину максимального типа.
57. Центры деревьев
Эксцентриситет e(xi) вершины в связном графе G определяется как max{d(xi,xj)}, xj є V. Радиусом графа r(G) называется наименьший из эксцентриситетов вершин. Вершина xi называется центральной вершиной графа, если e(xi) = r(G). Центр графа – это множество центральных вершин.
Теорема: Каждое дерево имеет центр, состоящий из одной вершины или из двух смежных вершин.
Доказательство:
Утверждение очевидно для деревьев с
одной и двумя вершинами. Покажем, что у
любого другого дерева T те же центральные
вершины, что и у дерева T’, полученного
из T удалением всех его висячих вершин.
Расстояние от данной вершины дерева u
до любой другой вершины v достигает
наибольшего значения, когда v – висячая
вершина. Таким образом, эксцентриситет
каждой вершины дерева T’ точно на единицу
меньше эксцентриситета этой же вершины
в дереве T, следовательно, центры этих
деревьев совпадают. Продолжим процесс
удаления и получим требуемое.
59 Орграфы. Основные понятия.
Орграфом называется пара множеств, элементы первого множества называются вершины, элементы второго называются дугами.
Множество дуг — это множество упорядоченных пар вершин.
(i,j)≠(j,i)
i- начало дуги, j — конец дуги.
Число дуг входящих в вершину — полустепень захода.
Полустепень исхода — число дуг, выходящих из вершины.
Орграф называется простым, если он не имеет параллельных дуг, в противном случае он называется мультиграфом.
62.Деревья
Дерево это совокупность элементов, которые называются узлами (один из них обозначается как корень) и отношений, которые строят иерархическую структуру узлов. Узлы также как и вершины графа могут быть представлены списками, обозначаются обычно буквами. Дерево, как правило, может быть задано рекуррентно. Вершины, которым инцидентно одно ребро называются висячими (или листьями).