LUCRARE DE ATESTAT PROFESIONAL
TEMA GRAFURI EULERIENE SI HAMILTONIENE
CUPRINS
Memoriu justificativ..........pag.3
Teoria grafurilor ...........pag.4
Grafuri euleriene si hamiltoniene ......pag.9
Descrierea aplicatiilor .........pag
Aplicatiile (codul sursa) .......pag.23
'Cu cit esti mai intelept, cu atit iti dai mai bine seama ca pe lume exista multi oameni deosebiti. Oamenii de duzina nu observa nici o deosebire intre semenii lor.'
'Omul este o trestie, cea mai fragila din intreaga natura, dar este o trestie ganditoare'
Blaise Pascal
MEMORIU JUSTIFICATIV
Motivul alegerii acestei teme este:
PREZENTAREA IN LIMBAJUL DE PROGRAMARE PASCAL A UNOR PROBLEME. ISI PROPUNE SA EXPUNA CAT MAI MULTE DINTRE CUNOSTINTELE ACUMULATE DEA LUNGUL CELOR 4 ANI DE LICEU SI DE ASEMENEA CAT DE ADEVARAT ESTE FAPTUL CA TOTUL A PORNIT DE LA EXPERIENTELE UNOR OANEMI CU NUME SONOR IN STIINTA.
PE LANGA NOTIUNILE DE TEORIE CE VOR FACE OBIECTUL ACESTEI LUCRARI, GRAFURILE EULERIENE SI HAMILTONIENE, VOI MAI PREZENTA EXPLICAREA APROFUNDATA A TUTUROR PASILOR ALGORITMILOR SI ATASAREA FISIERULUI CE DEMONSTREAZA CORECTITUDINEA PROBLEMELOR.
CAPITOLUL 1
TEORIA GRAFURILOR
INTRODUCERE
Conform DEX notiunea de graf reprezinta ansamblul a doua multimi disjuncte, intre care s-a stabilit o corespondenta.
Teoria grafurilor este disciplina care studiaza proprietatile topologice ale structurii grafelor.
Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri 555c21f 51;i amuzamente matematice care au atras atentia matematicienilor (Euler , Hamilton). Aceasta problema celebra a fost enuntata de matematicianul Euler, care impreuna cu Hamilton au fost cei care au pus bazele teoriei grafurilor.
Data nasterii teoriei grafurilor este considerata a fi anul 1736, cand matematicianul Leonhard Euler a publicat un articol in care a clarificat 'Problema celor 7 poduri din Kaliningrad' (Euler s-a intrebat daca poate face o plimbare care sa includa in traseul sau toate cele 7 poduri, astfel incat fiecare pod sa fie traversat o singura data si sa revina la punctul de plecare).
In general, pentru situatiile care necesita la rezolvare un oarecare efort mintal (si un caz tipic este cel al celor din economie), se cauta, in primul rand, o metoda de reprezentare a lor care sa permita receptarea intregii probleme dintr-o privire (pe cat posibil) si prin care sa se evidentieze cat mai clar toate aspectele acesteia.
In acest scop se folosesc imagini grafice gen diagrame, schite, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate in special pentru vizualizarea sistemelor si situatiilor complexe. In general, vom reprezenta componentele acestora prin puncte in plan iar relatiile (legaturile, dependentele, influentele etc) dintre componente prin arce de curba cu extremitatile in punctele corespunzatoare. Intre doua puncte pot exista unul sau mai multe segmente (in functie de cate relatii dintre acestea, care ne intereseaza, exista) iar segmentelor li se pot asocia sau nu orientari (dupa cum se influenteaza cele doua componente intre ele), numere care sa exprime intensitatea relatiilor dintre componente etc.
Este evident, totusi, ca aceasta metoda are limite, atat din punct de vedere uman (prea multe puncte si segmente vor face desenul atat de complicat incat se va pierde chiar scopul pentru care a fost creat - claritatea si simplitatea reprezentarii, aceasta devenind neinteligibila) cat si din punct de vedere al tehnicii de calcul (un calculator nu poate 'privi' un desen ca un om).
Din acest motiv, alaturi de expunerea naiv-intuitiva a ceea ce este un graf, data mai sus, se impune atat o definitie riguroasa cat si alte modalitati de reprezentare a acestora, adecvate in general rezolvarilor matematice.
Se numeste multigraf un triplet G = (X, A, f) in care X si A sunt doua multimi iar f este o functie, definita pe produsul vectorial al lui X cu el insusi (X2 = X×X), care ia valori in multimea partilor multimii A (notata P(A)). Multimea X se numeste multimea nodurilor multigrafului si elementele sale se numesc noduri (sau varfuri) ale multigrafului, iar A reprezinta multimea relatiilor (legaturilor) posibile intre doua noduri ale multigrafului.
Se numeste graf orientat un multigraf in care multimea A are un singur element: A = .
In acest caz multimea partilor multimii A are doar doua elemente: multimea vida si intreaga multime A. Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea A atunci spunem ca exista arc de la nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj). Nodul xi se numeste nod initial sau extremitate initiala a arcului (xi,xj) iar nodul xj se numeste nod final sau extremitate finala a arcului (xi,xj). Arcul (xi,xj) este incident spre interior varfului xj si incident spre exterior varfului xi. Daca pentru un arc nodul initial coincide cu nodul final atunci acesta se numeste bucla. Nodurile xi si xj se vor numi adiacente daca exista cel putin unul din arcele (xi,xj) si (xj,xi).
Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea vida atunci spunem ca nu exista arc de la nodul xi la nodul xj.
Este evident ca a cunoaste un graf orientat este echivalent cu a cunoaste varfurile si arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este multimea varfurilor sale iar U multimea arcelor sale.
De asemenea, putem cunoaste un graf orientat cunoscand multimea nodurilor si, pentru fiecare nod, multimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X,Γ) unde X este perechea nodurilor iar Γ este o functie definita pe X cu valori multimea partilor lui X, valoarea acesteia intr-un nod xi, Γ(xi) ⊆ X fiind multimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea initiala.
Se numeste graf neorientat un multigraf in care multimea A are un singur element iar functia f are proprietatea: f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi si xj din X
In aceste conditii, daca f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientata este o muchie iar daca f[(xi,xj)] = f[(xj,xi)] = spunem ca nu exista muchie intre varfurile xi si xj.
Deoarece, in cele mai multe din cazurile practice care vor fi analizate in acest capitol, situatia este modelata matematic printr-un graf orientat, vom folosi, pentru simplificarea expunerii, denumirea de graf in locul celei de graf orientat iar in cazul in care graful este neorientat vom specifica acest fapt la momentul respectiv.
1.2. Concepte de baza in teoria grafurilor
semigraf interior al unui nod xk: este multimea arcelor = care sunt incidente spre interior nodului xk
semigraf exterior al unui nod xk: este multimea arcelor = care sunt incidente spre exterior nodului xk
semigradul interior al unui nod xk: este numarul arcelor care sunt incidente spre interior nodului xk = cardinalul lui si se noteaza cu ; kxU kx
semigradul exterior al unui nod xk: este numarul arcelor care sunt incidente spre exterior nodului xk = cardinalul lui si se noteaza cu ; kxU kx
gradul unui nod xk: este suma semigradelor nodului xk kx kx kx
nod izolat: este un nod cu gradul 0;
7. nod suspendat: este un nod cu gradul 1;
arce adiacente: arce care au o extremitate comuna;
9. drum intr-un graf: o multime ordonata de noduri ale grafului: (x , x , , xk), cu proprietatea ca exista in graf toate arcele de forma (xi,xi+1) i = 1,,k-1;
lungimea unui drum: este numarul arcelor care il formeaza;
drum elementar: un drum in care fiecare nod apare o singura data;
12. drum simplu: un drum in care fiecare arc apare o singura data;
putere de atingere a unui nod xi < X in graful G: numarul de noduri la care se poate ajunge din xi. Puterea de atingere se noteaza cu p(xi i n si evident p(xi ix
drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;
15. drum eulerian: un drum simplu care contine toate arcele grafului;
lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;
17. circuit: un drum in care nodul initial coincide cu cel final;
18. circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;
circuit simplu: un drum in care fiecare arc apare o singura data;
circuit hamiltonian: un circuit care trece prin toate nodurile grafului;
ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;
ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;
ciclu simplu: un ciclu in care fiecare arc apare o singura data; Observatie: Intr-un graf neorientat notiunile de drum si lant sunt echivalente si de asemenea cele de circuit si ciclu.
graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;
subgraf al unui graf G = (X, ): este un graf G'(X', ') unde X' X si '(xi (xi X' pentru orice xi X'; 113
Elemente de teoria grafurilor
graf redus al unui graf G = (X,U): este un graf G (X ,U ) unde X este formata din multimile unei partitii de multimi nevide ale lui X, iar () exista doar daca i j si exista cel putin un arc in U, de la un nod din la un nod din *iX,*jX*iX*jX.
graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum;
graf simplu conex: este un graf in care intre oricare doua noduri exista cel putin un lant; Observatie: Pentru grafuri neorientat notiunile de tare conex si simplu conex sunt echivalente, graful numindu-se doar conex;
componenta tare conexa a unui graf G = (X,U): este un subgraf al lui G care este tare conex si nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, intre oricare doua noduri din componenta exista cel putin un drum si nu mai exista nici un nod in afara componentei legat printr-un drum de un nod al componentei).
. NOTIUNEA DE GRAF
Desi definitiile date anterior ,referitoare la notiunea de graf sunt clare si complete, tin sa dezvolt aceasta pentru o mai buna intelegere.
Se numeste graf orice multime finita X prevazuta cu o relatie binara interna U. Graful se noteaza G=(X,U).
Grafurile pot fi de doua tipuri:
Grafuri orientate
(digrafuri);
Grafuri neorientate.
Se numeste graf orientat perechea ordonata G= (X,U) in care relatia binara nu este simetrica.
Se numeste graf neorientat perechea ordonata G=(X,U) in care relatia binara este simetrica.
1.3.a.Grafuri neorientate
Definitie :Se numeste graf neorientat o pereche ordonata de multimi (X,U), unde :
X este o multime finita si nevida de elemente numite varfuri sau noduri
U este o multime de perechi neordonate de cate doua elemente din X, numite muchii sau arce.
Asadar, un graf neorientat poate fi reprezentat sub forma unei figuri geometrice alcatuita din puncte (varfuri, noduri) si linii drepte sau curbe care unesc aceste puncte (muchii, arce).
Vom folosi:
pentru grafuri neorientate termenii de varf si muchie ;
pentru grafuri orientate termenii de nod si arc
Daca o muchie trece prin nodurile x si y, atunci ea se noteaza (x,y) sau [x,y].
Pe caz general, intr-un graf neorientat G = (X,U) notam :
m → numarul muchiilor ; n → numarul nodurilor ;
X = 
→ multimea varfurilor ;
U = 
→ multimea muchiilor ;
o muchie uk este o pereche neordonata (a,b) alcatuita din doua elemente din X.
Definitie: Pentru o muchie uk = (a,b) , vom spune ca :
varfurile a si b sunt adiacente si se numesc extremitatile muchiei uk ;
muchia uk si varful a sunt incidente in graf. La fel, muchia uk si varful b ;
muchia (a,b) este totuna cu (b,a) (nu exista o orientare a muchiei).
Definitie: Gradul unui varf x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).
Un varf care are gradul 0 se numeste varf izolat.
Un varf care are gradul 1 se numste varf terminal.
Teorema Intr-un graf G = (X,U), cu n varfuri si m muchii , suma gradelor tuturor varfurilor este egala cu 2 * numarul muchiilor.
Exemplu :
Avem pentru graful considerat :
- X = → multimea varfurilor (nodurilor)
- U= → multimea muchiilor (arcelor)
- Muchiile sunt : u1 = (1,2) ; u2 = (2,3) ; u3 = (3,4) ; u4 = (2,4) ; u5 = (5,6) ;
- d(1) = 1 ; d(2) = 3 ; d(3) = 2 ; d(4) = 2 ; d(5) = 1 ; d(6) = 1 ; d(7) = 0 ;
- varful 7 este varf izolat ; vafurile 5 si 6 sunt varfuri terminale .
1.3.b.Metode de reprezentare
Este o matrice A cu n linii si n coloane, in care elementele a[i,j] se definesc astfel:
Deoarece muchia (a,b) este totuna cu muchia (b,a), rezulta ca a[i,j] = a[j,i] ,
oricare ar fi i
,j 
.
Din acest motiv, matricea de adiacenta pentru un graf neorientat este
simetrica fata de diagonala principala.
Pentru
fiecare nod i , cu i,
formam lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt
extremitati ale muchiilor ce trec prin nodul i.
Reprezentam graful de mai sus prin primele doua metode :
 |
2. 
Pe fiecare linie i din listele vecinilor contine indicii coloanelor pe care se gasesc valori de 1 in linia i a matricei de adiacenta.
Citirea unui graf memorat cu ajutorul matricei de adiacenta
Varianta 1:
Citirea numarului de varfuri,citirea regiunii de deasupra diagonalei principale urmata de simetrizare.
var a:array[1..120,1..120] of 0..1;
x,d,i,j,n:byte;
begin
write('nr de varfuri:=');readln(n);
for i:=1 to n-1 do
for j:=i+1 to n do begin
write('a[',i,',',j,']:=');readln(a[i,j]);
a[j,i]:=a[i,j];
end;
end.
Varianta 2:
Se citesc n-nr de varfuri,m-nr de muchii;
-initializarea matricei de adiacenta cu zero;
-citirea extremitatii fiecarei muchii;
-completarea matricei de adiacenta
var a:array[1..120,1..120] of 0..1;
x,d,i,j,n:byte;
begin
write('n:=');readln(n);
write('m:=');readln(m);
for i:=1 to n do
for j:=1 to n do a[i,j]:=0;
for i:=1 to m do begin
writeln('Muchia ',i,' este:');
readln(x,y);
a[x,y]:=1;
a[y,x]:=1;
end;
end.
Definitie: Fie graful G = (X,U).
Un graf partial al lui G este
un graf G1 = (X,V), cu V 
U.
Altfel spus, un graf partial G1 al lui G, este chiar G, sau se
obtine din G pastrand toate varfurile si suprimand niste
muchii.
Definitie.Fie graful G = (X,U).
Un subgraf al lui G este un graf G1
= (Y,T), cu Y 
X si
T U,
iar T va contine numai muchiile care au ambele extremitati in Y.
Altfel spus, un subgraf G1 al lui G se obtine din G eliminand
niste varfuri si pastrand doar acele muchii care au ambele
extremitati in multimea varfurilor ramase.
Exemplu :
-graful
initial
Am eliminat muchiile u3 si u4, pastrand toate varfurile.
1.4.Notiunile de lant si ciclu
Definitie.Se numeste lant in graful G, o succesiune de
varfuri L = (z1,z2,,zk), unde z1,z2,,zk
X, cu proprietatea ca oricare doua varfuri consecutive sunt
adiacente, adica exista muchiile [z1,z2], [z2,z3],.,
[zk-1,zk] U.
Varfurile z1 si zk se numesc extremitatile lantului, iar numarul de muchii care intra in componenta sa reprezinta lungimea lantului.
Daca varfurile z1,z2,,zk sunt distincte doua cate doua, lantul se numeste elementar. In caz contrar, lantul este ne-elementar.
Exemplu :
L1 = (1,2,3,4) - lant elementar
L2 = (1,2,4,3,2,3,4) - lant ne-elementar
L3 = (2,4,3,2,1) - lant ne-elementar
L4 = (6,5,1,2,3,4) -lant elementar
Definitie.Se numeste ciclu intr-un graf, un lant L = (z1,z2,,zk) cu proprietatea ca z1 = zk si muchiile [z1,z2], [z2,z3],., [zk-1,zk] sunt distincte doua cate doua.
Def. Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclu se numeste elementar. In caz contrar, el este ne-elementar.
C1 = (2,3,4,2) - ciclu elementar
C2 = (1,2,4,3,1) - ciclu elementar
C3 = (5,2,4,3,1,5 - ciclu elementar
C4 = (1,2,3,4,2,5,1) - ciclu ne-elementar
C5 = (5,2,3,4,2,1,5) - ciclu ne-elementar
Obs. In cadrul unui lant, muchiile se pot repeta, dar in cadrul unui ciclu ele trebuie sa fie distincte.
Definitie.Un graf G este conex daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga.
Obs. Intr-un graf conex, luand oricare doua varfuri , putem gasi cel putin un traseu(lant) care porneste dintr-un varf si ajunge in celalalt.
Definitie.Se numeste componenta conexa a grafului G =(X,U), un subgraf G1=(X1,U1) a lui G,conex, cu proprietatea ca nu exista nici un lant care sa lege un varf din X1 cu un varf din X-X1.
Exemplu.
In acest exemplu exista 3 componente conexe:
G1 =(X1,U1), cu X1= si U1=
G2 =(X2,U2), cu X2= si U2=
G3 =(X3,U3), cu X3= si U1= Ø
Problema: Sa se determine daca un graf e conex sau nu.
Program conex;
Var a:array[1..50,1..50] of integer;
Viz: array[1..50] of boolean;
i, n: integer;
f:boolean;
procedure DF(x:integer);
end;
procedure citire;
end;
BEGIN
Citire; DF(1);
f:=true;
for i:=1 to n do if not viz[i] then f:=false;
if f then write('Graful este conex')
else write('Graful nu este conex');
END.
1.6.Parcurgerea grafurilor
Parcurgerea grafurilor se realizeaza cu scopul vizitarii varfurilor acestora.Fiecare varf se va vizita o singura data,cu scopul prelucrarii informatiei.
Parcurgerea:-in latime
-in adancime
Parcurgerea in latime (BF-Breath First)
Se viziteaza la inceput varful initial,apoi se viziteaza vecinii nevizitati ai acestuia,apoi vecinii nevizitati ai vecinilor si asa mai departe.
Program pentru BF
Se va utiliza o coada.Initial,in coada se afla doar varful initial,la fiecare pas se va prelucra varful aflat la inceputul cozii.Consideram toti vecinii nevizitati ai acestuia si ii adaugam in coada dupa care, varful fiind prelucrat va fi eliminat din coada.Prelucrarea se va face atat timp cat exista elemente in coada.
Pentru a retine varfurile vizitate folosim un vector boolean cu semnificatia:
viz[i]=true,daca varful i a fost vizitat
=false,altfel
Initial,toate varfurile sunt nevizitate.
var c:array[1..20]f byte;
a:array[1..20,1..20]of 0..1;
viz:array[1..20]of boolean;
vi,vc,n,u,i,p:byte
begin
write('varf initial:=');readln(vi);
for i:=1 to n do viz[i]:=false;
p:=1;
u:=1;
c[1]:=vi;
viz[vi]:=true;
while p<=u do begin
vc:=c[p];
for i:=1 to n do
if a[vc,i]=1 and not viz(i) then
begin
u:=u+1;
c[u]:=i;
viz[i]:=true;
end;
p:=p+1;
end;
for i:=1 to n do write(c[i],' ');
readln;
end.
PARCURGEREA IN ADANCIME(DF-Depth First)
Se porneste din varful initial,se viziteaza primul vecin nevizitat al acestuia,apoi primul vecin nevizitat al vecinului,si asa mai departe.Cand un varf nu mai are vecini nevizitati se realizeaza o intoarcere in varful precedent lui de unde se continua prelucrarea.
Vom utiliza o procedura recursiva,vectorul viz de vizitate,matricea a de adiacenta ,vectorul df in care vom retine sucesiunea varfurilor in parcurgerea varfurilor in adancime si o variabila nvv-nr de varfuri vizitate.
var a:array[1..20,1..20]of 0..1;
viz:array[1..20]of boolean;
df:array[1..20]of byte;
n,vi,nvv,i,j:byte;
procedure d_f(vc:byte);
var i:byte;
begin
viz[vc]:=true;
nvv:=nvv+1;
df[nvv]:=vc;
for i:=1 to n do
if (a[vc,i]=1) and (not viz[i]) then d_f(i);
end;
begin
for i:=1 to n do viz[i]:=false;
nvv:=0;
d_f(vi);
for i:=1 to n do write(df[i],' ');
readln;
end.
CAPITOLUL II
Grafuri hamiltoniene si grafuri euleriene
Definitie Se numeste ciclu hamiltonian intr-un graf, un
ciclu elemenar care contine toate varfurile grafului.
Definitie: Se numeste graf hamiltonian , un graf care
contine un ciclu hamiltonian.
Exemplul 1:
Ciclul C = [1,2,3,5,4,1] este un ciclu hamiltonian => graf hamiltonian (muchiile sunt distincte doua cate doua)
Exemplul2:
Graful din acest exemplu este hamiltonian, deoarece ciclu C =[2,5,1,3,4,2] este
elementar (pleaca din varful 2 si se intoarce tot in 2, iar muchiile [2,5], [5,1], [1,3], [3,4], [4,2] sunt distincte doua cate doua) si in plus contine toate varfurile.
Definitie Se numeste lant hamiltonian intr-un graf, un lant elementar care contine toate varfurile grafului.
Teorema: Daca intr-un graf G(X,U) cu n≥3 varfuri,
gradul fiecarui varf x verifica conditia 
, atunci graful este
hamiltonian.
Definitie: Se numeste ciclu eulerian intr-un graf, un ciclu care contine toate muchiile grafului.
Definitie: Se numeste graf eulerian, un graf care contine un ciclu eulerian.
Exemplul1:
Ciclul C=[1,2,3,6,7,8,3,4,5,1] este eulerian, deoarece muchiile sale consecutive sunt distincte doua cate doua (ciclul nu trece de doua ori prin acelasi ciclu).
Exemplul 2:
Pentru acest graf, ciclu C = [2,1,5,2,3,4,2] este eulerian, deoarece pleaca din 2 si se intoarce tot in doi, iar muchiile sale consecutive, adica [2,1], [1,5], [5,2], [2,3], [3,4], [4,2] sunt distincte doua cate doua si reprezinta toate muchiile grafului.
Teorema: Un graf fara varfuri izolate este eulerian, daca si numai daca este conex si gradele tuturor varfurilor sunt numere pare.
Demonstratie
Fie un graf fara varfuri izolate care contine un ciclu eulerian (graf eulerian).
Demonstram ca graful este conex si gradele tuturor varfurilor sale sunt pare.
a) Graful este conex. Fie x si y doua varfuri ale grafului. Cum x nu este izolat, rezulta ca exista o muchie incidenta lui x. Tot asa, exista o muchie incidenta cu y. Cum ciclul este eulerian (contine toate muchiile) va contine si cele doua muchii. Prin urmare, x si y sunt unite printr-un lant.Cum x si y au fost alese intamplator, rezulta ca oricare duoa varfuri sunt unite printr-un lant.In concluzie, graful este conex.
b) Gradele tuturor muchiilor sunt pare. Sa presupunem ca varful x apare de k ori in lant. La fiecare aparitie a lui x , se vom d(x)=2k. Cum varful x a fost luat arbitrar, rezulta ceea ce trebuia demonstrat.
Sa presupunem ca graful G este conex si are gradele tuturor varfurilor numere pare.Sa aratam ca G contine un ciclu eulerian.
Pornim cu unul din varfurile grafului . Fie el v. Intentionam sa formam un ciclu , care incepe si se termina cu v.Conform ipotezei,exista un numar par de muchii incidente cu v. Selectam una dintre ele incidenta la varful v1.Atat in v cat si in v1 raman cu un numar impar de muchii incidente. Selectam, o muchie incidenta la v1 si repetam rationamentul. Multimea varfurilor este finita. In concluzie, vom ajunge, la un moment dat , intr-unul din varfurile prin care am trecut. Daca acesta este chiar v am obtinut ciclul cautat. Sa presupunem ca am ajuns intr-un alt varf decat v. Tinand cont de algoritm au fost selectate un numar par de muchii incidente acestuia. Prin urmare, exista o muchie pe care o putem selecta. Porcesul se repeta pana cand selectam o muchie incidenta la v.
In acest caz am gasit un ciclu care incepe si se termina in v. Il notam cu " c" .
Exista doua posibilitati:
Ciclul obtinut este eulerian, caz in care teorema este demonstrata.
Ciclul nu este eulerian. In acest caz, operam asupra grafului G, renuntand la muchiile selectate.In acest fel, se obtine un graf partial al lui G pe care il notam cu H.In acelasi timp, retinem ciclul gasit. Din analiza grafului H rezulta:
Gradele tuturor varfurilor sale sunt pare ;
Multimea muchiilor lui H este nevida;
Cel putin una din muchiile lui H are o extremitate comuna (varf) cu una din muchiile ciclului selectat;
Pornind dintr-un varf comun, selectam intocmai ca la inceput un alt ciclu c1. Formam din c si c1 un nou ciclu .Extragem muchiile comune ciclului c1 si apoi procedam in mod similar.
Repetam procedeul pana la selectia unui ciclu eulerian.
CAPITOLUL III
DESCRIEREA APLICATIILOR
Problema 1:
Se citesc m perechi de numere intregi (x,y) reprezentand extremitatile muchiilor unui graf neorientat cu n varfuri si m muchii. Sa se verifice daca graful este eulerian tiparindu-se un mesaj. Se va folosi teorema conform careia un graf este eulerian daca este conex si gradele tuturor varfurilor sunt numere pare.
Se defineste vectorul d =(d[1],d[2],.,d[n]) in care se vor memora gradele tuturor varfurilor 1,2,3,.,n.
In procedura se introduce graful de la tastatura, cu constructia matricei de adiacenta si a vectorului d.
Se initializeaza vectorul d si matricea de adiacenta a cu 0 (zero).
Intr-un ciclu k=1,2,.,n se citeste m perechi de numere intregi (x,y) ( cu validare: repeta citirea lui x,y, pana cand valorile introduse sunt cuprinse intre 1 si n).
Pentru fiecare pereche (x,y):
se marcheaza in matrice existenta muchiei (x,y)
se incrementeaza gradele varfurilor x si y .
Conform teoremei ,un graf este eulerien daca este conex si gradele tututror varfurilor sunt pare.Pentru aceasta functia verifica daca gradele tuturor varfurilor sunt numere pare, returnand TRUE sau FALSE.
Initial, se considera ca toate gradele sunt pare si variabila ok:=true.Apoi, se parcurge intr-un ciclu vectorul gradelor d, cu i de la 1 la n .Pentru fiecare i se testeaza gradul varfului i .Daca acesta este impar ,graful nu poate avea toate gradele pare, deci ok:=false.
Pentru verificarea conexitatii grafului se folosesc cele doua functii:
Functia care verifica daca in graf mai exista varfuri nevizitate in urma parcurgerii BF.In cazul in care nu mai exista aceasta va returna -1, altfel va returna primul nod nevizitat.
Functia care verifica daca graful este conex sau nu returnand TRUE sau FALSE.
In programul principal:
se apeleaza procedura citire_graf;
se apeleaza functia conex: daca aceasta a returnat TRUE graful este conex,atunci:
& daca gradele tuturor varfurilor sunt pare (functia grade_pare a returnat TRUE),atunci graful este conex si eulerian;
& in caz contrar, graful este conex dar nu si eulerian;
daca functia conex a returnat FALSE, atunci graful nu este conex, ca atare nu este eulerian.
Problema 2:
Se citesc de la tastatura doua numere naturale m si n reprezentand numarul de muchii respectiv numarul de varfuri ale unui graf neorientat, apoi m perechi de numere naturale de forma (x,y), elementele fiecarei perechi reprezentand varfurile extremitati ale unei muchii. Scrieti un program care testeaza daca graful este hamiltonian,afisand un mesaj corespunzator.
Se defineste vectorul d =(d[1],d[2],.,d[n]) in care se vor memora gradele tuturor varfurilor 1,2,3,.,n.
In procedura se introduce graful de la tastatura, cu constructia matricei de adiacenta si a vectorului d.
Se initializeaza vectorul d si matricea de adiacenta a cu 0 (zero).
Intr-un ciclu k=1,2,.,n se citeste m perechi de numere intregi (x,y) ( cu validare: repeta citirea lui x,y, pana cand valorile introduse sunt cuprinse intre 1 si n).
Pentru fiecare pereche (x,y):
se marcheaza in matrice existenta muchiei (x,y)
se incrementeaza gradele varfurilor x si y .
Conform teoremei , un graf cu n>=3 varfuri, este hamiltonian daca gradul fiecarui varf verifica conditia d[i] >=n/2.Pentru aceasta functia verifica daca gradele tuturor varfurilor verifica aceasta conditie, returnand TRUE sau FALSE.
Initial, se considera ca toate gradele verifica aceasta conditie si variabila ok:=true. Apoi, se parcurge intr-un ciclu vectorul gradelor d, cu i de la 3 la n .Pentru fiecare i se testeaza gradul varfului i .Daca acesta este <n/2 ,graful nu indeplineste conditia teoremei , deci ok:=false.
Pentru verificarea conexitatii grafului se folosesc cele doua functii:
Functia care verifica daca in graf mai exista varfuri nevizitate in urma parcurgerii BF.In cazul in care nu mai exista aceasta va returna -1, altfel va returna primul nod nevizitat.
Functia care verifica daca graful este conex sau nu returnand TRUE sau FALSE.
In programul principal:
se apeleaza procedura citire_graf;
daca functia grade a returnat TRUE ,atunci graful este hamiltonian.
daca functia grade a returnat FALSE, atunci graful nu este hamiltonian.
CAPITOLUL IV
Aplicatie: Graf eulerian
Program graf_eulerian;
var m,n,pi,ps,prim,p,nc:integer;
a:array[1..50,1..50] of integer;
d,c,viz:array[1..50] of integer;
procedure citire_graf;
var i,j,k,x,y:integer;
begin
write('numarul de varfuri='); readln(n);
write('numarul de muchii='); readln(m);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;
for i:=1 to n do d[i]:=0;
for k:=1 to m do
begin
writeln('dati muchia cu nr de ordine',k,'=');
repeat
readln(x,y);
until (x>=1) and (x<=n) and (y>=1) and (y<=n);
a[x,y]:=1;
a[y,x]:=1;
d[x]:=d[x]+1;
d[y]:=d[y]+1;
end;
end;
function nevizitat:integer;
var prim_nev,j:integer;
begin
prim_nev:=-1;
j:=1;
while (j<=n) and (prim_nev=-1) do
begin
if viz[j]=0 then prim_nev:=j;
j:=j+1;
end;
nevizitat:=prim_nev;
end;
function conex:boolean;
var k,pi,ps,z:integer;
conex:boolean;
begin
for k:=1 to n do c[k]:=0;
for k:=1 to n do viz[k]:=0;
write('varful de plecare='); readln(prim);
pi:=1;
ps:=1;
c[pi]:=prim;
viz[prim]:=1;
while ps<=pi do
begin
z:=c[ps];
for k:=1 to m do
if (a[z,k]=1) and (viz[k]=1) then
begin
pi:=pi+1;
c[pi]:=k;
viz[k]:=1;
end;
ps:=ps+1;
end;
for k:=1 to pi do write(c[k]:3);
if nevizitat=-1 then conex:=TRUE
else conex:=FALSE;
end;
function grade_pare:boolean;
var i:integer;
ok:boolean;
begin
ok:=TRUE;
for i:=1 to n do
if d[i]mod2<>0 then ok:=FALSE;
grade_pare:=ok;
end;
citire_graf;
writeln;
if conex=TRUE then
if grade_pare=TRUE then writeln('graful este conex si eulerian')
else writeln('graful este cinex dar nu eulerian')
else writeln ('graful nu este conex');
end.
Aplicatie: Graf hamiltonian
Problema: Se citesc de la tastatura doua numere naturale m si n reprezentand numarul de muchii respectiv numarul de varfuri ale unui graf neorientat, apoi m perechi de numere naturale de forma (x,y), elementele fiecarei perechi reprezentand varfurile extremitati ale unei muchii. Scrieti un program care testeaza daca graful este hamiltonian,afisand un mesaj corespunzator.
Program graf_hamiltonian;
var m,n,pi,ps,prim,p:integer;
a:array[1..50,1..50] of integer;
d,c,viz:array[1..50] of integer;
procedure citire_graf;
var i,j,k,x,y:integer;
begin
write('numarul de varfuri='); readln(n);
write('numarul de muchii='); readln(m);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;
for i:=1 to n do d[i]:=0;
for k:=1 to m do
begin
writeln('dati muchia cu nr de ordine',k,'=');
repeat
readln(x,y);
until (x>=1) and (x<=n) and (y>=1) and (y<=n);
a[x,y]:=1;
a[y,x]:=1;
d[x]:=d[x]+1;
d[y]:=d[y]+1;
end;
end;
function nevizitat:integer;
var prim_nev,j:integer;
begin
prim_nev:=-1;
j:=1;
while (j<=n) and (prim_nev=-1) do
begin
if viz[j]=0 then prim_nev:=j;
j:=j+1;
end;
nevizitat:=prim_nev;
end;
parcurgere_Bf;
var k,pi,ps,z:integer;
begin
for k:=1 to n do c[k]:=0;
for k:=1 to n do viz[k]:=0;
write('varful de plecare='); readln(prim);
pi:=1;
ps:=1;
c[pi]:=prim;
viz[prim]:=1;
while ps<=pi do
begin
z:=c[ps];
for k:=1 to m do
if (a[z,k]=1) and (viz[k]=1) then
begin
pi:=pi+1;
c[pi]:=k;
viz[k]:=1;
end;
ps:=ps+1;
end;
for k:=1 to pi do write(c[k]:3);
end;
function grade:boolean;
var i:integer;
ok:boolean;
begin
ok:=TRUE;
for i:=3 to n do
if d[i]>=n/2 then ok:=FALSE;
grade:=ok;
end;
citire_graf; writeln;
if grade=TRUE then writeln('graful este hamiltonian')
else writeln('graful nu este hamiltonian');readln;
end.
BIBLIOGRAFIE
Tudor Sorin : 'Informatica'
Adrian Atanasiu:"Culegere de probleme Pascal"
George Daniel Mateescu si Pavel Florin Moraru:
" Informatica pentru liceu si bacalaureat"
|
