Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

Эйлера [7, 15]. Данные выражения являются необходимыми усло-
виями существования плоских графов с заданными наборами чисел
Любому связному плоскому графу G можно поставить в соот-
ветствие двойственный ему связный плоский граф G , определяе-
мый следующим образом: каждой грани графа G соответствует
вершина графа G*, каждому ребру V графа G, являющемуся гра-
ничным для граней z/ и z2, соответствует ребро V* графа G*, соеди-
няющее соответствующие граням z/ и z2 вершины. Понятие двой-
ственного графа тесно связано с понятием двойственности в
линейном программировании [7].
2. Экстремальные пути и контуры на графах
Задачи поиска кратчайших и длиннейших путей на графах
возникают в различных областях управления. Сначала мы рас-
смотрим задачи о кратчайшем пути, затем задачи об экстремаль-
ных контурах.
Задача о кратчайшем пути. Пусть задана сеть из п + 1 вер-
шины, то есть ориентированный граф, в котором выделены две
вершины - вход (нулевая вершина) и выход (вершина с номером
п). Для каждой дуги заданы числа, называемые длинами дуг. Дли-
ной пути (контура) называется сумма длин входящих в него дуг
(если длины дуг не заданы, то длина пути (контура) определяется
как число входящих в него дуг). Задача заключается в поиске
кратчайшего пути (пути минимальной длины) от входа до выхода
сети1.
Известно [7, 15], что для существования кратчайшего пути не-
обходимо и достаточно отсутствия в сети контуров отрицательной
длины.
Предположим, что в сети нет контуров. Тогда всегда можно
пронумеровать вершины таким образом, что для любой дуги (i,j)
имеет место j > i. Такая нумерация называется правильной. Легко
показать, что в сети без контуров всегда существует правильная
нумерация.
' В дальнейшем будем предполагать, что в любую вершину сети можно попасть
из входа, и из любой вершины можно попасть в выход (вершины, не удовлетво-
ряющие этому требованию, можно удалить).
1

 

1 2 3 4 5 6 7 8 9 10 20


Математика