Деревья и циклы

Нагруженные графы

Образ и прообраз вершины и множества вершин

Пусть ориентированный граф - некоторая вершина .

Обозначим - образ вершины ;

- прообраз вершины ;

- образ множества вершин V₁ ;

- прообраз множества вершин V₁.

Нагруженный граф − ориентированный граф D=(V,X), на множестве дуг которого определена не которая функция , которую называют весовой функцией.

Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).

Рис. 5.

Обозначения: для любого пути П нагруженного ориентированного графа D через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути.

Если выбрать веса равными 1, то придем к ненагруженному графу.

Путь в нагруженном ориентированном графе из вершины v в вершину w, где v¹w, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный маршрут в нагруженном графе.

Введем матрицу длин дуг C(D)=[c_ij] порядка n, причем

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

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

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

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

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

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

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

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

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

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

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

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

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

Утверждение 4.Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Утверждение 5.Пусть G связный граф, а − висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Утверждение 6.Пусть G - дерево с n(G) вершинами и m(G) ребрами. Тогда m(G)=n(G)-1.

Утверждение 7.Пусть G – дерево. Тогда любая цепь в G будет простой.

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

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

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