INFORMATICA - APLICATII GRAFURI NEORIENTATE

 

MATEMATICA-INFORMATICA

1.ENUNTUL PROBLEMEI

Sa se scrie un program care, prin intermediul unui meniu, selecteaza in mod repetat, atata timp cat utilizatorul doreste acest lucru, una din urmatoarele actiuni:

  Generarea aleatorie a matricei de adiacenta a unui graf neorientat

  Crearea matricei de incidenta prin citirea datelor din matricea de adiacenta, a unui graf neorientat

  Crearea listei de adiacenta din matricea de adiacenta, a unui graf neorientat, implementarea cu matrice

  Generarea tuturor grafurilor partiale ale unui graf folosind matricea de incidenta

  Generarea tuturor subgrafurilor unui graf folosind matricea de adiacenta

  Afisarea tuturor lanturilor elementare dintr-un graf folosind matricea de adiacenta

  Determinarea ciclurilor elementare intr-un graf folosind matricea de adiacenta

  Determinarea componentelor conexe intr-un graf

2. NOTIUNI ELEMENTARE

Graful neorientat este o pereche ordonata de multimi G=(V,E) unde: V - multime finita si nevida numita multimea varfurilor(nodurilor)

E - multimea formata din perechi neordonate de elemente distincte din V, numita multimea muchiilor(arcelor) lui G

O muchie eE este deci o submultime cu de varfuri distincte din V si o vom nota (u,v)-notatie muchie. Vom spune ca varfurile u si v sunt adiacente in G si ca ambele sunt incidente cu muchia (u,v). Varfurile u si v se mai numesc si extremitatile muchiei (u,v).

Daca e1 si e2 sunt doua muchii care au o extremitate comuna ele vor fi numite de asemenea incidente.

Graful neorientat este reprezentat prin diferite modalitati, folosind diverse tipuri de structuri de date. Reprezentarile vor fi utilizate in diversi algoritmi si in programele care implementeaza pe calculator acesti algoritmi.

Cele mai cunoscute forme de reprezentare ale unui altfel de graf sunt:- matricea de adiacenta

- listele vecinelor

- vectorul de muchii

  Matricea de adiacenta

Este o matrice a cu n linii si n coloane, in care elementele a[i][j] se definesc astfel:

a[i][j]=1, daca exista (i,j) din E si i≠j

0, daca nu exista (i,j) din E

Matricea de adiacenta asociata unui graf neorientat are urmatoarele proprietati:- este simetrica fata de diagonala principala

- toate elementele de pe diagonala principala sunt nule

- suma elementelor de pe o linie k sau coloana k este egala cu gradul nodului k

  Listele vecinilor

Pentru fiecare nod i formam lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt extremitati ale muchiilor ce trec prin nodul i (sau altfel spus toate nodurile adiacente cu nodul i).

  Listele muchiilor

Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu st si dr putem defini tipul de date TMUCHIE astfel:

typedef struct

TMUCHIE;

Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul TMUCHIE. In consecinta, putem defini graful ca un ,,vector de muchii, adica un vector cu elemnte de tipul TMUCHIE.

Numarul efectiv de muchii este m. Fiecare element v[i] are doua componenete: v[i].st si v[i].dr

3. PREZENTAREA PROBLEMEI

In cadrul programului de atestat realizat sub indrumarea doamnei profesoare LAZUREAN ANCUTA - MARIA am ilustrat pe baza unui meniu modul de lucru al reprezentarii grafurilor neorientate folosind diferite structuri de date, si anume:

  Generarea aleatorie a matricei de adiacenta a unui graf neorientat

  Crearea matricei de incidenta prin citirea datelor din matricea de adiacenta, a unui graf neorientat

  Crearea listei de adiacenta din matricea de adiacenta, a unui graf neorientat, implementarea cu matrice

  Generarea tuturor grafurilor partiale ale unui graf folosind matricea de incidenta

  Generarea tuturor subgrafurilor unui graf folosind matricea de adiacenta

  Afisarea tuturor lanturilor elementare dintr-un graf folosind matricea de adiacenta

  Determinarea ciclurilor elementare intr-un graf folosind matricea de adiacenta

  Determinarea componentelor conexe intr-un graf

a) Generarea aleatorie a matricei de adiacenta

Pentru a testa programele care prelucreaza grafuri implementate cu matricea de adiacenta, putem sa generam aleatoriu matricea de adiacenta.

Functia generare() genereaza matricea de adiacenta a unui graf neorientat, cu n noduri si m muchii.

b) Crearea matricei de incidenta prin citirea datelor din matricea de adiacenta

Matricele de adiacenta se citeste din fisierul text creat anterior: adiac.txt. Se creeaza matricea de incidenta. Se salveaza in fisier informatiile despre muchii astfel: pe primul rand, despartite prin spatii, numarul de noduri si numarul de muchii ale grafului, si apoi, pe cate un rand, separate prin spatiu, cele doua noduri terminale ale fiecarei muchii. Se folosesc matricele a si b pentru matricea de incidenta si functiile citeste() pentru a citi matricea de adiacenta din fisier, salveaza() pentru a salva in fisierul text informatiile muchiile grafului, transforma() pentru a obtine matricea de incidenta din matricea de adiacenta, afiseaza_noduri_izolate() pentru a afisa nodurile izolate, si afiseaza_muchii() pentru a afisa muchiile.

c) Crearea listei de adiacenta din matricea de adiacenta, implementarea cu matrice

Se citeste dintr-un fisier creat anterior matricea de adiacenta implementata cu matrice. Se salveaza listele de adiacenta intr-un fisier text, astfel: pe prima linie, valorile pentru numarul de noduri n si numarul de muchii m, despartite prin spatiu, iar apoi, pe urmatoarele n linii, despartite prin spatiu, numarul de vecini ai unui nod si lista vecinilor pentru graful neorientat. Functia citeste() se foloseste pentru a citi matricea de adiacenta din fisier, functia transpune() pentru a obtine lista de adiacenta din matricea de adiacenta, iar functia scrie() pentru a scrie listele de adiacenta in fisier.

d) Generarea tuturor grafurilor partiale ale unui graf folosind matricea de incidenta

Algoritmul: Se foloseste metoda backtracking. In stiva se vor genera muchiile grafului partial. Deoarece graful partial poate avea p muchii (0≤p≤m), se va apela repetat subprogramul bt(), la fiecare apel generandu-se variantele cu p muchii. Fiecare apel al subprogarmului bt() trebuie sa genereze (combinari de p luate cate n) de muchii din graf. La fiecare apel al subprogramului, solutia se obtine atunci cand in stiva s-au generat cele p muchii ale grafului partial. Evidenta muchiilor este pastrata in matricea de incidenta.

Implementarea algoritmului: Se citeste din fisierul text adiac.txt matricea de adiacenta a unui graf neorientat. Pentru fiecare graf partial se afiseaza muchiile. Matricea de incidenta b se obtine din matricea de adiacenta cu functia transformare(). In variabila nr se contorizeaza numarul de grafuri partiale generate. In functia tipar() se afiseaza graful partial generat.

e) Generarea tuturor subgrafurilor unui graf folosind matricea de adiacenta

Algoritmul: Se foloseste metoda backtracking. In stiva se genereazanodurile subgrafului. Deoarece subgraful poate avea p noduri (1≤p≤n), se va apela repetat subprogramul bt(), la fiecare apel generandu-se variantele cu p noduri. Fiecare apel al subprogramului trebuie sa genereze ,,combinari de p luate cate n de noduri din graf. La fiecare apel al subprogramului, solutia se obtine atunci cand in stiva s-au generat cele p noduri ale subgrafului. Pentru nodurile generate in stiva se afiseaza muchiile care exista in graf.

Implementarea algoritmului: Se citeste diin fisierul text adiac.txt matricea de adiacenta a unui graf neorientat. Pentru fiecare subgraf generat, se afiseaza numarul de noduri si muchiile. In variabila nr se contorizeaza numarul de subgrafuri generate. In functia tipar() se afiseaza subgarful generat.

f) Afisarea tuturor lanturilor elementare dintr-un graf folosind matricea de adiacenta

Algoritmul: Pentru generarea tuturor lanturilor elementare din graf se vor genera lanturile elementare dintre nodul x (1≤x≤n) si nodul y (1≤y≤n), folosind metoda backtracking, care se va apela pentru fiecare pereche de noduri x si y(x≠y).

Implementarea algoritmului: Se citeste din fisierul text matricea de adiacenta a unui graf neorientat. Se cauta toate lanturile elementare care exista in graf si se afiseaza. Daca nu exista nici un lant elementar, se afiseaza un mesaj.

g) Determinarea ciclurilor elementare intr-un graf folosind matricea de adiacenta

Algoritmul: Se genereaza toate lanturile elementare care pornesc din nodul x (1≤x≤n), trec prin cel putin trei noduri si se pot inchide cu nodul x. Pentru generarea acestor lanturi elementare se foloseste metoda backtracking, care se va apela pentru fiecare nod x. Solutia se obtine atunci cand nodul adaugat in stiva formeaza o muchie cu nodul x si stiva contine cel putin 3 noduri.

Implementarea algoritmului: Se citeste din fisierul text adiac.txt, matricea de adiacenta a unui graf neorientat. Se cauta toate ciclurile elementare care exista in graf si se afiseaza. Daca nu exista nici un ciclu elementar, se afiseaza un mesaj.

h) Determinarea componentelor conexe intr-un graf

Algoritmul: O componenta conexa este formata din toate nodurile intre care exista un lant elementar. Deoarece un nod nu poate sa apartina decat unei componente conexe, se va folosi un vector cu n elemente pentru a memora nodurile care au fost deja inregistrate intr-o componenta conexa. Initial, elementele vectorului au valoarea 0 (nici un nod nu a fost inregistrat intr-o componenta conexa), iar daca un nod x va fi adaugat la o componenta conexa, valoarea elementului x din vector va fi 1. Pentru a verifica daca exista un lant elemntar intre doua noduri x si y se folosste metoda backtracking.

Implementarea algoritmului: Se citeste din fisierul text adiac.txt, matricea de adiacenta a unui graf neorientat si se afiseaza componentele conexe. In vectorul v se memoreaza nodurile care au fost deja inregistrate intr-o componenta conexa. Variabila este se foloseste pentru a verifica daca s-a gasit un lant elementar intre doua noduri(are variabila 0-False, daca nu s-a gasit un lant elementar). Variabila m se foloseste pentru a numara componentele conexe identificate. Functia citeste() se foloseste pentru a citi matricea de adiacenta din fisier. Functia componente() se foloseste pentru a afisa componentele conexe ale grafului: pentru fiecare nod x (1≤x≤n) care nu a fost afisat intr-o componenta conexa (v[x]=0), se cauta toate nodurile y (1≤y≤n si y≠x) care sunt legate cu un lant elementar de nodul x. Pentru un nod y gasit, se marcheaza in vectorul v faptul ca a fost adaugat la o componenta conexa(v[y]=1).

BIBLIOGRAFIE

  Informatica pentru liceu si bacalaureat, materia de clasa a XI-a, colectia Donaris

  Informatica intensiv, manual pentru clasa a XI-a, editura Didactica si Pedagogica, R.A.

  www.programare.org