1

Ministerul Educaiei a Republicii Moldova

Universitatea Tehnic a Moldovei

Lucrare de laborator la Matematica discretLucrare de laborator nr. 1

Tema: Pstrarea grafurilor n memoria calculatorului.

A elaborat: st. gr. TI-046 Chlimari N. A verificat: Marchitan Chiinu 2005

1. SCOPUL LUCRRII:

Studierea metodelor de definire a unui graf: matrice de inciden, matrice de adiacen, liste;

Elaborarea unor proceduri de introducere, extragere i transformare a diferitor forme de reprezentare intern a grafurilor cu scoaterea rezultatelor la display sau imprimant. 2. NOTE DE CURSMetode de reprezentare a grafului

Exist trei metode de baz de definire a unui graf:

1. Matricea de inciden;

2. Matricea de adiacen;

3. Lista de adiacen (inciden).

Vom face cunotin cu fiecare dintre aceste metode.

Matricea de inciden

Este o matrice de tipul mxn, n care m este numrul de muchii sau arce (pentru un graf orientat), iar n este numrul vrfurilor. La intersecia liniei i cu coloana j se vor considera valori de 0 sau 1 n conformitate cu urmtoarea regul:

1 - dac muchia i este incident cu vrful j (dac arcul i "intr" n vrful j n cazul unui graf orientat);

0 - dac muchia (arcul) i i vrful j nu sunt incidente;

-1 - numai pentru grafuri orientate, dac arcul i "iese" din vrful j.

x1x2x3x4x5x6x7

u1-1010000

u2-1001000

u3000-1001

u400-10001

u50-110000

u60-100100

u70-100010

u800-10010

Fig. 3. Exemplu de matrice de inciden

Este uor de observat c aceast metod este de o eficacitate mic n sensul utilizrii memoriei calculatorului: fiecare linie conine doar dou elemente diferite de zero (o muchie poate fi incident cu nu mai mult de dou vrfuri).

n limbajul Pascal matricea de inciden poate fi redat printr-un tablou bidimensional mxn:

Matr_Incd: array [1..LinksCount, 1..TopsCount] of integer;

Matricea de adiacen

Este o matrice ptrat nxn, aici n este numrul de vrfuri. Fiecare element poate fi 0, dac vrfurile respective nu sunt adiacente, sau 1, n caz contrar. Pentru un graf fr bucle putem observa urmtoarele:

diagonala principal este format numai din zerouri;

pentru grafuri neorientate matricea este simetric fa de diagonala principal.

x1x2x3x4x5x6x7

x10011000

x20010110

x30000011

x40000001

x50000000

x60000000

x7 0 0 0 0 0 0 0

Fig. 4. Exemplu de matrice de adiacen

n limbajul Pascal matricea de adiacen poate fi reprezentat n modul urmtor:

Matr_Ad :array [1..TopsCount,1..TopsCount] of byte,

sau

Matr_Ad :array [1..TopsCount,1..TopsCount] of boolean;

Dup cum este lesne de observat i n acest caz memoria calculatorului este utilizat nu prea eficace din care cauz matricea de adiacen ca i matricea de inciden se vor utiliza de obicei doar n cazul n care se va rezolva o problem concret pentru care reprezentarea grafului n aceast form aduce unele faciliti algoritmului respectiv.

Pentru pstrarea grafurilor n memoria calculatorului (n deosebi, memoria extern) se va utiliza una din posibilitile de mai jos.

Lista de adiacen i lista de inciden

Lista de adiacen este o list cu n linii (dup numrul de vrfuri n), n linia cu numrul i vor fi scrise numerele vrfurilor adiacente cu vrful i.

Lista de inciden se definete analogic cu deosebirea c n linia i vor fi scrise numerele muchiilor (arcelor) incidente cu vrful i.

Reprezentarea grafurilor prin intermediul acestor liste permite utilizarea mai eficace a memoriei calculatorului, ns aceste forme sunt mai complicate att n realizare, ct i n timpul procesrii. Pentru a lua n consideraie lungimea variabil a liniilor vor fi utilizate variabile dinamice i pointeri.

Vom exemplifica pentru un graf cu n vrfuri. Deoarece fiecare element al listei conine numere de vrfuri este evident s considerm c vom avea un ir de variabile dinamice de tip INTEGER care se vor afla n relaia respectiv de precedare (succedare). Aceast relaie se va realiza prin pointeri, unii mpreun cu variabila de tip ntreg n nregistrarea (Pascal: record). Pentru a pstra indicatorii de intrare n aceste iruri se va folosi un tablou unidimensional de indicatori de lungime n. n calitate de simbol de terminare a irului se va utiliza un simbol care nu a fost folosit la numeraia vrfurilor (de exemplu 0), care va fi introdus n calitate de variabil de tip ntreg al ultimului bloc.

De exemplu, lista de adiacen :

1 - 3, 4, 0

2 - 3, 5, 6, 0

3 - 6, 7, 0

4 7, 0

5 - 0

6 - 0

7 - 0

va avea urmtoarea reprezentare intern:

variabile dinamice (pointer i variabil de tip ntreg)

masiv de indicatori

Fig. 5. Reprezentarea intern a listei de adiacen

Va fi necesar de realizat urmtoarea declaraie:

Type

BlockPtr = ^BlockType;

BlockType = record;

Number : integer;

Point : BlockPtr;

end;

Var In_Ptr :array [1..TopsCount] of BlockPtr;

Lista de adiacen (i realizarea reprezentrii interne) se va implementa cu ajutorul procedurii New (BlockPtr_Type_Variable), n care BlockPtr_Type_Variable este o variabil de tip BlockPtr.

3. SARCINA DE BAZ

1. Elaborai procedura introducerii unui graf n memoria calculatorului n form de matrice de inciden, matrice de adiacen i list de adiacen cu posibiliti de analiz a corectitudinii.

2. Elaborai proceduri de transformare dintr-o form de reprezentare n alta.

3. Folosind procedurile menionate elaborai programul care va permite:

introducerea grafului reprezentat sub oricare din cele trei forme cu posibiliti de corecie a datelor;

pstrarea grafului n memoria extern n form de list de adiacen;

extragerea informaiei ntr-una din cele trei forme la imprimant sau display.

Listingul

//Lucrare de laborator Nr1.

// Tema:Memorarea grafului in memorie sub diferite forme.

#include

#include

#include

#include

#include

int n,u,m,g[40][20],g1[20][20],i,j,k;

struct lista {

int c;

struct lista *urm;

} start[20],*nod;

//===============================================================

void Virf()

{ clrscr();

_setcursortype(_NORMALCURSOR);

printf("\n\t");

textcolor(3); cprintf("Introduceti numarul de virfuri : ");

scanf("%d",&n);

}

//--------------------------------------------------------------------

void Afis()

{ printf("\n\t");

textcolor(30);

}

//-------------------------------------------------------------------

void Pauza()

{ textcolor(2); cprintf("\n Tastati o tasta pentru a continua...");

textcolor(15);

getch();

}

//-------------------------------------------------------------------

/* Prezentarea temei */

void Prezt()

{ clrscr();

_setcursortype(_NOCURSOR);

printf("\n\n\n\n\t\t");

textcolor(3); cprintf("Lucrare de laborator Nr1 la Matematica Discreta.");

printf("\r\n\n\t\t");

cprintf("Memorarea grafului in memorie sub diferite forme.");

textcolor(15);

getch();

}

//===============================================================

void InMIn()

{ printf("\n\t");

textcolor(3); cprintf("Introduceti numarul de arce : ");

scanf("%d",&u);

Afis(); cprintf("Introduceti matricea de incidenta:\n\n\n");

textcolor(2); cprintf("\r In ");

textcolor(11);

for(i=1;i=0;j--) if(i