Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate didacticaScoala trebuie adaptata la copii ... nu copiii la scoala





Biologie Botanica Chimie Didactica Fizica Geografie
Gradinita Literatura Matematica




Matematica


Qdidactic » didactica & scoala » matematica
Teoria grafurilor - Gǎsirea drumurilor intr-un graf orientat - pas cu pas



Teoria grafurilor - Gǎsirea drumurilor intr-un graf orientat - pas cu pas


Gǎsirea drumurilor intr-un graf orientat

Daca privim graful ca imagine a unui sistem, nodurile reprezentand componentele sistemului, atunci o interpretare imediata a unui arc (xi,xj) este ca, componenta xi influenteaza direct componenta xj. Daca nodurile au semnificatia de stari posibile ale unui sistem atunci un arc (xi, xj) semnifica faptul ca sistemul poate trece direct din starea xi in starea xj. In ambele cazuri se vede ca avem de-a face doar cu informatii despre legaturi directe; totusi, chiar daca o componenta xi nu influenteaza direct componenta xj ea o poate influenta prin intermediul altor componente, existand un sir de componente intermediare: x1, x2,, xk, fiecare influentand-o direct pe urmatoarea si xi direct pe x1 iar xk direct pe xj. Astfel, daca dintr-o stare xi nu se poate trece direct intr-o stare xj s-ar putea totusi in mai multe etape, prin alte stari intermediare. Deoarece gasirea acestor influente sau treceri posibile este de obicei foarte importanta iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi facut 'din ochi', este necesara formalizarea notiunii de 'influente' si 'treceri' posibile, nu neaparat directe. Acest lucru a si fost facut mai sus, deoarece este evident ca ' xi influenteaza xij' sau 'din starea xi se poate trece in starea xij' este echivalent cu existenta in graf a unui drum de la nodul xi la nodul xj.

In continuare vom da un algoritm prin care putem gasi toate drumurile dintr-un graf orientat cu un numar finit de noduri.


Pasul 1. Se construieste matricea booleana a adiacentelor directe corespunzatoare grafului, notata cu A. In aceasta se afla, evident, toate drumurile de lungime 1.


Este interesant de vazut ce legatura exista intre aceasta matrice si drumurile de lungime 2. Fie doua noduri xi si xj oarecare din graf. Existenta unui drum de lungime 2 intre ele presupune existenta unui nod xk, din graf, cu proprietatea ca exista atat arcul (xi, xk) cat si arcul (xi, xk). Pentru a vedea daca acesta exista, luam pe rand fiecare nod al grafului si verificam daca exista sau nu ambele arce ((xi, xk) si (xi, xk)). Aceasta este echivalent cu a verifica daca, in matricea booleana a adiacentelor directe, exista vreun indice k astfel incat elementul k al liniei i si elementul k al coloanei j sa fie ambele egale cu 1. Daca folosim operatiile algebrei booleene de adunare si inmultire:



atunci verificarile de mai sus sunt echivalente cu a verifica daca elementul de pe pozitia (i,j) din A2 este egal cu 1. Valoarea 1 spune doar ca exista cel putin un drum de lungime 2 de la xi la xj. Daca dorim sa vedem si cate sunt, vom folosi regulile de inmultire si adunare obisnuita. De asemenea, se poate observa ca existenta unui drum de lungime 3 de la xi la xj presupune existenta unui nod xk astfel incat sa existe un drum de lungime 2 de la xi la xk si un arc de la xk la xj, care este echivalent cu a verifica daca exista vreun indice k astfel incat elementul k al liniei i din matricea A2 si elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, daca elementul (i,j) din A3 este 1.

Din cele de mai sus se observa ca existenta drumurilor de lungime k este data de valorile matricei Ak, daca s-au folosit regulile algebrei booleene si numarul lor este dat de Ak, daca s-au folosit regulile obisnuite.


Pasul 2. Vom calcula succesiv puterile lui A pana la puterea An-1


Daca intre nodurile xi si xj exista un drum de lungime ≥ n atunci el va contine un numar de noduri mai mare sau egal nu n+1 si, cum in graf sunt doar n varfuri, este clar ca cel putin unul, sa zicem xk, va aparea de doua ori. Vom avea in acest caz un drum de la xi pana la prima aparitie a lui xk, si un drum de la ultima aparitie a lui xk la xj. Eliminand toate nodurile dintre prima aparitie a lui xk si ultima aparitie a sa vom obtine un drum de la xi la xj, in care xk apare o singura data. Aplicand acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obtine un drum de la xi la xj, in care fiecare nod apare o singura data (deci un drum elementar), care are evident cel mult n-1 arce. In concluzie, daca exista vreun drum de la xi la xj atunci exista si un drum elementar si, deci, va exista o putere a lui A, intre A1 si An-1, in care pozitia (i,j) este diferita de 0. Pentru deciderea existentei unui drum intre oricare doua noduri este suficienta, deci, calcularea doar a primelor n-1 puteri ale lui A.


Pasul 3. Se calculeaza matricea D = A + A2 + + An-1


dij =

1, dacǎ existǎ cel putin un drum de la xi la xj

0, dacǎ nu existǎ nici un drum de la xi la xj




Daca ne intereseaza doar existenta drumurilor dintre noduri, nu si numarul lor, vom folosi inmultirea si adunarea booleana si conform observatiei de mai sus:

In acest caz, observand ca:


A∙(A + I)n-2 = C0n-2∙A + C1n-2∙A2 + + Cn-2n-2∙ An-1 = A + A2 + + An-1 = D


rezulta ca e suficient sa calculam doar puterea n-2 a matricei A + I si apoi s-o inmultim cu A. Avantajul acestei metode, in ceea ce priveste economia de timp, este sustinut si de urmatoarea observatie: daca D contine toate perechile de arce intre care exista drum atunci:


D = (A + A2 + + An-1) + An + An+1 + + An+k = D oricare ar fi k ≥ 0 =>

=> A∙(A + I)n-2+k = (A + A2 + + An-1) + An + An+1 + + An+k-1 = A∙ (A + I)n-2<=>

<=>A∙ (A + I)n-2+k = A∙ (A + I)n-2 oricare ar fi k ≥


deci de la puterea k = n-2 toate matricile Ak sunt egale. Putem, deci, calcula direct orice putere a lui A+I mai mare sau egala cu n-1 (de exemplu calculand (A+I)2, (A+I)4, (A+I)8, , (A+I)2r, r fiind prima putere a lui 2 pentru care 2r ≥ n-2).

Procedeul de mai sus nu asigura decat aflarea faptului daca exista sau nu drum intre doua noduri, eventual ce lungime are si cate sunt de aceasta lungime. Totusi, in problemele practice cel mai important este sa stim care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse in drumuri lementare si in problemele practice in general acestea sunt cele care intereseaza, pasii urmatori ai algoritmului vor fi dedicati gasirii lor. Pentru gasirea acestora se foloseste reprezentarea grafului prin matricea latina de la cazul F.


Pasul 4. Construim matricea latina L asociata grafului, unde:

lij =



xixj, dacǎ existǎ arcul (xi, xj)

0, dacǎ nu existǎ arcul (xi, xj)

si matricea Ļ, definita prin:

Ĩij =

xj, dacǎ existǎ arcul (xi, xj)

0, dacǎ nu existǎ arcul (xi, xj)

numita matricea latina redusa.

Gasirea unui drum de lungime 2 de la xi la xj presupune gasirea unui nod cu proprietatea ca exista arcele (xi, xk) si (xk, xj) si memorarea vectorului (xi, xk, xj). Aceasta este echivalent cu a gasi un indice k astfel incat elementul de pe pozitia k a liniei i, din matricea L, sa fie xi, xk si elementul de pe pozitia k al coloanei j, din matricea Ļ, sa fie xj. Vom inmulti deci matricea L cu matricea Ļ, folosind insa niste reguli de calcul speciale, numite inmultire si adunare latina.


Definitia 1: Se numeste alfabet o multime de semne numite simboluri sau litere unde I este o multime oarecare de indici, finita sau nu.

Definitia 2: Se numeste cuvant un sir finit de simboluri notat si1, si2, , sin.

Definitia 3: Se numeste inmultire latina o operatie definita pe multimea cuvintelor unui alfabet, notata 'xL ', astfel:

si1si2sin xL sj1 sj2 sjm = si1si2sinsj1 sj2 sjm

(produsul a doua cuvinte se obtine prin concatenarea lor)

Inmulti rea latina este asociativa, are ca element neutru cuvantul vid, nu e

comutativa si un element este inversabil doar daca este cuvantul vid.

Definitia 3: Se numeste adunare latina o functie definita pe multimea cuvintelor unui alfabet cu valori in multimea partilor multimi cuvintelor, notata '+L ' astfel:


(suma a doua cuvinte este multimea formata din cele doua cuvinte)


Pasul 5. Se calculeaza succesiv matricile:


L2 = L xL Ļ , L3 = L2 xL Ļ , ,Lk+1 = Lk xL Ļ


folosind operatiile de inmultire si adunare latina, alfabetul fiind multimea nodurilor grafului, unde operatia de inmultire este usor modificata, produsul dintre doua elemente ale matricilor fiind 0, daca unul dintre ele este 0 sau au un nod comun si este produsul latin al lor, in caz contrar.

Din felul cum a fost construita, matricea Lk va contine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cate are graful cu totul) rezulta ca:

primele n-1 puteri ale lui L contin toate drumurile elementare din graf;

puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;

matricea Ln-1 contine toate drumurile hamiltoniene din graf (daca exista).

Observatie: Deoarece obtinerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, daca graful are 100 de noduri, idicarea unei matrici de 100×100 la puterea 100) pentru obtinerea acesteia se poate aplica si urmatorul algoritm:

Pas 1. Se construieste matricea de adiacenta A;

Pas 2. Pentru fiecare linie i se aduna boolean la aceasta toate liniile j pentru care aij = 1.

Pas 3. Se reia pasul 2 pana cand, dupa o aplicare a acestuia, matricea ramane aceeasi (nu mai apare nici un 1).

Ultima matrice obtinuta este matricea drumurilor D numita si matricea conexiunilor totale.

Aceasta metoda, desi mai simpla nu spune insa si care sunt aceste drumuri, pentru gasirea lor aplicandu-se, de exemplu, inmultirea latina






Contact |- ia legatura cu noi -| contact
Adauga document |- pune-ti documente online -| adauga-document
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -| termeni
Copyright © |- 2024 - Toate drepturile rezervate -| copyright

Matematica



Statistica

Proiecte pe aceeasi tema


Functia de repartitie si densitatea de probabilitate
Atomi sau evenimente elementare
Triunghiul - perimetrul si aria triunghiului oarecare, unghiul exterior unui triunghi
Jocuri didactice matematica - lantul buclucas
Proiect didactic - activitate matematica - recunoasterea sirului crescator si descrescator
Dreapta perpendiculara pe plan
Trunchiul de piramida hexagonala regulata
Schema lui Bernoulli cu bila intoarsa si cu s stari
concursul centrelor de excelenta - matematica - CLASA a X-a -
Rezolvarea unui sistem de ecuatii liniare - lucrare



Ramai informat
Informatia de care ai nevoie
Acces nelimitat la mii de documente, referate, lucrari. Online e mai simplu.

Contribuie si tu!
Adauga online proiectul sau referatul tau.