Extras din laborator
1. Un graf se numeşte rar dacă numărul său de muchii m este mai mic decât , unde n reprezintă numărul de vârfuri. O justificare este aceea că matricea de adiacenţă A a grafului, care ocupă n2 locaţii de memorie, poate fi întotdeauna reprezentată folosind O( ) locaţii de memorie, astfel încât răspunsul la o întrebare „A(i, j) = 1 ?” să se facă în O(1). Descrieţi o astfel de schemă de reprezentare.
Soluţie:
Având în vedere faptul că în matricea de adiacenţă A a unui graf fiecare element
A(i, j) poate lua doar valorile 0 şi 1, este suficient un singur bit pentru a memora aceste informaţii.
Pentru reducerea spaţiului ocupat de matricea de adiacenţă se propune următoarea schemă de reprezentare:
- matricea A este împărţită în matrice pătratice de dimensiune X ;
- numărul acestor matrice este ;
- se creează o nouă matrice pătratică A’ de dimensiune ;
- fiecare element al matricei A’ este o codificare a unei matrice de dimensiune X după cum urmează:
o o astfel de matrice are log n elemente ce pot lua doar valorile 0 şi 1;
o dacă matricea este parcursă pe linii se obţine o segvenţă de log n biti;
o fiecare astfel de segvenţă poate fi reprezentarea binară a unui număr între 0 şi 2log n = n;
o fie B o matrice de dimensiune X obţinută prin partiţionarea lui A ca mai sus, cu B(i,j) = A(k1 +i, k2 +j) şi fie s secventa de biti obtinută prin parcurgerea matricei B pe linii; atunci A’(k1, k2) = m, unde m este numărul a cărui reprezentare binară este s;
o având în vedere că reprezentarea binară a numerelor naturale este unică, dacă B1 ≠ B2, atunci s1 ≠ s2 şi m1≠ m2;
- obţinerea răspunsului la întrebarea: „A(i, j) = 1 ?”: valoarea lui A(i,j) se poate obţine din matricea A’ astfel:
o din modul de partiţionare a lui A se constată că elementul A(i,j) se obţine din procesarea elementului A’( , );
o reprezentarea binară a elementului A’( , )este succesiunea liniilor matricii B, unde B(p,q) = A(i,j), cu
p = i mod şi q = j mod , adică bitul de pe poziţia (i mod )* + j mod din reprezentarea binară a lui A’( , ), numărând de la stânga la dreapta;
Observaţie: Având în vedere faptul că numănul n nu se împarte întotdeauna exact la , este posibil ca matricele de la extremităţile dreapta, respectiv jos ale matricei A matricele obţinute prin patriţionare să nu aibă dimensiunile cerute, ci dimensiuni mai mici.
De exemplu, o matrice de dimendiune 5 X 5 trebuie patriţionată în matrici de dimensiune 2 X 2. Coloana a cincea va fi deci împărţită în 3 matrice, două de dimensiune 2 X 1 şi una de dimensiune 1 X 1. Aceste matrice vor fi „extinse” la matrice de dimensiune 2 X 2 astfel:
Fie B1 o matrice de dimensiune 2 X 1 (de exemplu, B1(0,0) = A(0,4) şi B1(1,0) = A(1,4) şi B2 matricea de dimensiune 2 X 2 la care va fi extinsă B1; atunci B2(0,0) = B1(0,0), B2(1,0) = B1(1,0), iar B2(0,1) şiB2(1,1) pot avea oricare din valorile 0 şi 1. B2(0,0) B2(0,1), B2(1,0), B2(1,1) este reprezentarea binară a valorii elementului A’(2,0).
Am văzut mai sus cum se face extragerea dintr-un element al lui A’ a bitului care reprezintă valoarea lui A(i, j). De acolo ne dăm seama că nu se va încerca niciodată extragerea unui bit care nu corespunde unui element din matricea A, deci valorile elementelor adăugate la extinderea matricelor B nu au importanţă.
- complexităţi:
o matricea A’ are elemente, deci complexitatea spaţiu a reprezentării sale este O( );
o operaţiile de calcul al elementului corespunzător lui A(i,j) din A’ se fac prin efectuarea unor împărţiri sau calcule de resturi, operaţii ce necesită timp constant O(1);
o accesul la elementele matricei A’ se face în timp constant O(1);
o extragerea unui bit din reprezentarea binară a unui element din A’ se poate face în timp constant O(1) prin operaţii logice pe biţi (utilizându-se eventual o mască);
În concluzie,răspunsul la întrebarea: „A(i, j) = 1 ?” se poate obţine în timp constant (independent de n) O(1).
2. Diametrul unui graf este lungimea maximă a unui drum de lungime minimă între două vârfuri ale grafului. Două vârfuri care sunt extremităţile unui drum minim de lungime maximă în graf se numesc diametral opuse. Demonstraţi că următorul algoritm determină o pereche de vârfuri diametral opuse într-un arbore T :
• Dintr-un vârf oarecare se execută o parcurgere BFS a arborelui; fie u ultimul vârf vizitat;
• Din vârful u se executa o parcurgere BFS a arborelui; fie v ultimul vârf vizitat;
• Return u, v.
Rămâne valabil algoritmul pentru un graf conex arecare?
Soluţie :
Preview document
Conținut arhivă zip
- AlgGr_Tema1.doc
- AlgGr_Tema10r.doc
- AlgGr_Tema11.doc
- AlgGr_Tema12.doc
- AlgGr_Tema2.doc
- AlgGr_Tema3.doc
- AlgGr_Tema4.doc
- AlgGr_Tema5f.doc
- AlgGr_Tema6f.doc
- AlgGr_Tema7f.doc
- AlgGr_Tema8f.doc
- AlgGr_Tema9f.doc
- g01.doc
- g02.doc
- g03.doc
- g04.doc
- g05.doc
- g06.doc
- g07.doc
- g08.doc
- g09.doc
- g10.doc
- g11.doc
- g12.doc