Алгоритм Дейкстра (стр. 4 из 4)

~

Наслідок 1 леми 1. Для будь-якого графа G=(V,E) сума числа верхового покриття і верхового числа незалежності постійна і дорівнює кількості вершин G: (G)+(G)=|V(G)|.

Лема 2. Якщо граф G=(V,E) не має ізольованих вершин, то сума його числа паросполучення і числа реберного покриття постійна і дорівнює кількості вершин G: (G)+(G)=|V(G)|.

Доказ:

1) Нехай C - найменше реберне покриття G, що містить (G) ребер. Розглянемо підграф GC графа G, утворений безліччю ребер C і інцидентними вершинами G; по визначенню покриття в нього входять усі вершини G. Оскільки C є найменшим, GC складається з однієї чи більшої кількості компонентів, кожна з який є деревом (дійсно, у противному випадку можна було б "викинути" з них кільцеві ребра й одержати покриття меншої потужності). По теоремі 2 кількість ребер у кожнім компоненті GS_i графа GC на одиницю менше кількості вершин: |E(GC_i)| = |V(GC_i)| - 1. Просуммировав ці рівності для всіх i, одержимо: |E(GC)| = |V(GC)| - p, де p - кількість компонентів у GС, отже, p = |V(G)| - (G). З іншого боку, якщо взяти по одному ребру з кожного компонента GC, одержимо деяке паросполучення, отже, (G)  p = |V(G)| - (G) і (G) + (G)  |V(G)| (*).

2) Нехай M - найбільше паросполучення G, що містить (G) ребер. Розглянемо безліч U вершин графа G, не покритих М. З визначення паросполучення випливає, що |U| = |V(G)| - 2|M| = |V(G)| - 2(G). Безліч U є незалежним (дійсно, якби дві довільні вершини U "зв'язувалися" ребром, то можна було б додати це ребро M і одержати паросполучення більшої потужності). Оскільки G за умовою не має ізольованих вершин, для кожної вершини, що входить у U, існує ребро, що покриває неї. Позначимо безліч таких ребер через S. Безлічі M і S не перетинаються, тому |M  S| = |M| + |S| = (G) + |U| = |V(G)| - (G). Об'єднання M і S є реберним покриттям графа по визначенню, отже, (G)  |M  S| = |V(G)| - (G) і (G) + (G)  |V(G)| (**).

З нерівностей (*) і (**) випливає результат леми.

~

Подальші результати справедливі тільки для двочасткових графів.

Теорема 1 (мінімаксная теорема Кеніга). Якщо граф G є двочастковим, то (G) = (G).

(без доказу)

Визначення: зроблене паросполучення (1-фактор) - паросполучення, що покриває усі вершини графа.

Нехай X - довільна підмножина вершин графа G=(V,E). Позначимо через (X) безліч вершин G, інцидентних вершинам X.

Теорема 2 (теорема про весілля). Якщо G - двочастковий граф з частками P₁ і P₂, то G має зроблене паросполучення тоді і тільки тоді, коли |P₁| = |P₂| і, принаймні, одне з P_i (i=1..2) володіє тим властивістю, що для будь-якого X P_i виконується нерівність |X|  |(X)|.

(без доказу)

Назва теореми зв'язана з наступною "несерйозною" задачею: визначити, чи можливо "переженити" групу юнаків і дівчин так, щоб усі залишилися задоволені. Якщо допустити, що всі "симпатії" взаємні (припущення, прямо скажемо, нереалістичне), то задача зводиться до перебування зробленого паросполучення в двочастковому графі, вершини однієї з часток якого відповідають юнакам, іншої - дівчинам, і дві вершини зв'язані ребром тоді і тільки тоді, коли юнак і дівчина подобаються один одному.

2.Задача знаходження мінмального шляху в графах:

Алгоритм Дейкстра

Розглянемо задачу про найкоротший шлях. Нехай G=(V,E) - зважений зв'язний граф з ненегативними вагами ребер (дуг). Вага f(e) ребра e інтерпретуємо як відстань між вершинами, суміжними даному ребру. Для заданої початкової вершини s і кінцевої вершини t шукається простий ланцюг, що з'єднує s і t мінімальної ваги. (s,t) - ланцюг мінімальної ваги називають найкоротшим (s,t) - шляхом. Очевидно, рішення задачі існує. Опишемо один з можливих алгоритмів рішення (Е. Дейкстра, 1959 р.).

Ініціалізація:

1. усім вершинам v_i приписується мітка - речовинне число: d(s)=0, d(v_i)=+ для всіх v_is;
2. мітки усіх вершин, крім s, вважаються тимчасовими, мітка s - постійної;
3. вершина s з'являється поточної (c:=s);
4. усі ребра (дуги) вважаються непоміченими.

Основна частина:

1. для усіх вершин u_j, інцидентних поточній вершині c, мітки яких є тимчасовими, перераховуємо ці мітки по формулі: d(u_j):=min{d(u_j), d(c)+Weight(c,u_j)} (*), де (c,u_j) - ребро (дуга), що з'єднує вершини c і u_j, а Weight(c,u_j) - її вага; при наявності кратних ребер вибирається ребро з мінімальною вагою;
2. якщо мітки усіх вершин є постійними або рівні , те шлях не існує; ВИХІД("немає рішення");
3. інакше знаходимо серед вершин з тимчасовими мітками (серед усіх таких вершин, а не тільки тих, чиї мітки змінилися в результаті останнього виконання кроку (1)!) вершину x з мінімальною міткою, повідомляємо її мітку постійної, позначаємо ребро (дугу) (с',x), таке, що d(x) = d(с')+Weight(с',x), де с'=з або с' - вершина, що була поточної на одному з попередніх кроків (с'=з, якщо на кроці (1) при u_j=x реалізувалася друга частина формули (*)), і робимо цю вершину поточної (c:=x);
4. якщо c=t, то знайдений шлях довжини d(t), якому можна відновити в такий спосіб: це той шлях між s і t, що складається тільки з позначених на кроці (3) ребер (дуг) (можна довести, що він існує й единий); ВИХІД("рішення знайдене");
5. інакше переходимо на крок (1).

Алгоритм можна модифікувати так, щоб він закінчував роботу після одержання усіма вершинами графа G постійних міток, тобто знаходяться найкоротші шляхи з s в усі вершини графа. Алгоритм визначить основне дерево D найкоротших шляхів з вершини s. Для будь-якої вершини v єдиний (s,v) - шлях у дереві D буде найкоротшим (s,v) - шляхом у графі G.

Алгоритм Дейкстра не завжди знаходить правильне рішення у випадку довільних ваг ребер (дуг) графа. Наприклад, для орграфа, зображеного на малюнку, алгоритм Дейкстра знайде маршрут s(s,t)t довжини 1 між вершинами s і t, а не мінімальний маршрут довжини 2+(-2)=0, що проходить через третю вершину графа.

Приклад орграфа, для якого не будем застосовувати алгоритм Дейкста.

Текст програми написаної на основі алгоритму Дейкстра

/* Алгоритм пошуку дерева найкоротших шляхів у зваженому графі */

/* Е.Дейкстра 1959 р. */

#include <stdio.h>

#include <stdlib.h>

#include <float.h>

int load_matrix(int n, double* weigh); /* Уведенняматриціваг */

int deik(int n, int s, double* weigh, int* Q, double* L); /* Алгоритмпошуку */

void print(int n, int* Q, double* L); /* Висновокрезультату */

void main(void){

int n=0,s=0,ret=0;

double *weigh;

int* Q; /* Масив міток покажчиків на попередню вершину */

double* L; /* Масив найдених ваг шляху до вершини */

printf("&bsol;nАлгоpитм пошуку дерева найкоротших шляхів у зваженому графі.&bsol;n");

printf("Е.Дейкстpа, 1959 р.&bsol;n");

printf("&bsol;nВведіть кількість вершин..");

scanf("%d",&n);

if (n <= 1){

printf("&bsol;nКількість вершин повинне бути більше одиниці!&bsol;n");

exit(1);

}

printf("&bsol;nВведіть початкову вершину..");

scanf("%d",&s);

s--;

if ((s < 0)||(s > (n-1))){

printf("&bsol;nПочаткова вершина зазначена неправильно! &bsol;n");

exit(1);

}

Q=malloc(n*sizeof(int));

L=malloc(n*sizeof(double));

weigh=malloc(sizeof(double)*n*n);

if ((weigh == NULL)||(Q == NULL)||(L == NULL)){

printf("&bsol;nHедостатньо пам'яті для завантаження масиву! &bsol;n");

exit(2);

}

ret=load_matrix(n,weigh);

if (ret != 0){

printf("&bsol;nПомилкавведенняданих!&bsol;n");

exit(5);

}

ret=deik(n,s,weigh,Q,L);

if (ret != 0){

switch (ret){

case 1 :

printf("&bsol;nГpафнеєзв'язаним!&bsol;n");

exit(3);

case 2 :

printf("&bsol;nHедостаточнопам'ятідляроботи!&bsol;n");

exit(4);

}

}

print(n,Q,L);

free(weigh);

free(Q);

free(L);

}

int load_matrix(int n, double* weigh){

int i,j,k;

double tmp;

for (i=0; i < n; i++){

for (j=0; j < n; j++){

weigh[n*i+j]=(-1);

}

}

printf("&bsol;nВведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.");

for (i=0; i < n; i++){

for (j=i+1; j < n; j++){

printf("&bsol;nВеpшини %d і %d ",i+1,j+1);

k=scanf("%lf",&tmp);

if (k != 1){return(1);}

weigh[i*n+j]=tmp;

}

}

return(0);

}

int deik(int n,int s, double* weigh, int* Q, double* L){

int i,j,k;

int* QI; /* Масив індикаторів сталості міток покажчиків */

double tmp;

QI=calloc(n,sizeof(int));

if (QI == NULL){return(2);}

QI[s]=1;

for (i=0; i < n; i++){

Q[i]=(-1);

L[i]=DBL_MAX;

}

Q[s]=s;

L[s]=0;

weigh[n*(n-1)+s]=0;

for (k=0; k < n; k++){ /* Основний цикл по вершинах */

for (i=0; i < n; i++){ /* Цикл по рядках матриці ваг */

for (j=i+1; j < n; j++){ /* Цикл по стовпцях матриці ваг */

if ((QI[i]+QI[j] == 1)&&

(QI[i]*QI[j] == 0)&&

(weigh[i*n+j] != (-1.0))&&

(((QI[i] == 1)&&((L[i]+weigh[i*n+j]) < L[j]))||

((QI[j] == 1)&&((L[j]+weigh[i*n+j]) < L[i])))){

if (QI[i] == 1){

L[j]=L[i]+weigh[i*n+j];

Q[j]=i;

}

else{

L[i]=L[j]+weigh[i*n+j];

Q[i]=j;

}

}

}

}

for (tmp=DBL_MAX,i=0; i < n; i++){

if ((tmp > L[i])&&(QI[i] == 0)){

tmp=L[i];

j=i;

}

}

QI[j]=1;

}

free(QI);

return(0);

}

void print(int n, int* Q, double* L){

int i;

printf("&bsol;n&bsol;nДеpевонайкоротшихшляхів:");

for (i=0; i < n; i++){

printf("&bsol;nВеpшина: %d Предок: %d Вага: %5.2lf",i+1,Q[i]+1,L[i]);

}

}

Результат виконання програми

Алгоритм пошуку дерева найкоротших шляхів у зваженому графі.

Е.Дейкстра, 1959 р.

Уведіть кількість вершин.. 6

Уведіть початкову вершину.. 6

Уведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.

Вершини 1 і 2 2

Вершини 1 і 3 -1

Вершини 1 і 4 2

Вершини 1 і 5 -1

Вершини 1 і 6 5

Вершини 2 і 3 2

Вершини 2 і 4 -1

Вершини 2 і 5 2

Вершини 2 і 6 -1

Вершини 3 і 4 -1

Вершини 3 і 5 -1

Вершини 3 і 6 12

Вершини 4 і 5 1

Вершини 4 і 6 2

Вершини 5 і 6 5

Дерево найкоротших шляхів:

Вершина: 1 Предок: 4 Вага: 4.00

Вершина: 2 Предок: 5 Вага: 5.00

Вершина: 3 Предок: 2 Вага: 7.00

Вершина: 4 Предок: 6 Вага: 2.00

Вершина: 5 Предок: 4 Вага: 3.00

Вершина: 6 Предок: 6 Вага: 0.00

Графічне зображення початкового графа та дерева мінімальних шляхів після виконання програми

Тестовий зв'язний зважений для алгоритму пошуку дерева шляхів з вершини 6 (Е. Дейкстра 1959р.)

Рішення: дерево найкоротших шляхів з вершини 6

4.Висновок

Ця курсова робота показує що дискретна математика, поряд з такими класичними розділами математики, як математичний аналіз, диференціальні рівняння, у навчальних планах спеціальності "Прикладна математика" і різні розділи по математичній логіці, алгебрі, комбінаториці і теорії графів тісно пов’язані із сучасним програмуванням. Причини цього неважко зрозуміти, просто розглянувши задачу, у цій курсовій роботі, яка за допомогою алгоритму Е. Дейкстра має змогу пошуку найкоротшого шляху в графі .

5.Література

1. Зыков А.А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.

2. Харари Ф. Теорія графів. - М.: Світ, 1973.

3. Зыков А.А. Основи теорії графів. - М.: Наука, 1987.

4. Кристофидес Н. Теорія графів. Алгоритмічний підхід. - М.: Світ, 1978.

5. Майника Э. Алгоритми оптимізації на мережах і графах. - М.: Світ, 1981.

6. Ловас Л., Пламмер М. Прикладні задачі теорії графів. Теорія паросочетаний у математику, фізику, хімії. - М.: Світ, 1998.