UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПошук шляхів у графі (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2591
Скачало254
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Пошук шляхів у графі

 

Користуючись методами, викладеними в попередньому розділі, можна

визначити зв’язність (тобто наявність або відсутність шляху) між

будь-якими вершинами vi і vj заданого графа G =(V,E ). Однак часто буває

необхідним не просто встановити існування шляху між заданими вершинами,

але й знайти послідовність вершин і ребер (шлях), що веде з vi у vj.

 

Крім того, для різних практичних застосувань теорії графів важливою є

проблема систематичного обходу (перебору) всіх вершин і/або ребер графа.

 

Двома класичними методами розв’язання цих проблем є: метод або алгоритм

пошуку (обходу графа) вшир та метод або алгоритм пошуку (обходу графа)

вглиб.

 

Сформулюємо постановку проблеми пошуку та обидва методи її розв’язання.

 

Нехай задано граф G =(V,E ), VO (V ( множину початкових вершин і VK (V (

множину кінцевих (заключних, цільових) вершин графа G. Необхідно знайти

шлях з деякої вершини v (VO в одну з вершин w (VK , тобто знайти

послідовність ребер (vi,vi +1)(E, і =1,2,...,t (1 таку, що v1= v і

vt= w.

 

Зокрема, множина початкових вершин VO і/або множина кінцевих вершин VK

можуть містити тільки по одній вершині. Такі вершини природно називати

початковою і кінцевою вершинами графа G.

 

Для опису алгоритмів нам знадобляться три списки ребер ВІДКР, ЗАКР і

РОЗВ. Крім того, для вершини v (V через S  (v) будемо позначати множину

всіх вершин w (V таких, що в графі G існує ребро (v,w)(E. Такі вершини w

часто називають синами вершини v, а множину S (v) ( множиною синів

вершини v.

 

Для зручності додамо до множини вершин V графа G "порожню" вершину p, а

до множини ребер - "порожні" ребра виду (р,v), де v (VO. При визначенні

шляху з VO у VK "порожні" ребра не враховуються.

 

Оскільки в запропонованій нижче формі обидва алгоритми пошуку

відрізняються тільки в одній позиції, викладемо їх одночасно і

відзначимо те місце, яким вони різняться між собою.

 

Алгоритм пошуку вшир / вглиб.

 

1. Всі "порожні" ребра розмістити у списку ВІДКР (у довільному порядку).

 

 

2. Якщо ВІДКР = (, то РОЗВ = ( (тобто сформульована задача не має

розв’язку) і алгоритм завершує свою роботу.

 

3. Закрити перше ребро (v,w) з ВІДКР, тобто перенести ребро (v,w) зі

списку ВІДКР у список ЗАКР.

 

4. Якщо вершина w закритого ребра є кінцевою вершиною (w(VK), то шуканий

список РОЗВ (тобто шуканий шлях з VO у VK) міститься серед ребер списку

ЗАКР і може бути виділений з нього послідовно, починаючи з останнього

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

для кожного з ребер (v,w) списку ЗАКР необхідно вибирати

ребро-попередника (u,v) так, що воно є першим ребром з кінцем v у списку

ЗАКР. Алгоритм завершує свою роботу.

 

У противному разі (w (VK) перейти до пункту 5.

 

5. Визначити S (w) ( множину синів вершини w останнього закритого ребра,

а також множину ребер R (w)={(w,z) | z (S (w) }.

 

Розмістити у списку ВІДКР усі ребра з множини R  (w) \ (ВІДКР ( ЗАКР)

після / перед усіх ребер, що вже містяться в цьому списку.

 

6. Перейти до пункту 2.

 

Відмінність між обома алгоритмами пошуку знаходиться в позиції 5 і

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ