Коротко про сайт

RefList.Su - це найбільша колекція рефератів. На сайті RefList.su Ви знайдете безліч цікавих робіт і статей: реферати, дипломні, курсові роботи, шпаргалки, контрольні та лабораторні роботи, топіки з англійської мови. На нашому порталі, Ви можете додавати свої матеріали, читати реферати користувачів, використовувати пошук по сайту. Також в RefList.su можна почитати викладу, доповіді, квитки, твори. Колекція рефератів доступна для всіх безкоштовно і без відправки смс, і реєстрації.

Реклама

Товари

Реферат на тему Aлгоритмы на графах скачати

Розділ: Інформатика, програмуванняТип роботи: реферат
Страница 1 из 2 | Следующая страница
Елементи теорії графів.

Граф - сукупність крапок і ліній, де кожна лінія з'єднує дві точки. Крапки називаються вершинами, чи вузлами, графа, лінії - ребрами графа. Якщо ребро з'єднають дві вершини, то кажуть, що його їм инцидентно; вершини, з'єднані руба називаються суміжними. Дві вершини, з'єднані руба, можуть збігатися; таке ребро називається петлею. Кількість ребер, инцидентных вершині, називається ступенем вершини. Якщо два ребра инцидентны одному й тому ж парі вершин, вони називаються кратними; граф, у якому кратні ребра, називається мультиграфом.

Ребро, з'єднуюче дві вершини, може мати напрям від однієї вершини в іншу; у разі воно називається спрямованим, чи орієнтованим, і змальовується стрілкою. Граф, де всі ребра орієнтовані, називається орієнтованим графом (орграфом); ребра орграфа часто називають дугами. Дуги іменуються кратними, якщо вони лише мають загальні вершини, а й збігаються в напрямі. Іноді потрібно розглядати не весь граф, яке частина (частина вершин і частина ребер). Частина вершин і всі инцидентные їм ребра називаються подграфом; все вершини і частина инцидентных їм ребер називаються суграфом. Циклом називається замкнута ланцюг вершин. Деревом називається граф без циклів. Остовным деревом називається пов'язаний суграф графа, яка має циклів.

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

Для неориентированного ребра порядок, у якому указанны соединяемые їм вершини, не важливий. Для орієнтованого ребра важливо: першої вказується вершина, з якої виходить ребро.

Маршрут, чи шлях - це послідовність ребер в неориентированном графі, у якому кінець кожного ребра збігаються з початком наступного ребра. Кількість ребер маршруту називається його довгою.

Графы широко використовують як у самій математиці, і у її додатках. Вони застосовуються при побудові різних математичних моделей: ліній електропередач, мереж автодоріг, ліній повітряних повідомлень тощо.

Завдання у тому, знайти шляхи з вершини A в вершину B. Будемо ставити граф матрицею суміжності, тобто. квадратної таблицею NxN, у якій на перетині i-й рядки - і j-го шпальти значення TRUE, якщо і і j з'єднані руба, і FALSE інакше.

Пошук завширшки.

Приблизно так як, відповідно до принципу Гюйгенса, кожна точка хвильового фронту є джерелом вторинної хвилі, ми, вирушивши з заданої вершини A, відвідуємо все суміжні із нею вершини (тобто. вершини, у яких ведуть стрілки з A). Кожна посещенная вершина стає джерелом нової хвилі тощо. У цьому слід подбати у тому, ніж повернуться до ту вершину, у якій були.

Задля реалізації алгоритму знадобляться:

матриця m[1..n, 1..n] - матриця суміжності графа;

допоміжний масив queue[1..n], у якому формуватися чергу, тобто. тип даних перший ввійшов – перший вийшов (FIFO). Розмір його достатній, адже ми не відвідуємо вершини двічі. З масивом queue пов'язані дві перемінні - head і tail. У перемінної head перебуватиме номер поточної вершини, з якої йде хвиля, а з допомогою перемінної tail нових вершин вкладаються у "хвіст" черги queue;

допоміжний масив visited[1..n], потрібного у тому, щоб відзначати вже пройдені вершини (visited[i]=TRUE вершина і пройдено);

допоміжний масив prev[1..n] для зберігання пройдених вершин. У цьому вся масиві і буде сформовано шуканий шлях;

змінна f, яка прийме значення TRUE, коли шлях буде знайдено.

З іншого боку, ми введемо кілька допоміжних змінних, що з організацією циклів.

Program breadth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_B(A, B: integer);

Var

Visited: array[1..n] of boolean;

Prev: array[1..n] of integer;

з: array[1..n] of integer;

head, tail: integer;

f: boolean;

і, v, k: integer;

Begin

head:=1;

tail:=1;

f:=False;

For i:=1 to n do

Begin

Visited[i]:=False;

Prev[i]:=0

End;

C[tail]:=A;

Visited[A]:=True;

While (head<=tail) and not f do

Begin

v:=C[head];

head:=head+1;

For k:=1 to n do

if m[v, k] and not Visited[k] then

Begin

tail:=tail+1;

C[tail]:=k;

Visited[k]:=True;

Prev[k]:=v;

if k=B then

Begin

f:=true;

break

End

End

End;

if f then

Begin

k:=B;

Write(B);

While Prev[k]<>0 do

Begin

Write('<-', Prev[k]);

k:=Prev[k]

end

End

else

Write('Пути з ', A, ' в ', B, ' немає')

end;

Begin

Write('A= '); readln(A);

Write('B= '); readln(B);

A_to_B(A, B)

End.

Пошук завглибшки.

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

Зауважимо, побудований в такий спосіб алгоритм здатні отримувати всі дороги з A в B, але хто першим знайдений необов'язково може бути найкоротшим.

Як завжди, алгоритм з поверненнями найлегше оформити з допомогою рекурсивної процедури. Для його реалізації нам знадобляться:

матриця m[1..n, 1..n] - матриця суміжності графа;

допоміжний масив visited[1..n], який ми у тому, щоб відзначати вже пройдені вершини (visited[i]=TRUE вершина і пройдено);

змінна f, яка прийме значення TRUE, коли шлях буде знайдено.

Program depth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_b(A, B: integer);

Var

Visited: array[1..n] of boolean;

f: boolean;

і: integer;

Procedure Depth(p: integer);

var k: integer;

Begin

Visited[p]:=True;

For k:=1 to n do

If not f then

If m[p, k] and not Visited[k] then

If k=B then

Begin

f:=True;

Write(B);

Break

End

else Depth(k);

If f then write('<=', p);

End;

Begin

For i:=1 to n do Visited[i]:=False;

f:=false;

Depth(A);

If not f then write('Пути з ', A, ' в ', B, ' немає')

End;

Begin

write('A= '); readln(A);

write('B= '); readln(B);

A_to_B(A, B)

End.

Эйлеровы цикли.

Потрібна знайти цикл, проходить з кожної дузі рівно одного разу. Це завдання вперше поставив і він вирішив Леонард Эйлер, що навіть заклав підвалини теорії графів, а відповідні цикли тепер називаються эйлеровыми.

Завдання виникла із запропонованих Эйлеру головоломки, що отримала назву "проблема кенигсбергских мостів". Річка Прегель, протека ющая через Калінінград (колись місто називався Кенігсбергом), омиває два острова. Береги річки пов'язані з островами оскільки показано малюнку. У головоломці треба було знайти маршрут, проходить за всі ділянкам суші в такий спосіб, щоб кожен із мостів пройдено рівно одного разу, а початковий і кінцевий пункти маршруту збігалися.

Выберем як вершин графа береги ріки, а ролі ребер - мости, їх що з'єднують. Після цього завдання очевидна: вимога нездійсненне - що його виконати, число дуг, які до кожної вершині, має бути четным. У насправді, оскільки з одному мосту не можна проходити двічі, кожному входу до берега має відповідати вихід.

Що потрібно, щоб у графі існував эйлеров цикл? По-перше, граф може бути пов'язаним: для будь-яких двох вершин має існувати шлях, їх котрий поєднує. По-друге, для неориентированных графів число ребер у кожному вершині має бути четным. Насправді цього вистачає.

Теорему. Щоб на пов'язаному графі існував эйлеров цикл, необхідне й досить, щоб число ребер у кожному вершині було четным.

Доказ. Необхідність доведено вище. Доказ достатності конструктивно - внаслідок отримають необхідний алгоритм.

Доказ ведеться індукцією за кількістю ребер графа. Нехай твердження доведено всім m

Зауважимо, що, коли ми повернулися в А, ми можемо продовжити шлях з поточного вузла X по крайнього заходу одне ребро. У насправді, кожен прохід через X залишає четным число ребер у цій вершині. Тому, коли ми входимо в X, залишається парне число невычеркнутых ребер, з її виходять (по крайнього заходу одне ребро). Нехай ми повернулися на A. Тоді, коли всі ребра викреслені, теорема доведено. Інакше решта ребра розпадаються на пов'язані подграфы, кожен із яких містить хоча б одну вершину з вже побудованого циклу (оскільки початковий граф пов'язаний) і має менш n ребер. Нехай, …,– вершини зазначених подграфов, якими проходить побудований шлях.

За припущенням індукції у кожному їх існує эйлеров цикл. Будуємо тепер новий шлях з A так:

– йдемо старому шляху до;

– включаємо до нього новий шлях;

– йдемо старому шляху від до;

– повторюємо процес для вершини тощо.

Для закінчення докази (і побудови алгоритму) зауважимо, що база індукції очевидна: якщо ребро лише те воно – петля.

Хоча доказ проведено для неориентированных графів, він одразу переноситься на орієнтовані, лише вимога парності замінюється тепер у таке: число які входять у кожну вершину ребер має бути одно числу виходять.

Залишилося помітити, що запропонований в доказі алгоритм линеен, тобто. число дій прямо пропорційно кількості ребер.

Program Euler;

const n=9;

m: array[1..n, 1..n] of boolean=

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Type

list=^node;

node=record

і: integer;

next: list

end;

Var stack1, stack2: list;

v, u, x, і: integer;

Procedure Push(x: integer; var stack: list);

Var temp: list;

Begin

New(temp);

temp^.i:=x;

temp^.next:=stack;

stack:=temp

End;

Procedure Pop(var x: integer; var stack: list);

Begin

x:=stack^.i;

stack:=stack^.next

End;

Function Peek(stack: list): integer;

Begin

Peek:=stack^.i

End;

Procedure PrintList(l: list);

Begin

Writeln;

If l=nil then writeln('NIL');

While l<>nil do

Begin

Write(l^.i:3);

l:=l^.next

End

End;

Begin

stack1:=nil;

stack2:=nil;

Write('Начальная вершина: ');readln(v);

Push(v, stack1);

While stack1<>NIL do

Begin

v:=peek(stack1);

i:=1;

While (і<=n) and not m[v, i] do inc(i);

If і<=n then

Begin

u:=i;

Push(u, stack1);

m[v, u]:=False;

m[u, v]:=False;

End

else

Begin

pop(x, stack1);

push(x, stack2)

End

End;

PrintList(stack2)

End.

Завдання Прима–Краскала.

Дана пласка країна й у ній n міст. Потрібно поєднати всі міста телефонної зв'язком те щоб загальна довга телефонних ліній була мінімальною.

Чи у термінах теорії графів:

Дан граф з n вершинами; довжини ребер задано матрицею. Знайти остовное дерево мінімальної довжини.

Уявімо, що зимівнику залишено певний запас продуктів, та її завданням є складання смачного меню протягом усього зиму. Якщо зимівник почне сіло, що спочатку їстиме саму смачну їжу (наприклад, шоколад), потім – другу по смакоти (наприклад, м'ясо), він ризикує залишити на за останній місяць лише сіль і маргарин. Подібною, якщо оптимальний (для визначеності, мінімальний) об'єкт будується якось по кроків, не можна першою кроці вибирати щось щонайменше, другою кроці – що залишилося щонайменше тощо. За таку політику звичайно припадає розплачуватися під час останніх кроках. Такий алгоритм називається жадібним.

Дивно, але у завданню Прима–Краскала, яка видається особливо простий, жадібний алгоритм дає точне оптимальне рішення.

Як відомо (це легко довести по індукції), дерево з n вершинами має n-1 ребер. Виявляється, кожне ребро потрібно вибирати жадібно (лиш би виникали цикли). Тобто n-1 раз вибирати найкоротший ребро із ще не обраний ребро за умови, що його не утворює циклу з роботи вже обраними.

Але як стежити, щоб нове ребро не утворювало циклу з колишніми? Зробити це. До побудови дерева офарбимо кожну вершину і на чудовий з інших колір і. При виборі чергового ребра, наприклад (і, j), де і і j мають різні кольору, вершина j і всі, забарвлені у її колір (тобто. раніше із нею з'єднані) перефарбовуються в колір і. Отже, вибір вершин різного кольору забезпечує відсутність циклів. Після вибору n-1 ребер все вершини отримують один колір.

Докажем, що описаний алгоритм одержує у точності мінімальне рішення. Аби довести нам знадобиться дуже просте твердження:

Якщо до дерева додати ребро, то дереві з'явиться цикл, у якому це ребро.

Справді, нехай додано ребро (u, v) – “додано” означає, що ребро – нове, що його в дереві був. Оскільки дерево є пов'язаною графом, що існує ланцюг C(u, …, v) з кількох ребер, з'єднує вершини u і v. Додавання ребра (u, v) замикає ланцюг, перетворюючи їх у цикл.

Теорему. Алгоритм Прима–Краскала отримує мінімальне остовное дерево.

Доказ. Результатом роботи алгоритму є набір з n-1 ребер. Не утворюють циклу, бо кожному з n-1 кроків з'єднувалися вершини різного кольору, тобто. раніше які пов'язані. Цей граф зв'язний, бо після проведення 1-го ребра залишилося n-1 різних кольорів, …, після проведення (n-1)-го ребра залишилася сама колір, тобто. одна компонента связности. Отже, отриманий набір ребер утворює зв'язний граф без циклів, у якому n-1 ребер і n вершин. Отже, граф є остовное дерево.

Задля реалізації алгоритму знадобляться:

Matrix – матриця відстаней, значення перетині i-ой рядки - і

Страница 1 из 2 | Следующая страница

Поділіться рефератом Aлгоритмы на графах

html-посилання на реферат
BB-cсылка на скачать реферат
Пряме посилання на завантажити реферат

Роботи схожі на Aлгоритмы на графах

Вершини кар'єри межа розвитку
Тип роботи: реферат
Є.В. Петров, директор персоналу ВАТ «Західно-Сибірський металургійний комбінат», р. Новокузнецк
Чимало топ-менеджерів усвідомлюють, що від їхньої професіоналізму залежить, було б бізнес процвітати чи, навпаки, зменшується. Вони розуміють н
Завантажити
Закон, яка у нас, називається совістю
Тип роботи: твір
Таллиннская Тынисмяэская Реальна Школа
Закон, яка у нас, називається совістю.
(за твором Ф. М. Достоєвського «Злочин покарання»)
Автор: Філіп Кекс
Таллінн 2002
Усередині кожної людини перебуває якийсь ме
Завантажити
Міністр освіти граф З. З. Уваров. Самодержавство, Православ'я, Народність
Тип роботи: реферат
6. Ідеологія. Теорія офіційної народності
Прагнучи протистояти революційним і ліберальних ідей, самодержавство вдавалася до як до репресій. Цар розумів, що поглядам можуть протистояти лише інші погляди. Офіційної ідеологією микол
Завантажити
Граф Л. Н. Толстой: шлях до «Війни і світу»
Тип роботи: стаття
Ранчин А. М.
Своєрідність “Детства” і “Отрочества” тонко помітив літератор і критик М. Р. Чернишевський у статті “Дитинство і отроцтво. Військові розповіді грн. Толстого” (1856). Назвав відмітними рисами толстовського таланту “глибоке знан
Завантажити
Пушкін: Граф Нулін
Тип роботи: виклад
Хазяїн маєтку, молодий пан, вирушає на псову полювання. Недбало простясь із молодою дружиною, він рушає в дорогу. Слід ліричний відступ мисливство, мисливців, і навіть про жіночих заняттях у селі: У світлі останніх числах вересня (Презренной прозоЗавантажити
Граф Олексій Андрійович Аракчеев
Тип роботи: реферат
Народився маєтку свого батька, в Новгородської губернії, 23 вересня 1769 р. Початковий освіту його передачі під керівництвом сільського дячка полягала до вивчення російської грамоти й арифметики. До останнього науці хлопчик відчував велику схильніЗавантажити