Grafuri Neorientate

- Scopul proiectului: obtinerea atestatului profesional de informatica de la sfarsitul clasei a 12-a.

- Limbajul in care a fost creat: Borland Pascal 7.0

- Configuratia minima necesara: calculatorul trebuie sa aiba minim un procesor 286 la 33 Mhz.

- 90% din informatiile legate de proiect au fost invatate la cursurile de informatica din scoala, restul au fost obtinute prin intermediul diferitelor materiale didactice enumerate in bibliografia lucrarii.

- Perspectivele de dezvoltare ale proiectului: Se poate imbunatati si completa cu noi informatii; se poate transforma intr-un curs de teoria grafurilor.

- Modulele lucrarii: citirea si constrirea matricii de adiacenta; afisarea matricii de adiacenta; calcularea gradelor; parcurgerea grafurilor; drumuri in grafuri; conexitatea; alte proprietati ale grafurilor.

- Am folosit 3 fisiere: atestat.pas, matrice.txt, mat_cost.txt.

Grafuri neorientate - introducere

Un graf neorientat reprezinta o pereche de multimi (X,U), unde X este o multime finita si nevida de elemente numite noduri (varfuri), iar U o multime de perechi neordonate de elemente din X numite muchii. Notam G = (X,U) un graf neorientat.

O muchie uEURU este deci o pereche (x,y) de varfuri distincte din X si notam u = [x,y]. Vom spune ca varfurile x si y sunt adiacente in G, iar despre u si x ca sunt incidente la fel ca si u si y, x si y reprezinta extremitatile muchiei u, iar daca sunt doua muchii care au o extremitate comuna, ele vor fi numita incidente.

Sa dam un exemplu. Fie G = (X,U) astfel incat:

X = {1,2,3,4,5,6,7,8,9,10,11}, iar

U = {[1,5],[3,7],[4,6],[9,8],[10,2],[1,2],[9,4],[1,10],[6,8],[2,6]}

Reprezentarea in plan a acestui graf este data in figura 1.

Manual de informatica(varianta Pascal) pentru clasa a XI-a - Tudor Sorin ,Editura LS Infomat 2002

- Informatica "Probleme rezolvate pentru Liceu si Bacalaureat"- Adrian Balasko, Marius Vulpe, Editura Dacia Educational.

- Limbajul Pascal - Corina Corici, Marinel Serban, Dorin Manz

Editura Libbris 1994.

- Bazele Informaticii - Adrian Atanasiu, Rodica Pintea, Editura Petrion 2003.

- Analiza si sinteza algoritmilor, Livovschi Georgescu H. , 1996

- Probleme de combinatorica si teoria grafurilor, Editura Didactica si Pedagogica, Bucuresti, 1981, -Tomescu Ion

- Probleme de Informatica - Atanasiu Andrei, Editura Figaro, Bacau, 1998.