Lucrare de Laborator Nr. 1 La Matematica Discretă [PDF]

Zitiervorschau

MINISTERUL EDUCAŢIEI REPUBLICII MOLDOVA

UNIVERSITATEA TEHNICĂ A MOLDOVEI Facultatea Calculatoare, Informatică si Microelectronică Catedra Automatică si Informatică

RAPORT Lucrare de laborator nr. 1 La Matematica Discretă

Pe tema:

Păstrarea grafurilor in memoria calculatorului.

A efectuat: st. gr. AI-161

Popa Victor

A verificat: lector superior

GheorgheCeban

Chisinău 2017 1. Scopul lucrării:

1. Studierea metodelor de definire a unui graf : matricea de incidență, matricea de adiacență, liste. 2. Elaborarea unor proceduri de introducere , extragere si transformare a diferitelor forme de reprezentare internă a grafurilor cu scoaterea rezultatelor la display si imprimantă.

2. Sarcina de bază: 1. Elaborați procedura de introducere a unui graf în memoria calculatorului în formă de matrice de incidență, de matrice de adiacență și listă de adiacență cu posibilități de analiză a certitudinii. 2. Elaborați proceduri de transformare dintr-o formă de reprezentare in alta. 3. Folosind procedurile enumerate , elaborați programul care vă permite: * introducerea grafului reprezentat sub oricare forma din cele trei forme cu posibilități de corecție a datelor. * păstrarea grafului în memoria externă în formă de lista de adiacență. * extragerea informației într-una dintre cele trei forme la imprimantă și display.

3.Considerente Teoretice Numim graf o pereche ordonată de mulțimi, notată G=(X,U), unde X este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numește neorientat, altfel acesta este orientat. Așadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) și din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).

Ordine și grade Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulțimii X(G), și notăm această valoare cu se notează cu . Graful vid este graful și se notează cu este trivial dacă acesta are ordinul 0 sau 1.

. Numărul de muchii

. Spunem că un graf G

Spunem că un nod v este incident cu o muchie r dacă . Două vârfuri x și y se numesc adiacente dacă există o muchie e care le unește (cu care amândouă vârfurile sunt incidente). Două muchii sunt adiacente dacă există un nod x care să fie incident cu ambele muchii. Numim gradul unui nod particular v conectate la acel nod și se notează de obicei cu

, numărul de arce care sunt sau cu

.

Dacă adunăm gradele tuturor nodurilor din graful G, obținem de două ori numărul de muchii:

Faptul că membrul drept al ecuației va fi mereu par, implică aceeași proprietate în membrul stâng, pentru ca egalitatea să fie satisfăcută. Numim semigrad exterior Xi ,numărul de conexiuni care pleacă din Xi. Numim semigrad interior Xi,numărul de conexiuni care intra in Xi.

Metode de păstrare a grafului în memoria calculatorului:

-Matricea de incidență

-Matricea de Adiacență

-Lista de adiacență

4-Listingul Programului

4. Afisare la ecran: Introducerea matricei de incidență

b)Adăugarea unui nou virf

c)Stergerea unui vîrf

5. Concluzie: În această lucrare de laborator am făcut cunoștință cu diferite modalități de reprezentare a grafului în memoria calculatorului:Matricea de adiacență, Matricea de incidență,Lista de adiacență. Am elaborat un program care permite utilizatorului să introducă un graf aleator în una din cele 3 forme și să-îl afișeze în una din cele 3 forme.Am acumulat cunoștințe despre grafuri și metodele practice de implementare a

lor in programre. Efectuînd analiză asupra programului am ajuns la concluzia că cea mai eficientă formă de păstrare a grafului în memoria calculatorului este lista de adiacență. Matricea de incidență este mai ușor accesibilă utilizatorului care nu cunoaște formele de reprezentare a grafului în memoria calculatorului. Ciclul de verificări al corectitudinii introducerii listei de adiacență este mai mic față de cel echivalent pentru matricea de incidență, astefel programul are un timp de execuție mai redus față de alte forme. În caz de trebuință acest program poate fi dezvoltat si introdus noi metode de prelucrare și clasificarea a grafelor.