[TEMA] "Transformare" matrice in graf

Multe probleme de programare dinamica au cerinta sa se determine cel mai scurt drum dintre a[x1][y1] si a[x2][y2] cu x1,x2,y1,y2 citite de la tastatura .Hai sa ziceam ca avem cel mai scurt drum de la a[1][2] pana la a[n][m-1] (cu n  linii si m coloane ),deplasandu-se doar pe pozitiile a[i+1][j] ,a[i+1[j-1] , a[i+1][j+1].Am inteles ca se folosesc algoritmi care implica grafuri,precum Lee ,Dijkstra,Ford,Roy-Floyd(in general nu neaparat pentru tipul asta de problema).


exemplu

7 1 5 6 6
6 1 8 6 5
3 2 2 4 3
6 5 4 1 3
9 8 6 2 3

Imi puteti desena graful care corespunde matricei respective ?(puteti sa nu colorati cu rosu drumurile) . Sau daca nu ,imi puteti spune cum pot citi matricea asta sub forma de graf?Graful am impresia ca trebuie sa fie neorientat...


Ce s-ar schimba daca "punctul" s-ar puteam deplasa doar pe verticala(stanga,dreapta) si orizontala(in jos) ,dar nu si pe diagonale(evident,in jos) ?

Edited by VladBtz, 04 March 2015 - 19:26.

Suna ciudat "graful care corespunde matricei respective". Grafurile le poti reprezenta sub forma de matrici.
Zi-ne ce reprezinta valorile din matrice.

matricea e un tablou bidimensional,o bucata din memorie si fiecare "slot" are o valaore,i-ar valorile cu rosu sunt drumul de la a[..][..] la a[,,,][,,,] .suna ciudat,dar ai prins ideea


daca suna ciudat imi poti desena un graf "corespunzator" si sa imi spui cum il pot reprezenta sub forma de matrice?se poate reprezenta sub forma amtricei din exeplu sau doar versiunea cu diagonala principala = 0 si unde nu exista drum s epune infinit?

Edited by VladBtz, 04 March 2015 - 20:48.

Matricea care ai dat-o ca exemplu e un graf complet(exista muchie intre fiecare nod al grafului,cu costul dat in matrice).In fine pentru drumul minim de la un punct dat la alt punct dat in matrice nu iti trebuie neaparat algoritmi pentru grafuri.
Pur si simplu aplici algoritmul lui Lee(care e pentru drumul minim in matrice,nu are legatura special cu grafurile precum Floyd,Bellman,etc.).Daca nu stii Lee,pur si siplu cauta-l pe internet(e bine explicat).O sa intelegi cum sa rezolvi problema expusa.

Edited by cumva, 04 March 2015 - 21:13.

Cand vrei sa salvezi eficient un graf, il salvezi ca matrice, cum ai aratat tu - ala e deja graful - si nu ca structuri de noduri care au pointeri catre alte noduri.

Intuitia imi spune ca graful postat de tine e un fully connected weighted graph.

E fully connected, pentru ca nu ai 0 in matrice (toate nodurile sunt conectate cu toate celelalte), si e weighted, pentru ca nu ai doar 0 si 1, care ar denota daca intre noduri e o conexiune sau nu, ci ai si alte numere > 1.

A, si probabil mai e si directed, pentru ca diagonala principala a matricii nu constituie o axa de simetrie, de exemplu m[3][2] nu este egal cu m[2][3].

Graful are 5 noduri - le poti numerota de la 0 la 4.

Desene: http://en.wikipedia....djacency_matrix

Ideea e ca nu prea vad matricea sub forma de graf,la Olimpiada daca da,o sa dea matrice si o sa trebuiasca sa aplic algorimi ptr graduri (chiar daca "e acelasi lucru").care sunt alea 5 noduri care el are matricea mea?Imi pare rau ca a iesit complet,as putea sa pun numere > 10 si sa zic ca prin alea nu poate trece,ca sa nu mai fie complet?deci nu imi puteti desena graful matricei (chiar daca e acelasi lucru) ?nici daca modific matricea?am citit si din culegeri faza cu matricea de adiacenta si nu m-a prea ajutat

VladBtz, on 04 martie 2015 - 22:04, said:

Deseneaza deasupra fiecarei coloane pe rand numerele 0, 1, 2, 3, 4. Fie acele numere "de la nodul X din graf".

Deseneaza in stanga fiecarui rand din matrice numerele 0, 1, 2, 3, 4. Fie acele numere "pana la nodul Y".

In matrice ai informatia: "drumul de la nodul X pana la nodul Y costa m[X][Y]".

VladBtz, on 04 martie 2015 - 22:04, said:

Daca vrei sa nu se poata trece de la nodul X la nodul Y, scrii in matrice la adresa m[X][Y] o valoare "speciala" gen 0 sau -1. Valoarea in sine nu e speciala, ceea ce o face speciala e modul in care o tratezi in algorimul tau. Daca stabilesti ca valoarea ta speciala este -42, in cod vei avea probabil conditii ca if(m[i][j] != -42). In orice caz, vei alege o valoare ce nu poate apare "in mod normal" in matrice, pentru a nu exista ambiguitati (42 de exemplu ar fi o valoare aleasa prost, deoarece poate insemna fie "drumul de la X la Y costa 42", fie "intre X si Y nu exista un drum". Dar chiar si asa, speciala o face codul pe care il scrii, si daca tu alegi ca 42 sa fie acea valoare, 42 va fi - doar ca algoritmul tau nu va putea lucra corect cu "costul 42 intre X si Y".

Ca sa nu fie complet deci, trebuie sa scrii valoarea 0 undeva.

VladBtz, on 04 martie 2015 - 22:04, said:

Noi putem sa-l desenam, dar e mai bine daca il desenezi tu, ca exercitiu, si noi iti oferim feedback - sa vezi daca ai inteles corect articolul de pe wikipedia.

Citeste articolul cu atentie, e totul explicat acolo - nu are rost sa repetam ce scrie deja acolo. Daca ai intrebari concrete de intelegere, intreaba.

Nu suntem la gradinita, si nici tu nu esti prost - ceva ceva tot poti intelege de acolo. Acest citit e un exercitiu bun pentru dezvoltarea ta ca individ: inveti sa citesti o descriere tehnica si sa extragi intelegere din ea.

E cam neinteligibil un graf pornind de la acea matrice
 a.png   70.92K   17 downloads

dani.user, on 04 martie 2015 - 23:55, said:

mersi de efort.stii vreo matrice unde sa se vada mai bine grafu?

VladBtz, on 05 martie 2015 - 19:29, said:

[0]

OriginalCopy, on 05 martie 2015 - 19:31, said:

deci sa inlocuiesc unele elemente cu 0 ca neaccesibile si sa pun a conditie if( a[i][j] ) ca sa il faca neaccesibil?

VladBtz, on 05 martie 2015 - 20:23, said:

Nu omule, asta e matricea de adiacenta a celui mai simplu graf: [0]. Graful are un singur nod.

Vezi daca n-ai folosit oportunitatea pe care ti-am oferit-o, de a desena singur graful, si noi sa-l corectam? Ai primit totul de-a gata, dar ciuciu intelegere, ne-am racit tastaturile degeaba cu tine.

10000000    cu 1 obstacol , 0 drum liber
11011011
10001011
00000111
11110000
00101111
00000000
01010101


[ https://scontent-fra.xx.fbcdn.net/hphotos-xpa1/v/t1.0-9/11052032_867615233259089_5610546949433100892_n.jpg?oh=88f2e77db04afbc6fa1e2be1c5824c27&oe=55793A6B - Pentru incarcare in pagina (embed) Click aici ]

Edited by VladBtz, 05 March 2015 - 21:18.

Graful asta e prea complicat pt tine.

Incearca ceva mai simplu. Scrie matricile de adiacenta ale acestor grafuri

1.

[ https://i.imgur.com/1OnnfIU.png - Pentru incarcare in pagina (embed) Click aici ]

2.

[ https://i.imgur.com/JUXERpp.png - Pentru incarcare in pagina (embed) Click aici ]

ptr grafu 2

000
101
100

si pentru primul

01
10

e bine?

Da

si grafu ala mai mare care era ''prea comple''' e bun?