русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Нахождение минимального пути в нагруженном графе.


Дата добавления: 2013-12-23; просмотров: 3419; Нарушение авторских прав


Определение. Граф (орграф) называется взвешенным (нагруженным), если каждой дуге xсоответствует некоторое действительное число s(x).

Взвешенные графы.

Лекция № 10. Сети и потоки в сетях. Задача о максимальном потоке и минимальном сечении. Задача декомпозиции (разрезания) графа.

Условия, определяющие чертёж оригинала.

Если проецировать оригинал на плоскость прямолинейными лучами и условиться о положении наблюдателя то не трудно заметить, что получаемое изображение оригинала будет определяться двумя условиями:

1) При данном положении плоскости и направлении проецирования вид получаемого изображения будет зависеть от положения оригинала относительно плоскости проекции. (Например наши точки могут быть спроецированы в одну точку или как изображение точек А2 и В2);

2) При данном относительном положении плоскости проекции и оригинала вид изображения будет определятся, направлением проецирования при этом проецирование осуществляется параллельными лучами в заданном направлении.

Значение s(x) называется весом. В качестве весов могут выступать длины дуг, пропускная способность, стоимость эксплуатации и т. д. Для любого пути p нагруженного графа обозначим через s(p) сумму весов, входящих в pдуг, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь. Величина s(p) называется длиной пути p. Ранее так называлось количество дуг в пути не нагруженного графа, что соответствует случаю когда все веса равны 1.

Определение. Путь в нагруженном графе из вершины vi в vj , где vi ` vj, называется минимальным, если он имеет минимальную длину среди всех путей из вершины v i в vj.

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

1) Если для x X, s(x) > 0, то любой минимальный путь является простой цепью.



2) Если v1 v2 … vk – минимальный путь, то для любых номеров i, j таких, что 1d i d j d k, путь vi v … v также является минимальным.

3) Если vi … vm vj – минимальный путь среди путей из вершины vi в vj, содержащих не более k+1 дуг, то vi … vm – минимальный путь среди путей из вершины vi в vm, содержащих не более k дуг.

Определение. Назовём орграф нагруженным, если на множестве дуг определена некоторая функция , которую часто называют весовой функцией.

Тем самым и нагруженном орграфе каждой дуге поставлено в соответствие некоторое действительное число . Значение будем называть длиной дуги .

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

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

Рассмотрим задачу поиска минимальных путей в нагруженном орграфе. Для графа поиск минимальных путей производится аналогично.

Замечание. Поиск максимальных путей сводится к поиску минимальных путей заменой знаков весов на противоположные.

Пусть G(V, X) – нагруженный орграф, V={v1, …, vn}, n e 2. Введем величины z, где i = 1, …, n, k = 1, 2, … Для каждых фиксированных i и k величина z равна длине минимального пути среди путей из вершины v1 в vi, содержащих не более k дуг. Если таких путей нет, то z = .

Кроме того, если произвольную вершину vi считать путем из vi в v нулевой длины, то величины z можно ввести также и для k = 0.

Тогда z = 0, z = , i = 2, … , n. (3.12)

Введем в рассмотрение квадратную матрицу C(G) порядка n с элементами

которая называется матрицей длин дуг нагруженного орграфа.

Утверждение. При i = 2, …, n, k e 0 выполняется следующее равенство

z = min ( z + c), (3.13)

1djdn

а при i = 1, k e 0 справедливо равенство

z = min [ 0, min( z + c)]. (3.14)

1djdn

Используя это утверждение можно найти таблицу значений величин z,

где i – номер строки таблицы ( i = 1, …, n ), k + 1 – номер столбца таблицы

( k = 0, …, n-1 ).

Заполнять таблицу начинают с первого столбца (k = 0). Согласно (3.12) z = 0,

z = … = z = .

Затем определяют значения второго столбца (k = 1). По формуле (3.14) z = 0. Остальные элементы второго столбца вычисляются по формуле (3.13).

Затем аналогично определяют элементы третьего столбца (k = 2) и т. д.

Замечание. Таблицу можно “ удлинить “ до необходимого количества столбцов, а не ограничиваться n столбцами.

Рассмотрим алгоритм, позволяющий по матрице длин дуг и таблице величин z, определить минимальный путь в нагруженном орграфе из вершины v1 в любую достижимую вершину vj, причем из всех возможных путей он выделяет путь с наименьшим числом дуг.

Рассмотрим теперь задачу поиска минимальных путей (маршрутов) в нагруженном орграфе (графе). При этом для определенности рассуждения будем проводить для орграфа (для графа они аналогичны).

Пусть - нагруженный орграф, , . Введем величины , где , ..., , , ,... Для каждых фиксированных и величина равна длине минимального пути среди путем из в , содержащих не более дуг; если же таких путей нет, то =. Кроме того, если произвольную вершину считать путем из в нулевой длины, то величины можно ввести также и для , при этом

(1)

Введем также в рассмотрение квадратную матрицу порядка с элементами

которую будем называть матрицей длин дуг нагруженного орграфа.

Следующее утверждение дает простые формулы для вычисления величин .

Утверждение 1.

.



<== предыдущая лекция | следующая лекция ==>
Основной принцип, чтения чертежа понятие вида. | Алгоритм Форда-Беллмана.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.