.RU

Транзитивное замыкание графа


Лекция 6

Транзитивное замыкание графа.


Пусть G=(A,R) – ориентированнй граф.

Транзитивный замыканием графа G называется граф G*=(A,R*), в котором из v в w из A идёт ребро тогда и только тогда, если существует путь (длины 0 или больше) из v в w.

Если (a,b)R и (b,c)R => (a,b)R*, (b,c)R*, (a,c)R*


Алгоритм 1: (~n3)

Взять произвольную вершину a.

Рассмотреть для всех вершин b: (b,a)R и всех вершины c дуги (a,c)R

Будем строить матрицу M* - смежности.



M[i,k]=1 и M[k,j]=1 => M*[i,j]=1

Провести такие вычисления для всех вершин.



Начальные значения: R* = R;

Для всех вершин kA выполнить

Для всех вершин iA выполнить

Для всех вершин jA выполнить

Если (i,j)R* и (k,j)R*,

то: (i,j)R*

R*=R*{(i,j)}


Алгоритм 2: (~n4)

Для всех вершин построить транзитивное замыкание длины 2. Найти все вершины, до которых есть путь длины 2.



M[i,j]=1 и M[j,k]=1 => M[i,k]=1


И так n раз для каждых вершин строить транзитивное замыкание.

Пример:



Изначально:



В итоге:



Дуги:(1,3) (5,3) (1,4) (2,4) (5,4) (1,5) (2,5) (3,5) (5,5) (2,2) (3,2) (3,3) (4,2) (4,3) (4,4)


^ Нахождение кратчайших путей в графе


Определение: Пусть G=(V,E) – ориентированный граф. Поставим в соответствие каждому ребру e графа G неотрицательную вещественную стоимость c(e). с() – функция стоимости дуги.

Стоимость пути определяется как сумма стоимостей ребер, образующих его.

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

Обсудим алгоритм сложности O(n2) нахождения кратчайших путей из одного источника (из одной вершины во все другие). Его работа основана на построении множества S узлов, кратчайшие растояния до которых от источника известны. На каждом шаге к S добавляется тот из оставшихся узлов, растояние до которого от источника меньше всех других остальных узлов.

^ Алгоритм Дейкстры:

Вход: G=(V,E) – ориентированный граф.

v0V – источник

с: E -> R+ - функция, отображающая дуги во сножества неотрицательных чисел

Полагаем, что c(vi,vj)=+, если (vi,vj)E, c(v,v)=0

Выход: Для всех vV наименьшая сумма меток на рёбрах из E, взятая по всем путям, идущим из v0 в V.

Метод: Строим такое множество SV, что кратчайший путь из источника в каждый узел vS целиком лежит в S. Массив D[v] содержит стоимость текущего кратчайшего пути из v0 до вершины v.

Алгоритм:

начало

  1. S<-{v0};

  2. D[v0]<-0;

  3. Для всех vV\{v0} выполнить: D[v]<-c(v0,v);

  4. пока S≠V выполнять:

начало

выбирать узел wV\S, для которого D[w] принимает наименьшее значение;

добавить w к S;

для всех vV\S выполнить: D[v]<-min(D[v],D[w]+c(w,v));

конец

конец


Пример:





Итерация

S

w

D[w]

D[v1]

D[v2]

D[v3]

D[v4]

Нач. знач.

{ v0}

--

--

2

+

+

10

1

{v0,v1}

v1

2

2

5

+

9

2

{v0, v1,v2}

v2

5

2

5

9

9

3

{v0, v1,v2, v3}

v3

9

2

5

9

9

4

все узлы

v4

9

2

5

9

9


Алгоритм Дейкстры вычисляет стоимость кратчайшего пути среди всех путей, идущих из v0 в любой узел и занимает O(n2) времени.

Обобщенный алгоритм Дейкстры. (Флойда)

Нахождение всех минимальных (кратчайших) путей для всех вершин графа.

Строится таблица стоимостей:

M[i,j]=c(i,j), где c(i,j)=+, если нет дуги из i в j,c(i,j)=0, если i=j

for (k=0;k
for (i=0;i
for (j=0;j
if (M[i,j]> M[i,k]+M[k,j]) {

M[i,j]=M[i,k]+M[k,j];

}

}

}

}


Здесь, как и в алгоритме транзитивного замыкания, некоторая вершина транзитная (промежуточная)

Временная сложность этого алгоритма O(n3)





studencheskie-konferencii-olimpiadi-konkursi-i-vistavki-studencheskih-rabot.html
studencheskie-vizi-vidannie-inostrancam-s-20022003-po-20072008-god.html
studencheskie-vospominaniya-1894-knigi-publicistiki-za-shest-let-1906-1912-1912-a-takzhe-mnogochislennih-istoricheskih-proizvedenij-moskovskoe-knyazhest-stranica-7.html
studencheskij-kalendar-pozdravlyaem-tebya-s-nachalom-studencheskoj-zhizni.html
studencheskij-socialno-pedagogicheskij-proekt.html
studencheskoe-lekcionnoe-turne-slt-russia-cis-201112.html
  • literature.bystrickaya.ru/bobrovnikovo.html
  • pisat.bystrickaya.ru/spravka-ob-itogah-rassmotreniya-krasnogorskim-rajonnim-sudom-g-kamenska-uralskogo-sverdlovskoj-oblasti-ugolovnih-del-i-materialov-v-otnoshenii-nesovershennoletnih-za-2011-god.html
  • grade.bystrickaya.ru/monografiya-posvyashena-aktualnim-voprosam-primeneniya-kraniomet.html
  • uchebnik.bystrickaya.ru/v-naukah-o-cheloveke-dolzhen-proizojti-sdvig-kotorij-mozhno-sravnit-lish-s-kopernikianskoj-revolyuciej-v-astronomii.html
  • uchebnik.bystrickaya.ru/v-i-goncharov-adres-redakcii-stranica-4.html
  • shpargalka.bystrickaya.ru/vlastelin-kolec-vozvrashenie-korolya-stranica-3.html
  • tasks.bystrickaya.ru/20-harakteristika-sovremennogo-nauchnogo-metoda-1-uchenie-konfuciya.html
  • write.bystrickaya.ru/glava-xv-88-o-chestvovanii-svyatih-i-ih-moshej-kniga-pervaya-29.html
  • vospitanie.bystrickaya.ru/zadachi-razvitie-prostranstvennih-predstavlenij-detej-razvitie-rechi-obogashenie-aktivnogo-slovarya-razvitie-proizvolnoj-pamyati.html
  • esse.bystrickaya.ru/put-razmesheniya-na-sajte-mintrud-rtsocialnoe-partnerstvorazvitie-socialnogo-partnerstvainformaciya-stranica-4.html
  • laboratornaya.bystrickaya.ru/programmnoe-obespechenie-sistemi-sbora-opisanie-i-instrukciya-po-ekspluatacii-g-obninsk.html
  • textbook.bystrickaya.ru/kak-sdelat-sherstyanie-tkani-i-sukno-nepromokaemi-obihodnaya-receptura-sadovoda-shtejnberg-pn.html
  • reading.bystrickaya.ru/leonardo-da-vinchi-1982-god-stranica-3.html
  • thesis.bystrickaya.ru/programma-disciplini-tehnologiya-stroitelnih-processov.html
  • college.bystrickaya.ru/1-tehnologicheskaya-podgotovka-proizvodstva-etap-tehnologicheskoj-podgotovki-proizvodstva-tesno-svyazan-s-predidushimi-etapami-tak-kak-vhodnoj-informaciej-dlya.html
  • teacher.bystrickaya.ru/fizicheskaya-kultura-i-adaptaciya-organizma-xxx-nauchno-metodicheskaya-konferenciya-vladivostok.html
  • gramota.bystrickaya.ru/zapolnenie-zayavki-na-uchastie-v-konkurse-prilozhenie-2-a-a-temkin-2-marta-2007-goda.html
  • literature.bystrickaya.ru/deyatelnost-municipalnogo-arhiva-otchet-glavi-municipalnogo-rajona-krasnochikojskij-rajon-za-2010god.html
  • school.bystrickaya.ru/kopchenie-i-koptilnie-kameri.html
  • uchit.bystrickaya.ru/titovichvladimir-vasilevich-ukazatel-personalij.html
  • crib.bystrickaya.ru/igrapriroda-igri-predmet-i-zadachi-psihologii-kak-nauki.html
  • books.bystrickaya.ru/dokumentaciya-ob-aukcione-na-pravo-zaklyucheniya-gosudarstvennogo-kontrakta-na-postavku-tovara-dlya-gosudarstvennih-nuzhd.html
  • esse.bystrickaya.ru/referat-otchet-97-str-47-illyustraciya-30-tablic-42-ispolzovannih-istochnika.html
  • writing.bystrickaya.ru/innovacionnaya-i-investicionnaya-deyatelnost-predpriyatiya.html
  • tasks.bystrickaya.ru/13092011-16092011-provedenie-vistavok-v-moskv-e-v-2011-godu.html
  • ucheba.bystrickaya.ru/prakticheskie-rekomendacii-teoreticheskie-i-metodologicheskie-osnovi-razvitiya-sestrinskogo-dela-na-urovne-pervichnoj.html
  • ekzamen.bystrickaya.ru/sabati-barisi.html
  • thesis.bystrickaya.ru/prilozhenie-17-metodicheskie-rekomendacii-dlya-organov-gosudarstvennoj-vlasti-subektov-rossijskoj-federacii-i-organov-mestnogo-samoupravleniya-po-realizacii-federalnogo-zakona-ot-8-maya-2010-g-83-fz-v-sfere-transporta.html
  • thescience.bystrickaya.ru/kasha-v-golove-fajnberg-v-l-inie-izmereniya-kniga-rasskazov.html
  • institut.bystrickaya.ru/stanca-i-prodolzhenie-tajnaya-doktrina.html
  • report.bystrickaya.ru/ii-mezhdunarodnaya-nauchno-prakticheskaya-konferenciya-voda-bescennoe-nasledie-sankt-peterburg-azimut-otel.html
  • literatura.bystrickaya.ru/rinochnaya-stoimost-nornikelya-sostavlyaet-po-raschetam-agentstva-bloomberg-29-mlrd.html
  • control.bystrickaya.ru/dialogovoe-proektirovanie-tehnologicheskih-processov-v-sisteme-tehnopro.html
  • zadachi.bystrickaya.ru/shpargalka-po-moskvovedeniyu.html
  • knigi.bystrickaya.ru/sovpadenie-imyon-sobitij-i-faktov-s-tem-chto-schitaetsya-realnim-sluchajnoe-stranica-6.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.