Головна

доведення коректності

Нехай l (v) - довжина найкоротшого шляху з вершини a у вершину v. Доведемо по індукції,

що в момент відвідування будь-якої вершини z, d (z) = l (z).

база. Першою відвідується вершина a. У цей момент d (a) = l (a) = 0.

крок. Нехай ми вибрали для відвідування вершину z! = A. Доведемо, що в цей момент d (z) = l (z).

Для початку зазначимо, що для будь-якої вершини v, завжди виконується d (v)> = l (v)

(Алгоритм не може знайти шлях коротше, ніж найкоротший з усіх існуючих).

Нехай P - найкоротший шлях з a в z, y - перша невідвіданих вершина на P, x -

попередня їй (отже, відвіданих). Оскільки шлях P найкоротший, його частина,

провідна з a через x в y, теж найкоротша, отже l (y) = l (x) + w (xy). за

припущенням індукції, в момент відвідування вершини x виконувалося d (x) = l (x),

отже, вершина y тоді отримала мітку не більш ніж d (x) + w (xy) = l (x) + w (xy) = l (y).

Отже, d (y) = l (y). З іншого боку, оскільки зараз ми вибрали вершину z, її

мітка мінімальна серед невідвіданих, тобто d (z) <= d (y) = l (y) <= l (z). комбінуючи це

з d (z)> = l (z), маємо d (z) = l (z), що й треба було довести. оскільки алгоритм

закінчує роботу, коли всі вершини відвідані, в цей момент d = l для всіх вершин.


19. Мережі та потоки. Величина потоку і його властивості (сума потоків з джерела = сумі потоків в стік). Завдання про знаходження максимального потоку.

Визначення. мережею називається зважений граф G = (E, V) з ваговою функцією q: E > R + в якому виділено джерело A ? V, > deg (A) = 0, і стік B ? V, < deg (B) = 0. Значення q (X, Y) називається пропускною спроможністю ребра (X, Y) ? E.

Якщо (X, Y) ? / E то вважаємо, що q (X, Y) = 0

Визначення. потоком називається вагова функція p: E > R + ? {0} така, що

1. p (X, Y) ? q (X, Y) для всіх (X, Y) ? E;

2. Для всіх вершин C! = A, B має місце

 p (C, X) =  p (Y, C).

Якщо (X, Y) ? / E то вважаємо, що p (X, Y) = 0. Теорема. Для потоку p: E 7 > R + в мережі G = (E, V, q, A, B)

має місце

 p (A, X) =  p (Y, B).

Дана сума називається величиною потоку.

 p (A, X) =  p (C, X) -  p (C, X) =  p (Y, C) -  p (Y, C) =

 p (Y, B).

Завдання про максимальний потік.

Дано. Нехай є мережа G = (E, V, q, A, B).

Знайти потік p: E > R + ? {0} з найбільшою величиною V (p).



 Доведення формули Ейлера для плоских зв'язкових графів |  алгоритм

 штрих Шеффера |  Знаходження мінімальної ДНФ. |  приклади |  Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво). |  Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями. |  Вершин, ребер і компонент зв'язності. |  Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху. |  Теорема Келі про кількість дерев на n вершинах. Коди Прюфера. |  Операції об'єднання і перетину регулярних мов |

© um.co.ua - учбові матеріали та реферати