Остовное дерево

Cтраница 3

Мы уже видели, как в задаче построения остовного дерева, описанной в примере 4.1, естественно возникает последовательность основных операций ОБЪЕДИНИТЬ и НАЙТИ. В этом разделе мы познакомимся с несколькими другими задачами, которые приводят к последовательностям операций ОБЪЕДИНИТЬ и НАЙТИ. [31]

Задача нахождения транзитивных зависимостей тесно связана с поиском остовного дерева графа. Соответствующий алгоритм будет рассмотрен в следующей главе. [32]

Именно с выделением в схеме цепи того или иного остовного дерева ( или каркаса), соединяющего все его т узлов ( будем называть его просто деревом), связаны в основном процедуры разбиения переменных на отдельные группы, матриц - на блоки, а также и выбора системы линейно-независимых ( т.е. несводимых друг к другу посредством их линейных комбинаций) контуров. [33]

В этих задачах от Вас требуется сравнить два остовных дерева или два пути. Такое сравнение провести легче, если обозначать ребра парой вершин в порядке возрастания их меток. Это возможно, поскольку работать придется с неориентированными графами. [34]

Орграф элементарного представителя топологии ( г, t ( 3, 1.| Набор разрезов ( коциклов ( штриховые линии для включающего ребра 1, 2, 3 остова орграфа, изображенного на. [35]

С ( рис. III.14), отвечающей некоторому выбранному остовному дереву графа [47, 176], ребра которого занумерованы числами от 1 до v - 1, а хорды - от v до и. Эти уравнения следуют из того факта, что сумма векторов ( г - Тр) по ребрам каждого контура равна нулю. Чтобы переписать (III.94) в матричном виде, отбросим от матрицы ее правую часть - единичную матрицу, затем поменяем знак оставшейся части и добавим к ней сверху новую единичную матрицу. [36]

Доказать, что в любом связном графе G существует остовное дерево, диаметр которого не более чем в два раза превосходит диаметр графа. [37]

Начнем с произвольной вершины графа и включим ее в остовное дерево. Все вершины, соединенные с данной, заносим в кайму. Затем выполняется цикл поиска ребра с наименьшим весом, соединяющего уже построенную часть остовного дерева с каймой; это ребро вместе с новой вершиной добавляется в дерево и происходит обновление каймы. После того, как в дерево попадут все вершины, работа будет закончена. [38]

В этом случае, исключив ребро lhe, получим новое остовное дерево, содержащее wst, длина которого не больше прежнего КОД. Следовательно, в случае (8.8) существует не единственное КОД, а ребро lst принадлежит по крайней мере одному из них. [39]

Остовные деревья графа G. [40]

На языке теории графов нам нужно в нагруженном графе найти остовное дерево наименьшего общего веса. Такое дерево принято называть минимальным остовным деревом или, сокращенно, МОД. В отличие от задачи коммивояжера, здесь есть эффективный алгоритм, находящий действительно минимальное остовное дерево. Он похож на алгоритм Прима, с которым мы познакомились в главе 1 при решении задачи поиска кратчайшего соединения для набора из шести шотландских городов. [41]

Каждому помеченному дереву с п вершинами соответствует ( единственным образом) остовное дерево графа Кп, обратно, каждое остовное дерево графа К ц представляет единственное помеченное дерево с п вершинами. [42]

В этом разделе предполагается, что читатель знаком с алгоритмами отыскания остовного дерева наименьшего веса для неориентированного графа со взвешенными ребрами. В действительности будет отыскиваться остовное дерево наибольшего веса, но поскольку все остовные деревья данного графа имеют одно и то же множество вершин, то нужный алгоритм может быть получен из алгоритма нахождения остовного дерева наименьшего веса с помощью перемены знака у весов ребер на противоположный. [43]

Если в орграфе присутствует больше одной корневой вершины, то не существует остовного дерева. [44]

Впрочем, имеется способ спасти кое-что из этого очаровательного комбинаторного условия, привлекающего остовное дерево. Можно утверждать, что ситуация, изображенная на рис. 11.1.1, никогда не возникнет в реальной жизни, так как эти два ребра графа представляют два разных устройства и, если R и - R являются физическими параметрами, соответствующими этим устройствам, то они никогда не будут в точности одинаковыми. Если они хотя бы чуть-чуть отличаются, то система будет на самом деле иметь единственное решение. [45]

Страницы: 1 2 3 4