Главная | Обратная связь

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для любой дуги , то любой минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для " i,j : путь (маршрут) тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) из x в y, содержащих не более k+1 дуг (ребер), то − минимальный путь (маршрут) из x в u среди путей (маршрутов), содержащих не более k дуг (ребер).

 

Деревья

Неориентированным деревом(или просто деревом) называется связный граф без циклов.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.

Число − цикломатическое число графа G.

Граф G называется лесом если все его компоненты связности - деревья.

Свойства деревьев:

Следующие утверждения эквивалентны:

1) Граф G есть дерево.

2) Граф G является связным и не имеет простых циклов.

3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

4) " две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

Корневые деревья находят многочисленные применения при представлении иерархических структур данных. Поэтому возникает необходимость экономного представления структуры корневых деревьев в памяти ПК. Наиболее эффективным является так называемое бинарное представление корневых деревьев.

Каждому плоскому корневому дереву с т ребрами можно взаимно однозначно сопоставить двоичный вектор длины 2m, называемый кодом дерева. Код плоского корневого дерева определим по индукции.

Базис индукции. Дереву с одним ребром (см. рис. 27, а) сопоставим вектор 01.

Индуктивный переход. Если дереву А (см. рис. 27, б) сопоставлен вектор α, а дереву В (см. рис. 27, в) — вектор β, то дереву С (см. рис. 27, г) сопоставляется вектор αβ, а дереву D (см. рис. 27, д) сопоставлен вектор 0α1.

Рис. 27.

Пример. Дереву, изображенному на рис. 28, а, сопоставляется вектор 001001010111.

Рис. 28

Отметим, что код дерева с m ребрами является двоичным вектором, обладающим следующими двумя свойствами.

1. Число нулей в векторе α совпадает с числом единиц.

2. Для любого k≤2m число единиц среди первых k координат набора α не превосходит числа нулей среди тех же k координат.

Восстановить дерево по коду можно следующим образом.

Базис индукции. Вектору 01 сопоставляем дерево с одним ребром (см. рис. 27, а). Такое плоское дерево единственно, поскольку все однореберные плоские корневые деревья одинаковы.

Индуктивный переход. Пусть дан вектор α с 2m координатами (m > 1), обладающий свойствами 1 и 2. Пусть k — наименьшее четное число такое, что вектор β, состоящий из первых k координат набора α, удовлетворяет свойству 1. Если k < 2m, рассмотрим еще вектор γ, составленный из координат αk+1,…,αm набора α. Тогда, поскольку плоские корневые деревья Аи В, кодами которых являются соответственно наборы β и γ, определены однозначно в силу предположения индукции, то можно однозначно сопоставить вектору α дерево, показанное на рис. 27, г. Если же k = 2m, то пусть δ — вектор, полученный из α отбрасыванием первой и последней координат. Нетрудно убедиться, что вектор δ также обладает свойствами 1, 2. Тогда в силу предположения индукции вектору δ соответствует единственное плоское дерево А. Сопоставим вектору α плоское дерево, изображенное на рис. 27, д.

Код плоского корневого дерева можно получить также с помощью обхода: при обходе дерева, начиная с корня, мы проходим каждое ребро дважды (см. рис. 28, б). Первый проход вдоль ребра отмечаем нулем, а второй — единицей. В результате получаем тот же самый код дерева, что и при индуктивном способе построения.