Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

 
CATEGORII DOCUMENTE


AstronomieBiofizicaBiologieBotanicaCartiChimieCopii
Educatie civicaFabule ghicitoriFizicaGramaticaJocLiteratura romanaLogica
MatematicaPoeziiPsihologie psihiatrieSociologie


Matrici asociate unui graf. Proprietati ale grafurilor

Matematica


loading...



DOCUMENTE SIMILARE

Trimite pe Messenger
FORMULE MATEMATICE GEOMETRIE
CHESTIONAR DE CONCURS - Proba: ,,Matematica”
Algebre Boole. Corpuri de parti
Progresii aritmetice - Progresii geometrice
Sisteme de ecuatii liniare
STRUCTURU ALGORITMICE FUNDAMENTALE
METODE DIRECTE DE REZOLVARE A SISTEMELOR DE ECUATII LINIARE
EVENIMENTE DEPENDENTE SI INDEPENDENTE
REZOLVAREA CAZULUI DE NEDETERMINARE
Sisteme de ecuatii lineare

TERMENI importanti pentru acest document

: : matricea conexiunilor directe ale unui graf : adunarea booleana matrici : determinarea drumurilor hamiltoniene intr-un graf :

Matrici asociate unui graf. Proprietati ale grafurilor

Matricea conexiunilor directe

Fie un graf  cu . Asociem acestui graf o matrice patratica  booleana C, , ale carei elemente sunt:

.

Matricea C poarta numele de matricea arcelor, matricea conexiunilor directe sau matricea de adiacenta pentru graful G.

figura 5.1

Exemplu: Pentru graful din fig. 1 de mai sus scriem matricea conexiunilor directe:

Observatii:

1. Numarul de cifre 1 de pe linia i reprezinta numarul de conexiuni directe ale lui , iar numarul de cifre 1 de pe coloana j reprezinta numarul conexiunilor directe cu .

2. Daca 2 grafuri au aceeasi matrice a conexiunilor directe (si aceeasi multime de varfuri) atunci cele 2 grafuri coincid.

3. Gradul exterior al varfului si se obtine adunand elementele de pe linia i a matricei C, iar gradul interior al aceluiasi varf se obtine adunand elementele de pe coloana i a matricei C.

Matricea drumurilor

Din matricea conexiunilor directe, prin anumite operatii se poate obtine o matrice  numita matricea drumurilor sau matricea conexiunilor totale, in care

.

Definitie  Puterea de atingere  a varfului  in graful  este egala cu numarul de varfuri la care se poate ajunge din , adica egala cu numarul de elemente „1” de pe linia „i” din matricea D.

Pentru elaborarea unui algoritm de determinare a matricii drumurilor introducem o operatie adecvata pe multimea formata din elementele 0 si 1, numita operatie de „adunare booleana” cu regulile urmatoare:

+

0

1

0

0

1

1

0

1

Astfel algoritmul de determinare al matricii drumurilor unui graf pornind de la matricea conexiunilor directe, este:

1. Pentru construirea liniei „i” din matricea D  urmarim elementele egale cu „1” de pe linia „i” din matricea C: daca , , , …, atunci , , , …

2. Folosind adunarea booleana, se aduna liniile  din matricea C la linia „i”; noile valori „1” aparute se trec in linia „i” a matricei D; fie  pozitiile ocupate de aceste noi valori in cadrul linie i.

3. Adunam (boolean) liniile  din C la linia „i” trecand noile valori de „1” aparute in linia „i” a matricii D.

Procesul se continua pana la aparitia uneia din situatiile:

a) sau toate elementele ,  devin egale cu „1”.

b) nu mai apare nici un element egal cu „1”, caz in care locurile ramase libere se completeaza cu zerouri si se trece la linia „i+1”, pentru care se repeta procedeul.

Exemplu: Pentru graful din fig.5 cu matricea conexiunilor directe C asociata, determinam matricea drumurilor D.

Observatii:

1. Graful G are circuite, caci exista i astfel incat .

2. Avem puterile de atingere ale varfurilor

.

Determinarea drumurilor hamiltoniene

Teorema (Y. Chen) Un graf fara circuite, care are „n” varfuri, contine un drum hamiltonian, daca si numai daca avem: .

Algoritmul inmultirii latine (A. Kaufmann 1963)

Fie o matrice , care in locul valorilor de „1” utilizate in matricea obisnuita a arcelor, utilizeaza insusi arcul respectiv, reprezentat prin varfurile care il compun, deci , unde .

    Prin suprimarea primei litere in matricea  se obtine o matrice  numita „matricea destinatiilor posibile”. Se compun matricele  si  prin operatia de „inmultire latina”,  definita astfel: inmultirea latina a matricilor se face formal ca si inmultirea a 2 matrici, fara insumare si fara inmultire efectiva tinand cont ca:

– inmultirea latina a doua componente participante la calcul este nul daca cel putin una din ele este nula.

– inmultirea latina a doua componente participante este nul daca au varf comun.

– rezultatul compunerii consta in scrierea in continuare a varfurilor componente ale simbolurilor participante.

Prin repetarea inmultirii latine avem: , , …, si algoritmul continua pana la obtinerea matricii , deoarece intr-un graf cu n varfuri un drum hamiltonian are  arce. In matricea  citim, conform modului de scriere de mai sus toate drumurile hamiltoniene ale grafului. Daca toate elementele lui  sunt zerouri, (), graful nu admite drum hamiltonian.

Exemplu: Sa se determine drumurile hamiltoniene pentru graful din figura 5.1.

Solutie: Cum stim, graful are circuite. Vom folosi metoda inmultirii latine. Matricele  si  sunt:

 si

Atunci:

Astfel, in graful dat exista 4 drumuri hamiltoniene,

Algoritmul Bellman-Kalaba

Fie  un graf, vom introduce o functie  ce asociaza fiecarui arc din Γ o valoare reala. Notam:  si  graful valuat. In cazurile reale valuarea poate reprezenta:

– distanta dintre 2 puncte (localitati)

– timpi sau costuri intr-o retea de transport etc.

Pentru un drum  in graful G vom numi „valoare a drumului”, suma valorilor arcelor componente, adica: .

Vrem sa determinam drumul „d” de la un varf oarecare  la varful , pentru care valoarea lui  sa fie minima. Pentru aceasta introducem „matricea extinsa a valorilor arcelor” , data de

si notam cu  valoarea minima a drumului d de la  la  in graful dat, considerat in multimea drumurilor de cel mult k arce, cu  valoarea minima a drumului de la  la , considerata in multimea tuturor drumurilor (indiferent de numarul de arce componente).

Algoritmul de construire a vectorilor  se bazeaza pe urmatoarele propozitii:

Propozitia 1: Pentru orice  avem .

Propozitia 2: Daca exista  pentru care , pentru orice , atunci:

a) , , pentru orice ;

b) , .

Algoritmul de determinare a drumului minim este:

Etapa 1:    Se considera graful valuat , . Se construieste matricea estinsa a valorilor arcelor .

Etapa 2:    Se adauga matricii V, liniile suplimentare  astfel:

a) linia  coincide cu transpusa coloanei n a matricii V, ;

b) presupunand completata linia , se completeaza linia  conform propozitiei 1.

c) se continua aplicarea punctului (b) pana la obtinerea a 2 linii  si  identice.

Etapa 3:    Se determina regresiv drumul  minim de la  la  astfel:

– se aduna linia „i” din V cu linia  urmarindu-se rezulta-tul minim ce se poate obtine. Sa presupunem ca: , atunci primul arc din drumul minim de la  la  este arcul .

– se aduna linia „j” din V cu  retinand valoare minima, aflata de exemplu pe coloana „t”, atunci al doilea arc va fi , s.a.m.d. Ultimul succesor determinat va fi .

Algoritmul de determinare a drumului maxim

Etapa 1:    Se construieste matricea V a valorilor arcelor

Etapa 2:    Similar cu etapa 2 din algoritmul anterior, dar la
b) linia  se completeaza prin relatia .

Etapa 3:    Determinarea drumului maxim se determina la fel ca la etapa 3 anterioara.

Vom prezenta doua exemple de determinare a drumului minim, respectiv maxim cu ajutorul algoritmului Bellman-Kalaba.

Exemplu: Varfurile  reprezinta intreprinderi, iar pe arce este marcata durata executarii controlului in punctul  dupa efectuarea lui in punctul  in unitatea de timp corespunzatoare. Sa se determine timpul minim de control, dintre  si .

figura 5.2

Solutie: Construim matricea V a valorilor arcelor, si folosind algoritmul de determinare a drumului minim vom intocmi tabelul:

0

2

6

11

0

4

3

9

0

1

11

0

9

6

0

14

19

4

0

13

0

9

19

13

0

20

12

10

9

15

13

0

14

12

10

9

15

13

0

14

12

10

9

15

13

0

            Drumul minim de la  la  va fi  cu .

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 929
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Distribuie URL

Adauga cod HTML in site

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2014. All rights reserved