67602

Минимальные пути, (маршруты) в нагруженных орграфах (графах)

Лекция

Математика и математический анализ

Примеры латинских свойств. Не проходить через данную вершину (или через множество вершин). Не проходить через данную дугу (или через множество дуг). Быть простой цепью (или простым контуром). Быть цепью или контуром. Не проходить через каждую вершину более k раз.

Русский

2014-09-12

223.5 KB

2 чел.

Лекция №11

Минимальные пути, (маршруты) в нагруженных орграфах (графах)

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

Числа – вес дуги, (цена дуги).

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

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

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

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

Задачи на min П имеет смысл ставить тогда, когда нет отрицательных замкнутых путей (иначе можно повторять цикл многократно, уменьшая «длину»).

Свойства min путей в нагруженном орграфе

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

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

Доказывается аналогично св-вам ненагруж. графа.

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

Поиск  min пути.

Пусть D=(V,X) – нагр. орграф, V={v1,… vn}, n>1. Введем величины , где i=1,…,n, k=1,2,…,n-1.

Для каждого фиксированного i и k величина  равна длине min пути среди путей из v1 в vi содержащих не более k дуг. Если путей нет, то .

Положим также .

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

Утверждение. При i=2,…,n, k0 выполняется равенство

(Принцип динамического программирования. Использовать его позволяют свойства 2,3 min путей).

Алгоритм Форда-Беллмана нахождения min пути в нагруженном орграфе D из v1 в vi.(i1).

( записываем в виде матрицы, i- строка, k-столбец).

1) Составляем табл. , i=1,…,n, k=0,…,n-1. Если , то пути из v1 в vi нет. Конец алгоритма.

2) Если  то это число выражает длину любого min пути из v1 в vi. Найдем min k11, при котором . По определению  получим, что k1- min число дуг в пути среди всех min путей из v1 в vi.

3) Затем определяем номера i2,…,  такие, что

,

,

. . . . . . . . . . . . .

,

Пример. v1v6 

v1

v2

v3

v4

v5

v6

v1

5

5

2

12

0

0

0

0

0

0

v2

2

7

5

5

5

v3

2

5

3

3

3

3

v4

2

5

4

4

4

4

v5

1

2

2

2

2

2

2

v6

12

12

9

7

7

Путь v1v6

7=5+2 (2-ая стр.)

5=3+2 (3-я стр.)

3=1+2 (5-я стр.)

2=0+2 (1-я стр.)

Путь v1v5v3v2v6

Примеры

Специальные пути в орграфах (маршруты в графах).

Рассмотрим орграфы.

Определение. Свойство называется латинским, если из того, что путь =12, где 1, 2  (множество всех путей в орграфе) обладает свойством , следует, что пути 1, 2 также обладают свойством .

Примеры латинских свойств.

  1.  Не проходить через данную вершину (или через множество вершин).
  2.  Не проходить через данную дугу (или через множество дуг).
  3.  Быть простой цепью (или простым контуром).
  4.  Быть цепью или контуром.
  5.  Не проходить через каждую вершину более k раз.

Определение. Матричный способ перечисления путей в орграфе, обладающих заданным латинским свойством , называют методом латинской комбинации.

Введем бинарную операцию . Пусть 1=v1v2vk (мн-во путей, обладающих свойством ), 2=w1w2wL. Положим

Положим ==.

Введем латинскую матрицу  размерности nn такую, что  - множество путей длины k из vi в vj, обладающих свойством , (, если таких путей нет).

Под результатом комбинации  будем понимать квадратную матрицу C=[cij] порядка n с элементами

(аналогично произведению матриц: строка на столбец).

Утверждение. При любом k1 выполняется

Пример. Найти все простые цепи длины 3 в орграфе D:

     

v1v2

v1v3

v1v2v3

v1v2v4

v1v3v4

v2v3

v2v4

v2v4v1

v2v3v4

v3v4

v3v4v1

v3v4v2

v4v1

v4v2

v4v1v2

v4v1v3

v4v2v3

v1v3v4v2

v1v2v3v4

v2v3v4v1

v2v4v1v3

v3v4v1v2

v4v1v2v3

Дополнение. Найти простые контура длины 4 в том же орграфе (свойство ).

Для этого используем матрицу , полученную при решении предыдущей задачи

v1v2

v1v3

v2v3

v2v4

v3v4

v4v1

v4v2

v1v3v4v2

v1v2v3v4

v2v3v4v1

v2v4v1v3

=

v3v4v1v2

v4v1v2v3

v1v2v3v4v1

v2v3v4v1v2

v3v4v1v2v3

v4v1v2v3v4

Пример 2.


 

А также другие работы, которые могут Вас заинтересовать

83672. Резонансные явления в цепях несинусоидального тока 130 KB
  Как и при синусоидальных токах резонанс на кй гармонике соответствует режиму работы при котором ке гармоники напряжения и тока на входе цепи совпадают по фазе иначе говоря входное сопротивление входная проводимость цепи для кй гармоники вещественно. Для кй гармоники тока можно записать где действующее значение кй гармоники ЭДС. Таким образом при изменении С величина кй гармоники тока будет изменяться от нуля при С=0 до при достигая максимума при резонансе см. Следует отметить что несмотря на то что обычно с ростом...
83673. Переходные процессы в линейных электрических цепях с сосредоточенными параметрами 157.5 KB
  Для цепей с заданными постоянными или периодическими напряжениями токами источников принужденная составляющая определяется путем расчета стационарного режима работы схемы после коммутации любым из рассмотренных ранее методов расчета линейных электрических цепей. общее решение уравнения 2 имеет вид 4 Соотношение 4 показывает что при классическом методе расчета послекоммутационный процесс рассматривается как наложение друг на друга двух режимов принужденного наступающего как бы сразу после коммутации и свободного имеющего...
83674. Способы составления характеристического уравнения 175.5 KB
  Путем исключения из системы уравнений описывающих электромагнитное состояние цепи на основании первого и второго законов Кирхгофа всех неизвестных величин кроме одной относительно которой и записывается уравнение 2; путем использования выражения для входного сопротивления цепи на синусоидальном токе; на основе выражения главного определителя. Согласно первому способу в предыдущей лекции было получено дифференциальное уравнение относительно напряжения на конденсаторе для последовательной RLCцепи на базе которого записывается...
83675. Переходные процессы в цепи с одним накопителем энергии и произвольным числом резисторов 167.5 KB
  Общий подход к расчету переходных процессов в таких цепях основан на применении теоремы об активном двухполюснике: ветвь содержащую накопитель выделяют из цепи а оставшуюся часть схемы рассматривают как активный двухполюсник А эквивалентный генератор см. Совершенно очевидно что постоянная времени здесь для цепей с индуктивным элементом определяется как: и с емкостным как: где входное сопротивление цепи по отношению к зажимам 12 подключения ветви содержащей накопитель энергии. Например для напряжения на конденсаторе в цепи на...
83676. Операторный метод расчета переходных процессов 174.5 KB
  Выделенную из некоторой сложной цепи. Замыкание ключа во внешней цепи приводит к переходному процессу при этом начальные условия для тока в ветви и напряжения на конденсаторе в общем случае ненулевые. Отсюда 2 где операторное сопротивление рассматриваемого участка цепи. Следует обратить внимание что операторное сопротивление соответствует комплексному сопротивлению ветви в цепи синусоидального тока при замене оператора р на .
83677. Некоторые важные замечания к формуле разложения 143.5 KB
  Если при этом в цепи также имеют место другие источники например постоянной Е и экспоненциальной ЭДС и начальные условия для токов в ветвях с индуктивными элементами и напряжений на конденсаторах ненулевые то они должны быть все введены в формулу предварительно умноженными на j поскольку только в этом случае они будут учтены при взятии мнимой части от формулы разложения т. Определение независимых начальных условий путем расчета докоммутационного режима работы цепи. Составление операторной схемы замещения цепи для простых цепей с...
83678. Расчет переходных процессов с использованием интеграла Дюамеля 157.5 KB
  Метод переменных состояния Уравнения элекромагнитного состояния это система уравнений определяющих режим работы состояние электрической цепи. Метод переменных состояния основывается на упорядоченном составлении и решении системы дифференциальных уравнений первого порядка которые разрешены относительно производных т. Количество переменных состояния а следовательно число уравнений состояния равно числу независимых накопителей энергии. К уравнениям состояния выдвигаются два основных требования: независимость уравнений; возможность...
83680. Расчет нелинейных цепей методом эквивалентного генератора 149.5 KB
  Ветвь содержащая нелинейный резистор выделяется из исходной цепи а вся остальная уже линейная схема представляется в виде активного двухполюсника АД. Если необходимо также найти токи в линейной части исходной цепи то после расчета нелинейной схемы на рис. 1б в соответствии с теоремой о компенсации нелинейный резистор заменяется источником ЭДС или тока после чего проводится анализ полученной линейной цепи любым известным методом.