Ориентированное дерево
Cтраница 3
 |
Слияние блоков 1, 7, 8 и 4, 5 разбиения РАЗЕ.| Минимальное стягивающее дерево, построенное алгоритмом Краскала. [31] |
Для наших целей достаточно следующего метода: каждый блок разбиения представляется ориентированным деревом, в котором из каждой вершины существует путь до корня. Корень идентифицирует данный блок. Такое дерево содержит также информацию о своей высоте. [32]
Разработайте алгоритм ( как можно более эффективный) для обращения канонического представления ориентированного дерева в традиционное представление для компьютера с использованием FATHER-связей. [33]
Ясно, что свойства ( а) и ( Ь) из определения ориентированного дерева удовлетворяются. [34]
Верно или нет, что последний элемент / ( Vn j) в каноническом представлении ориентированного дерева всегда является корнем этого дерева. [35]
Действительно, если ориентацию не принимать в расчет, то первые Два и последние два ориентированных дерева на рис. 1 тождественны. [36]
В тексте показано, как, помещая корень в нужную вершину, свободное дерево можно превратить в ориентированное дерево. Следовательно, если имеется ориентированное дерево с корнем R, то его можно сначала превратить в свободное дерево, убрав направления дуг, а затем, установив новые направления, получить ориентированное дерево с корнем в некоторой выбранной вершине. [37]
Но имеется значительно более информативный путь решения этой проблемы, дающей нам новый и компактный способ представления ориентированного дерева. [38]
Доказать, что если ребра полного обыкновенного графа случайным образом ориентированы, то полученный ориентированный граф обязательно содержит ориентированное дерево, которое покрывает этот граф. [39]
Верно или неверно такое утверждение: Направленный граф, удовлетворяющий условиям ( а) и ( Ь) определения ориентированного дерева и не имеющий ориентированных циклов, является ориентированным деревом. [40]
Верно или нет следующее утверждение: Направленный граф с корнем, не содержащий ни циклов, ни ориентированных циклов, является ориентированным деревом. [41]
Условия 700 0 и ац 1 - это не что иное, как условия ( а), ( Ь) определения ориентированного дерева. Если G не является ориентированным деревом, то ( согласно упр. [42]
Суть теоремы D в том, что она указывает простой путь построения эйлеровой цепи в уравновешенном направленном графе, в случае когда дано некоторое ориентированное дерево этого графа. Фактически теорема D дает нам возможность подсчитать точное количество эйлеровых цепей в направленном графе; этот и многие другие важные результаты, основанные на развитых в этом пункте идеях, можно найти в приводимых ниже упражнениях. [43]
Генеалогическое дерево, в котором вершины соответствуют лицам мужского пола, а дуги ориентированы от родителей к детям, представляет собой хорошо известный пример ориентированного дерева. [44]
Верно или неверно такое утверждение: Направленный граф, удовлетворяющий условиям ( а) и ( Ь) определения ориентированного дерева и не имеющий ориентированных циклов, является ориентированным деревом. [45]
Страницы: 1 2 3 4