Rusu D. Carmen Adina (căs. Gheorghiu) [610835]
UNIVERSITATEA “TRANSILVANIA” DIN BRAȘOV
FACULTATEA DE PSIHOLOGIE ȘI ȘTIINȚELE EDUCAȚIEI
DEPARTAMENTUL PENTRU PREGĂTIREA PERSONALULUI DIDACTIC
LUCRARE METODICO -ȘTIINȚIFICĂ
PENTRU OBȚINEREA GRADULUI DIDACTIC I
Coordonator științific:
Conf. univ. dr. CIUPALĂ LAURA
Candidat: [anonimizat] „Spiru Haret”, Tecuci, Galați
2015 -2017
1 Grafuri neorientate -optimizarea procesului de predare
UNIVERSITATEA “TRANSILVANIA” DIN BRAȘOV
FACULTATEA DE PSIHOLOGIE ȘI ȘTIINȚELE EDUCAȚIEI
DEPARTAMENTUL PENTRU PREGĂTIREA PERSONALULUI DIDACTIC
TITLUL LUCRĂRII
GRAFURI NEORIENTATE –
OPTIMIZAREA PROCESULUI DE
PREDARE
Coordonator științific:
Conf. univ. dr. CIUPALĂ LAURA
Autor:
Rusu D. Carmen Adina (căs. Gheorghiu )
Colegiul Național „Spiru Haret” , Tecuci, Galați
2015-2017
2 Grafuri neorientate -optimizarea procesului de predare
Avizul conducătorului științific,
Numele și gradul didactic
Domnule Director,
Subsemnata____________________________________________
vă rog să -mi aprobați susținerea lucrării metodico – științifice cu titlul
__________________________________________________________
__________________________________________________________
sub îndr umarea d -nei conf. univ. dr.______________________________
Data, Semnătura,
3 Grafuri neorientate -optimizarea procesului de predare
Cuprins
Introducere ………………………….. ………………………….. ………………………….. ……………………… 5
Capitolul I. Aspecte teoretice generale ale grafurilor neorientate ………………………….. .. 8
1.1. Grafuri neorientate -terminologie, noțiuni de bază, forme de reprezentare …………….. 8
1.1.1. Un exemplu de graf ………………………….. ………………………….. ………………………… 8
1.1.2. Noțiunile de graf neorientat, incidență, adiacență, grad ………………………….. ……. 8
1.1.3. Reprezentarea grafurilor neorientate ………………………….. ………………………….. .. 10
1.1.3.1. Matricea de adiacență ………………………….. ………………………….. ……………… 10
1.1.3.2. Listele vecinilor ………………………….. ………………………….. ……………………… 12
1.1.3.3. Vectorul de muc hii ………………………….. ………………………….. …………………. 13
1.1.3.4. Matricea de incidență ………………………….. ………………………….. ……………… 14
1.1.3.5. Matricea costurilor ………………………….. ………………………….. …………………. 15
1.2. Noțiunile de graf parțial și subgraf. Noțiunile de lanț și ciclu ………………………….. .. 17
1.2.1. Graf parția l ………………………….. ………………………….. ………………………….. ……… 17
1.2.2. Subgraf ………………………….. ………………………….. ………………………….. …………… 20
1.2.3. Lanț ………………………….. ………………………….. ………………………….. ……………….. 24
1.2.4. Ciclu ………………………….. ………………………….. ………………………….. ………………. 28
1.3. Tipuri speciale de grafuri ………………………….. ………………………….. ……………………… 32
1.3.1. Graf complet ………………………….. ………………………….. ………………………….. ……. 32
1.3.2. Graf bipartit ………………………….. ………………………….. ………………………….. …….. 33
1.3.3. Graf Hamilton -ian ………………………….. ………………………….. ………………………… 35
1.3.4. Graf Euler -ian ………………………….. ………………………….. ………………………….. ….. 39
1.3.5. Graf ponderat ………………………….. ………………………….. ………………………….. ….. 42
1.4.Noțiunile de arbore și arbore binar ………………………….. ………………………….. ………… 43
1.4.1. Arbori ………………………….. ………………………….. ………………………….. …………….. 43
1.4.2. Arbori binari ………………………….. ………………………….. ………………………….. ……. 48
1.4.3. Implementarea arborilor binari ………………………….. ………………………….. ………. 51
Capitolul II. A lgoritmi de prelucrare a grafurilor neorientate ………………………….. ….. 53
2.1.Parcurgerea grafurilor neorientate ………………………….. ………………………….. …………. 53
2.1.1. Parcurgerea în lățime ………………………….. ………………………….. …………………….. 53
2.1.2. Parcurgerea în adâncime ………………………….. ………………………….. ……………….. 57
2.2. Conexitate în grafuri neorientate ………………………….. ………………………….. …………… 61
4 Grafuri neorientate -optimizarea procesului de predare
2.2.1. Verificarea conexității unui graf ………………………….. ………………………….. …….. 61
2.2.2. Descompunerea în componente conexe a unui graf neorientat …………………….. 63
Capitolul III. Metode și strategii didactice de învățare și evaluare ……………………….. 67
3.1. Metode didactice ………………………….. ………………………….. ………………………….. ……. 67
3.2. Funcțiile pedagogice ale metodelor diactice ………………………….. ……………………….. 67
3.3. Clasificarea metodelor de învățământ ………………………….. ………………………….. ……. 68
3.4. Metode specifice de predare a informaticii ………………………….. …………………………. 70
3.5. Predarea prin metoda conversației ………………………….. ………………………….. ………… 72
3.6. Învățarea prin descoperire ………………………….. ………………………….. …………………… 73
3.7. Instruirea asistată de calculator(IAC) ………………………….. ………………………….. ……. 75
3.8. Evaluarea ………………………….. ………………………….. ………………………….. ………………. 80
3.8.1. Conceptul de evaluare ………………………….. ………………………….. ………………….. 80
3.8.2. Forme de evaluare ………………………….. ………………………….. ……………………….. 81
3.8.3. Metode alternative de evaluare ………………………….. ………………………….. ………. 83
3.9. Testul docimologic ………………………….. ………………………….. ………………………….. …. 84
Capitolul IV.Proiectarea didactică ………………………….. ………………………….. ……………… 89
4.1. Planul unității de învățare –“conexitate în grafuri neorientate ”(conversație,
descoperire) ………………………….. ………………………….. ………………………….. …………………. 89
4.2. Planul unității de învățare –“conexitate în grafuri neorientate”(IAC) ………………….. 97
4.3. Test de evaluare – conexitate în grafuri neorientate ………………………….. …………… 105
4.4. Concluzii ………………………….. ………………………….. ………………………….. …………….. 112
Anexe ………………………….. ………………………….. ………………………….. ………………………….. . 114
Bibliografie ………………………….. ………………………….. ………………………….. ………………….. 135
5 Grafuri neorientate -optimizarea procesului de predare
INTRODUCERE
Informatica este știința procesării sistematice a informației , în special a procesării
cu ajutorul calculatoarelor. Istoric, informatica s-a dezvoltat ca știință din matematică, în
timp ce dezvoltarea primelor calculatoare își are originea în electrotehnică și
telecomunicații. De aceea, calculatorul reprezintă doar dispozitivul pe care sunt
implementate conceptele teoretice. Informaticianul olandez Edsger Dijkstra afirma: ”În
informatică ai de-a face cu calculatorul, cum ai în astronomie cu telescopul”.
Termenul de ”informatica” provine d in alăturarea cuvintelor ‘informație’ și
‘matematica’. Alte surse susțin că provine din combinația informația și automatica.
Istoria ș tiinței calculatoarelor precede momentul apari ției computerului digital.
Înainte de anul 1920, termenul de ‘computer’ se referea, în limba englez ă, la o persoan ă
care efectua calcule (un func ționar). Primii cercet ători î n ceea ce avea s ă se numeasc ă
știința calculatoarelor, cum sunt Kurt Gödel, Alonzo Church și Alan Turing, au fost
interesa ți de problema computa țional ă: ce informaț ii ar putea un func ționar uman s ă
calculeze av ând hârtie și creion, prin urm ărirea pur și simplu a unei liste de in strucț iuni,
atât timp c ât este necesar, f ără să fie nevoie ca el s ă fie inteligent sau s ă presupun ă
capacit ăți intuitive. Una din motiva țiile acestui proiect a fost dorin ța de a proiecta și realiza
‘mașini computa ționale’ care s ă automatizeze munca, deseori plictisitoare și nu lipsit ă de
erori, a unui computer uman.
În perioada anilor 1940, c ând maș inile computa ționale au cunoscut o evolu ție
accelerat ă, termenul de ‘computer’ și-a modificat semnificaț ia, referindu -se de acum mai
degrab ă la ma șini, dec ât la predecesorii s ăi umani.
Informatica se divide în urm ătoarele domenii fundamentale:
-informatica teoretic ă
-informatica practic ă
-informatica tehnic ă
Pe lângă cele trei domenii mai exist ă și ‘inteligen ța artificial ă’ considerat ă o
interdisciplin ă de sine st ătătoare.
Informatica teoretic ă se ocup ă cu studiul ‘teoriei limbajelor formale’, respectiv
automatica, ‘teoria computa țional ă și complexit ății’, ’criptologie’ , ‘logica’, ’teoria
grafurilor’ ș .a.m.d pun ând bazele pentru construirea compilatoarelor pentru limbajele de
programare și pentru formalizarea problemelor din matematic ă. Ea este, prin urmare,
coloana vertebral ă a informaticii.
6 Grafuri neorientate -optimizarea procesului de predare
În matematic ă și informatic ă, ‘teoria grafurilor’ studiaz ă propriet ățile grafurilor.
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 punc te (care
corespund muchiilor sau arcelor).
Grafurile au o importan ță imens ă în informatic ă, de exemplu:
-în unele probleme de sortare și cautare – elementele mul țimii pe care se face sortarea sau
căutarea se pot reprezenta prin noduri într-un graf;
-schema logic ă a unui program se poate reprezenta printr -un graf orientat în care o
instruc țiune sau un bloc de instruc țiuni este reprezentat printr -un nod, iar muchiile
direc ționate reprezint ă calea de execu ție;
-în programarea orientat ă pe obiecte, ierarhia obi ectelor (claselor) unui program poate fi
reprezentat ă printr -un graf în care fiecare nod reprezint ă o clas ă, iar muchiile reprezint ă
relații între acestea (deriv ări, agreg ări).
De-a lungul timpului , de studiul arborilor s -au ocupat matematicieni și fizicieni de
primă mărime: Cayley a studiat arborii și posibilitatea aplicării lor în chimia organică, iar
Kirchoff a studiat grafurile bazându -se pe considerente din fizică și anume rețelele
electrice.
Sinteze ale principalelor părți ale lucrării :
Capitolul I. ( Aspecte teoretice generale ale grafurilor neorientate ) – prezintă aspecte
teoretice generale ale grafurilor neorientate , pornind de la noțiunea de graf, terminologia
utilizată, reprezentările grafurilor . Următoarea secțiune a acestui capitol este dedicată
descrierii tipurilor special e de grafuri neorientate: complet, bipartit, Hamilton -ian, Euler –
ian și ponderat . În continuare se prezintă arborii și arborii binari , terminologie și
implementare.
Capitolul II. ( Algoritmi de prelucrare a grafurilor neorientate ) – este dedicat descrierii
metodelor de parcugere ale unui graf neorientat precum și a conexității grafurilor
neorientate, cu verificarea conexității unui graf dar și des compunerea în compone nte
conexe .
Capitolul III. ( Metode și strategii didactice de învățare și evaluare) – cuprinde noțiuni
teoretice referitoare la metodele didactice t radiționale și active utilizate în procesul de
predare -învățare -evaluare, cu accent pe metoda predării prin m etoda conversației, învățarea
prin descoperire și instruirea asistată de calculator .
7 Grafuri neorientate -optimizarea procesului de predare
Instruirea asistată de calculator permite elevi lor să-și dezvolt e aptitudini reale,
cerute în zilele noastre, cum ar fi: capacitatea de a rezolva probleme complexe, capacitatea
de auto – direcționare și de autoevaluare, stimularea creativității și a imaginației.
Capitolul IV. (Proiectarea didactică) – Unitatea de învăț are „ Conexitate în grafuri
neorientate ” este organizată sub forma unui portofoliu care cuprinde :
– planul unității de învățare (metoda conversației și învățarea prin descoperire ) cu
obiectivele operaționale aliniate competențelor specifice și competențelo r generale
vizate, cu setul de întrebări cheie, precum și cu activitățile desfășurate, metodele de
predare și evaluare, mijloacele de învățare folosite, etc;
– planul unității de învățare ( instruirea asistată de calculator; )
– testul de evalu are finală ;
– prezentări realizate de profesor, alte materiale documentare care sprijină predarea
unității de învățare;
– materiale realizate de elevi .
Procesul instructiv -educativ valorifică și dezvoltă continuu capacitățile de cunoaștere
ale elevilor, spiritul de observ ație și de investigare, gândirea creativă, transformând nevoia
de instruire și de autoinstruire într -o trebuință intrinsecă fiecărei personalități în formare.
8 Grafuri neorientate -optimizarea procesului de predare
5 1 2
3
4 6 CAPITOLUL I
ASPECTE TEORETICE GE NERALE ALE GRAFURILO R
NEORIENTATE
1.1. GRAFURI NEORIENTATE: TERMINO LOGIE, NOȚIUNI DE BA ZĂ, FORME
DE REPREZENTARE
1.1.1. Un exemplu de graf
[27]În multe din problemele în a căror rezolvare se folosește calculatorul este
necesară reprezentarea unor relații generale între obiecte. Un model în astfel de cazuri este
graful orientat, dacă relația este nesimetrică, sau neorientat dacă relația este simetrică.
Situația unui turist aflat într -un oraș străin este elocventă. Deplasarea acestuia dintr –
un punct X într -un punct Y se va face pe baza unui desen(hărți ), în care intersecțiile vor fi
reprezentate prin puncte, iar străzile ce ”leagă” intersecțiile vor fi reprezentate prin linii
drepte sau curbe.
Desenul(harta) reprezintă un model clasic de graf neorientat .
Astfel, cu desenul în față, turistul își va putea alege singur traseul pe care urmează
să-l parcurgă.
1.1.2. Noțiunea de graf neorientat , adiacență, incidență, grad
[27]Definiție :
Se numește graf neorientat, o pereche ordonată de mulțimi G(X,U) , unde :
– X este o mulțime finită și nevidă de elemente , intitulată mulțimea nodurilor ;
– U este o mulțime de perechi neordonate, U={(x 1,x2)…(x i,xi+1)},
intitulată mulțimea muchiilor.
Așadar un graf neorientat poate fi reprezentat, ca în
figura 1, sub forma unei figuri geometrice alcătuită din puncte și
linii drepte sau curbe care unesc aceste puncte. În cazul grafurilor
neorientate vom vorbi de nod și muchie .
În figura 1, cercul albastru notat cu “1” este un nod al
acelui graf. De asemeni linia roșie cu extremitățile în vârfurile “2”
și “3” este o muchie . Figura 1
9 Grafuri neorientate -optimizarea procesului de predare
Pentru graful G(X,U) din figura 1, vom avea mulțimile:
X={1,2,3,4,5,6} ca fiind mulțimea nodurilor din graf;
U={(1,2),(1,4), (1,5),(1,3),(2,5),(4,5)} ca fiind mulțimea muchiilor.
În cazul nodurilor, la general vorbind, două noduri sunt extremitățile unei muchii.
Ca exemplu putem lua nodurile 2 și 3 din figura 1, ele fiind extremitățile muchiei (2,3)
desenată în figură cu roșu.
Două noduri x și y aparținând mulțimii X, sunt adiacente dacă există muchia (x,y)
aparținând lui U.
Două muchii putem spune că sunt incidente dacă au o extremitate comună, adică
un nod comun. Pentru a exemplifica acest lucru putem alege muchiile (1,2) și (1,4) ale
grafului din figura 1, observând că ele au o extremitate comună și anume nodul 1.
Putem spune de asemenea că o muchie și un vârf sunt incidente, în cazul în care
vârful ales este extremitate a muchiei alese. Din graful din figura 1 putem alege oricare
nod și muchie, spunând ca acestea sunt incidente numai în cazul în care vârful este
extremitatea muchiei respective. Exemplu, ar fi vârful 1, extremitate a muchiei (1,5).
Într-un graf , fiecare nod are gradul său.
[27]Definiție :
Gradul unui nod x, notat d(x), reprezintă numărul muchiilor care trec prin nodul
x (incidente cu nodul x).
Un vârf care are gradul 0 se numește vârf izolat, iar un vârf care are gradul 1, se
numește vârf terminal.
Spre exemplu luăm nodul 5 al grafului din figura 1, și îi c alculăm gradul. Gradul
nodului 5 este egal cu 3, deoarece vârful 5 este incident cu 3 muchii: (1,5), (2,5) și (4,5).
Spre exemplu mai putem calcula gradul nodului 6 din figura 1. Vom observa că
gradul acestui nod este 0. În acest caz vom preciza că nodul respectiv este un nod izolat.
[27]Teoremă :
Într-un graf G(X,U) cu n vârfuri și m muchii, suma gradelor tuturor nodurilor este
egală cu 2*numărul muchiilor.
∑𝒅(𝒙𝒊)𝒏
𝒊=𝟏=𝒅(𝒙𝟏)+𝒅(𝒙𝟐)+⋯+𝒅(𝒙𝒏)=𝟐∗𝒎
Demonstrația este evidentă. Fiecare muchie de forma (x i,xj) (unde x i și x j sunt noduri,
cu i, j ∈{1,2,…,n}), contribuie cu o unitate la gradul nodului i și cu o unitate la gradul
nodului j. Așadar fiecare muchie adaugă două unități la suma gradelor.
10 Grafuri neorientate -optimizarea procesului de predare
1 2
3
4
Figura 2 Având în total m muchii, rezultă că suma gradelor este 2*m.
1.1.3. Reprezentare a grafurilor neorientate
[4]Considerăm un graf neorientat G=(X,U) cu m muchii și n vârfuri numerotate
1,2,3,…..,n . Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt:
matricea de adiacență
listele vecinilor
vectorul muchiilor
matricea de incidență
matricea costurilor
Pentru implementările acestor metode de reprezentare vom considera definițiile globale de
constante și tipuri următoare:
#define N 50 //numărul de vârfuri
#define M 100 //numărul de muchii
#define INF 32000
typedef unsigned char tip;
1.1.3.1. Matricea de adiacență .
[4]Este o matrice pătrată de forma n*n, cu n numărul de noduri ale grafului,
alcătuită din elementele 0 și 1. Această matrice este simetrică față de diagonala sa
principală. Se va completa a[i,j](matricea) cu elementul 1 dacă există muchie de la nodul i
la nodul j și cu 0 dacă nu există muchie de la nodul i la nodul j.
a[i][j]= 1, dacă există muchia [i,j] cu i j
0, în caz contrar
Pentru a exemplifica matricea de adiacență ne vom folosi de figura 2:
0 1 1 1
1 0 0 1
A4*4=
1 0 0 1
1 1 1 0
Observații
Suma elementelor de pe linia x sau de pe coloana x din matricea de adiacență
reprezintă gradul nodului x.
11 Grafuri neorientate -optimizarea procesului de predare
Muchiile distincte din graf se regăsesc în jumătatea superioară a matricei de
adiacență.
Suma tuturor valorilor din matricea de adiacență este număr par egal cu de două ori
numărul muchiilor din graf.
Pentru memorarea în programe a matricei de adiacență se folosesc matrici pătratice
binare. Uzual, dintr -un fișier text se citesc numărul vârfurilor și, eventual, cel al muchiilor,
apoi perechi de valori diferite de vârfuri din graf reprezentând extremită țile unei muchii.
Din fiecare pereche citită, două valori din matricea de adiacență (valori simetrice) primesc
valoarea 1.
Funcția următoare citește dintr -un fișier text informațiile referitoare la un graf în
forma descrisă mai sus și construiește matric ea de adiacență.
void citire(tip a[N][N],int &n,int &m)
int k,x,y;
ifstream f(“in.txt”); f>>n>>m;
//numarul de varfuri si numarul de muchii
for(k=1;k<=m;k++)
f>>x>>y; //extremitățile unei muchii
a[x][y]=a[y][x]=1;
f.close();
Dacă nu se precizează numărul muchiilor din graf, funcția de citire se modifică în felul
următor:
void citire(tip a[N][N],int &n)
int x,y;
ifstream f(“in.txt”); f>>n;
//numarul de varfuri
while(!f.eof())
f>>x>>y; //extremitatile unei muchii
a[x][y]=a[y][x]=1;
12 Grafuri neorientate -optimizarea procesului de predare
f.close();
Dacă în fișier este memorată integral matricea de adiacență, citirea se face element cu
element ca în funcția următoare:
void citire(tip a[N][N],int &n)
int x,y;
ifstream f(“in.txt”); f>>n;
//numarul de varfuri
for(x=1;x<=n;x++)
for(y=1;y<=n;y++)f>>a[x][y]);
f.close();
Funcția de determinare a gradului unui nod x transmis ca parametru este următoarea:
int grad(int x)
{
int i,s;
s=0;
for(i=1;i<=n;i++)
s=s+a[x][i];
return s;
}
1.1.3.2. Listele vecinilor .
[4]Pentru fiecare nod i(cu i=1,2,…,n), formăm lista vecinilor lui i. Aceasta cuprinde
toate nodurile care sunt extremități ale muchiilor incidente cu nodul i.
Exemplu, pentru graful din figura 2 vom alcătui listele vecinilor:
Observăm că fiecare linie i din listele vecinilor conține indicii coloanelor pe care se găsesc
valori de 1 în linia i a matricei de adiacență. Acestă metodă de reprezentare se nodul lista vecinilor
1 2, 3, 4
2 1, 4
3 1, 4
4 1, 2, 3
13 Grafuri neorientate -optimizarea procesului de predare
implementează elegant utilizând alocarea dinamică a memoriei prin intermediul listelor
înlănțuite.
1.1.3.3. Vectorul de muchii .
[4]Fiecare muchie a grafului poate fi privită ca o înregistrare cu două componente:
cele două vârfuri care constituie extremitățile muchiei. Notând aceste ext remități cu x și y,
putem defini tipul de date TMUCHIE astfel:
typedef struct {
int x,y;
} TMUCHIE;
Graful în ansamblul său, este o mulțime de muchii, adică o mulțime de elemente de tipul
TMUCHIE . În consecință, definim graful ca un “ vector de much ii”, adică un vector cu
elemente de tipul TMUCHIE :
TMUCHIE v[M];
Numărul real de elemente este numărul de muchii m. Astfel, elementele efectiv folosite ale
vectorului vor fi v[1],v[2],….,v[m] . Fiecare element v[i] este de tipul TMUCHIE și
reprezintă o muchie a grafului, având două componente: v[i].x și v[i].y care sunt vârfurile
extremități ale muchiei.
Observații : în structura TMUCHIE se pot memora și alte informații referitoare la
muchiile grafului (de exemplu, costul muchiei).
Funcția următoare realizează construirea vectorului muchiilor prin citirea acestora
dintr -un fișier text.
void citire(TMUCHIE v[M],int &n,int &m)
int k;
ifstream f(“in.txt”); f>>n>>m;
for(k=1;k =m;k++)
f>>v[k].x>>v[k].y;
f.close();
14 Grafuri neorientate -optimizarea procesului de predare
1.1.3.4. Matricea de incidență .
[4]Pentru graful G=(X,U) cu n vârfuri și m muchii, matricea de incidență a are n
linii și m coloane și se definește astfel:
1, dacă vârful x i este incident cu muchia m j
0, în caz contrar
Exemplu: Fie graful G=(X,U) din figura 2, cu X={1,2,3,4} și
U={[1,2],[1,3],[1,4],[2,4],[3, 4]}
Pentru acest graf, asociind fiecăruia dintre vârfuri câte o linie a matricei și fiecărei muchii
câte o coloană, se obține matricea de incidență:
u1 u2 u3 u4 u5
x1 1 1 1 0 0
x2 1 0 0 1 0
x3 0 1 0 0 1
x4 0 0 1 1 1
Observații:
Fiecare coloană din matricea de incidență conține exact două valori nenule.
Suma elementelor de pe linia x din matricea de incidență reprezintă gradul nodului
x.
Suma tuturor elementelor din matricea de adiacență este un număr par (de două ori
numărul muchiilor).
Pentru memorarea în programe a matricei de incid ență se folosesc matrici binare
Anxm. Matricea de incidență se poate construi prin citirea muchiilor dintr -un fișier text.
Muchiile se vor numerota în ordinea citirii din fișier și fiecare muchie este incidentă cu
extremitățile ei.
Funcția următoare ilustrează modul de construire a matricii de incidenț ă prin citirea
informațiilor dintr -un fișier text.
void citire(tip a[N][M],int &n,int &m)
int k,x,y;
int k,x,y;
ifstream f(“in.txt”); f>>n>>m;
//numarul de varfuri si numarul de muchii
for(k=1;k<=m;k++) a[i][ij]=
15 Grafuri neorientate -optimizarea procesului de predare
f>>x>>y; //extremitatile unei muchii
a[x][k]=a[y][k]=1;
//muchia k este incidenta cu extremitatile x si y
f.close();
1.1.3.5. Matricea costurilor
[4]Această metodă se folosește pentru reprezentarea grafurilor ponderate , adică
grafuri care au atașate muchiilor valori strict pozitive numite ponderi sau costuri . Spre
exemplu, dacă graful modelează rețeaua de căi ferate dintr -o regiune, costul pot reprezenta
distanța dintre două localități legate prin cale ferată.
Datorită specificului unor probleme practice, acest mod de memorare a grafului
poate căpăta două aspecte, după cum trebuie determinat minimul sau maximul unei
anumite mărimi asociate muchiilor (cost, durată, timp, distanță etc.).
A) Matricea costurilor, forma 1 : este folosită în cazul în care se dorește determinarea
unui drum de lungime minimă între două vârfuri oarecare și se definește astfel:
c, dacă există o muchie de cost c>0 între nodurile i și j, i j
a[i][j]= 0, dacă i=j
, dacă nu există muchie între vârfurile i și j, i j
Este evidentă necesitatea atașării unei valori cât mai mari unei muchii ce de fapt nu
există, deoarece, căutându -se un drum de lungime minimă, în acest mod se evită selectarea ,
la un moment dat, a respectivei muchii. În practică, în scrierea unui program se alege cea
mai mare valoare ce se poate reprezenta în calculator.
B) Matricea costurilor, forma 2 : este folosită în cazul când se dorește determinarea unui
drum de lungime ma ximă între două noduri și se definește astfel:
c, dacă există o muchie de cost c>0 între nodurile i și j, i j
a[i][j]= 0, dacă i=j
-, dacă nu există muchie între vârfurile i și j, i j
16 Grafuri neorientate -optimizarea procesului de predare
De data ac easta, din considerente similare, se alege cea mai mică valoare ce se
poate reprezenta în calculator.
Pentru graful următor, matricea costurilor în forma 1 are configurația:
Figura 3
Următoarea funcție construiește matricea costurilor în forma 1 prin citirea datelor dintr -un
fișier text. Pentru fiecare muchie din graf se specifică pe o linie din fișier extremitățile și
costul.
void citire(tip a[N][N],int &n,int &m)
int k,x,y;
ifstream f(“in.txt”); f>>n;
for(x=1;x =n;x++) //initializam matricea costrurilor cu ∞
for(y=1;y =n;y++) a[x][y]=INF;
a[x][x]=0; //pe diagonala principala
while(!feof(f))
f>>x>>y>>k; //extremitatile unei muchii
//extremitatile unei muchii si costul
a[x][y]=a[y][x]=k;
f.close();
x1 x2 x3 x4 x5
x1 0 12 ∞ 7 ∞
x2 12 0 5 ∞ 8
x3 ∞ 5 0 9 15
x4 7 ∞ 9 0 ∞
x5 ∞ 8 15 ∞ 0
17 Grafuri neorientate -optimizarea procesului de predare
1.2. NOȚIUNILE DE GRAF PA RȚIAL ȘI SUBGRAF
NOȚIUNILE DE LANȚ ȘI CICLU
1.2.1. Graf parțial
[27]Definiție :
Fie graful G=(X,U). G1=(X,V), cu V⊆𝑼, este un graf parțial al lui G dacă și numai
dacă se obține prin eventuala eliminare a unor muchii din G. Astfel, în cazul în care nu
se va elimina nici o muchie, un graf parțial al lui G poate fi chiar G.
Un ex emplu de graf parțial este cel construit în figura 4.b, obținut din graful
reprezentat în figura 4.a.
m1 m3 m1
m2 m4 m4
m5 m5
m6
Fig. 4.a G=(X,U) Fig. 4.b G1=(X,V)
Astfel, grafului G=(X,U) cu X={1,2,3,4,5,6} și U={m1,m2,m3,m4,m5,m6} îi
corespunde graful parțial G1=(X,V), cu V={m1,m4,m5} obținut prin eliminarea muchiilor
m2, m3 și m6.
Se poate afla dacă G1 este un graf parțial al lui G folosind matricile de adiacență ale
celor două grafuri. Având aceleași dimensiuni, cele două matrici a și b (aparținând lui G,
respectiv lui G1) vor fi parcurse simultan pent ru a verifica dacă există o muchie în G1 care
să nu existe în G. În acest caz, U1 nu este inclus în U pentru că are un element în plus, deci
G1 nu este graf parțial al lui G. În schimb, dacă nu se găsește o asemenea muchie,
concluzia este că G1 este graf p arțial al lui G. Dacă cele două matrici de adiacență sunt
identice atunci G1 este chiar G.
Pentru exemplul reprezentat în figurile 4.a și 4.b am construit matricile de adiacență
din figurile 4.c și 4.d .
1
1
1
1
1
1
1
1
1
1
1
1
1 2
3
4
5 6 4 3 2
1
1
1
1
1
1
1
1
1
1
1
1
1 6
5
18 Grafuri neorientate -optimizarea procesului de predare
0 1 0 0 0 1 0 1 0 0 0 0
1 0 1 1 0 0 1 0 0 1 0 0
0 1 0 0 0 1 0 0 0 0 0 1
0 1 0 0 1 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 1 0 0 0
Figura 4.c Figura 4.d
Matricea de adiacență Matricea de adiacență
a grafului G=(X,U) a grafului G1=(X,V)
Se observă astfel că nu există o muchie în matricea de adiacență b care să nu existe
în matricea de adiacență a. De asemenea, asistăm la apariția de noduri izolate în G1 (nodul
5) datorită suprimării unor muchii (muchia m6) din G.
Programul C++ de generare a tuturor grafurilor parțiale ale unui graf G(X,U) dat prin
vectorul de muchii este următorul:
– Programul utilizează tehnica Backtracking în varianta recursivă;
– Se generează toate grafurile parțiale distincte după modelul combinărilor;
– Soluțiile sunt preze ntate sub forma matricilor de adiacență asociate grafurilor
parțiale rezultate.
#include<iostream.h>
#include<conio.h>
int st[10],a[10][10],m,n,k,p;
struct muchie
{
int x,y;
}v[10];
void citiri()
{
int i;
cout<<"Nr. de noduri: ";
cin>>n;
cout<<"Nr. de muchii: ";
cin>>m;
cout<<"Introduceti extremitatile muchiilor"<<endl;
for(i=1;i<=m;i++)
{
cout<<"v["<<i<<"]= ";
19 Grafuri neorientate -optimizarea procesului de predare
cin>>v[i].x>>v[i].y;
}
}
void init()
{
int i;
for(i=1;i<=p;i++)
st[i]=0;
}
int valid(int k)
{
if(k>1&&st[k]<=st[k -1])
return 0;
return 1;
}
void tipar()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=p;i++)
{
a[v[st[i]].x][v[st[i]].y]=1;
a[v[st[i]].y][v[st[i]].x]=1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<< a[i][j]<<' ';
cout<<endl;
}
cout<<"#############"<<endl;
}
void bktr(int k)
{
20 Grafuri neorientate -optimizarea procesului de predare
int i;
for(i=1;i<=m;i++)
{
st[k]=i;
if(valid(k))
if(k==p)
tipar();
else
bktr(k+1);
}
}
void main()
{
int i,j;
clrscr();
citiri();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<a[i][j]<<' ';
cout<<endl;
}
cout<<"#############"<<endl;
for(p=1;p<=m;p++)
{
init();
bktr(1);
}
getch();
}
1.2.2. Subgraf
[15]Definiție :
Fie graful G=(X,U). G1=(Y, T), cu 𝑻⊆𝑼 și 𝒀⊆𝑿, este un subgraf al lui G dacă și
numai dacă se obține prin eventuala eliminare a unor noduri din G, precum și a
21 Grafuri neorientate -optimizarea procesului de predare
muchiilor incidente cu acestea. Astfel, în cazul în care nu se va elimina nici un nod, un
subgraf al lui G poate fi chiar G.
Fie graful neorientat G=(X,U). Graful G1=(Y,T) va fi subgraf al lui G dacă Y este
inclus în X și dacă T este inclus în U.
Pentru graful din figura 5.a , am construit subgraful obținut prin eliminarea nodurilor 1
și 4, reprezentat în figura 5.b.
m3
m1 m3
m4
m2 m5
m5
m6
Figura 5.a Figura 5.b
Graful G=(X,U) Graful G1=(Y,T)
Astfel mulțimea X={1,2,3,4,5,6} devine Y={2,3,5,6} iar U={m1,m2,m3,m4,m5,m6}
se reduce la mulțimea T={m3,m5} datorită suprimării muchiilor m1,m2,m4 și m6
incidente în nodurile 1 și 4.
Programul C++ de generare a tuturor subgrafurilor unui graf G(X,U) dat prin vectorul
de muchii este următorul:
– Programul utilizează tehnica Backtracking în varianta recursivă;
– Se generează toate subgrafurile distincte după modelul combinărilor;
– Soluțiile sunt prezentate sub forma mulțimii nodurilor și mulțimii muchiilor
asociate subgrafurilor rezultate.
#include<iostream.h>
#include<conio.h>
int st[10],a[10][10],m,n,k,p;
struct muchie
{
int x,y;
}v[10];
void citiri() 2
1
6
5 3
4 3 2
5 6
22 Grafuri neorientate -optimizarea procesului de predare
{
int i;
cout<<"Nr. de noduri: ";
cin>>n;
cout<<"Nr. de muchii: ";
cin>>m;
cout<<"Introduceti extremitatile muchiilor"<<endl;
for(i=1;i<=m;i++)
{
cout<<"v["<<i<<"]= ";
cin>>v[i].x>>v[i].y;
}
}
int exista(int q,int z)
{
int i;
for(i=1;i<=m;i++)
if(v[i].x==q&&v[i].y==z||v[i].x==z&&v[i].y==q)
return 1;
return 0;
}
void init()
{
int i;
for(i=1;i<=p;i++)
st[i]=0;
}
int valid(int k)
{
if(k>1&&st[k]<=st[k -1])
return 0;
return 1;
}
void tipar()
{
int i,j;
23 Grafuri neorientate -optimizarea procesului de predare
cout<< "Noduri: ";
for(i=1;i<=p;i++)
cout<<st[i]<<' ';
cout<<endl;
cout<<"Muchii: ";
for(i=1;i<=p -1;i++)
for(j=i+1;j<=p;j++)
if(exista(st[i],st[j]))
cout<<'('<<st[i]<<','<<st[j]<<"),";
cout<<endl;
cout<<"#############"<<endl;
}
void bktr(int k)
{
int i;
for(i=1;i<=n;i++)
{
st[k]=i;
if(valid(k))
if(k==p)
tipar();
else
bktr(k+1);
}
}
void main()
{
int i,j;
clrscr();
citiri();
for(p=1;p<=n;p++)
{
init();
bktr(1);
}
getch();
}
24 Grafuri neorientate -optimizarea procesului de predare
1.2.3. Lanț
[12]Definiție :
Într-un graf oarecare G=(X,U), noțiunea de lanț se definește ca fiind o succesiune
de noduri L={x 1, x2, x3, …, x k} , unde x 1, x2, x3, …, x k aparțin mulțimii X cu proprietatea că
oricare două noduri consecutive sunt legate printr -o muchie aparținând mulțimii U.
Astfel, x 1 și x k sunt extremit ățile lanțului, numărul de muchii dintre acestea ce leagă
componentele lanțului între ele repre zentând lungimea lanțului.
Un lanț poate fi interpretat ca un traseu care pleacă din nodul x 1 (orașul A) și ajunge în
nodul x k (orașul Z) , trecând prin mai multe noduri ( eventual ) și parcurgând mai multe
muchii ( drumuri între diferite orașe ).
Lanțurile pot fi : – elementare;
– neelementare.
Lanțurile elementare sunt cele care au proprietatea că oricare două noduri comparate
împreun ă din componența sa sunt distincte.
Lanțuril e neelementare au proprietatea că cel puțin un nod se regăsește de cel puțin
două ori în mulțimea de noduri a lanțului.
Observând graful G=(X,U), cu X={1,2,3,4,5,6} , reprezentat în figura 6, putem distinge
cu ușurință câteva lanțuri, cum ar fi L1= (1,2,3,5,6,4), L2=(3,5,2,4,6), L3=(3,2,4,6,5,2). L1 și
L2 ( cel colorat cu albastru ) sunt lanțuri elementare, pentru că nici un nod nu se repetă în
succesiune iar L3 este lanț neelementar pentru că nodul 2 se repetă o dată.
Pentru a verifica dacă o secvență oarecare de noduri x1, x2, …, xk este un lanț folosind
matricea de adiacență trebuie să parcurgem succesiunea de noduri, condiția de bază fiind ca
oricare două noduri consecutive să fie adiacente (elementele din matricea de adiacență
corespunzătoare să fie egale cu 1). 1 2 3
5 4
6 Figura 6
25 Grafuri neorientate -optimizarea procesului de predare
Programul C++ de g enerare a tuturor lanțurilor elementare dintr -un graf G(X,U) dat
prin matricea de adiacență este următorul:
– Programul utilizează tehnica Backtracking în varianta recursivă;
– Se generează toate lanțurile elementare distincte după modelul combinărilor;
– Soluțiile sunt prezentate sub forma unor șiruri de noduri.
#include<iostream.h>
#include<conio.h>
int st[10], n,m, k,p, a[10][10],v[10][10],t,r;
int caut()
{
int t,z,sw,sw1,t1,nr;
if(r==0)
{
r++;
for(t=1;t<=p+1;t++)
v[r][t]=st[t];
return 0;
}
else
{
sw=0;
for(z=1;z<=r;z++)
{
nr=0;
for(t=1;t<=p+1;t++)
{
sw1=0;
for(t1=1;t1<=p+1;t1++)
if(v[z][t1]==st[t])
sw1=1;
if(sw1==1)
nr++;
}
if(nr==p+1)
sw=1;
}
if(sw==0)
26 Grafuri neorientate -optimizarea procesului de predare
{
r++;
for(t=1;t<=p+1;t++)
v[r][t]=st[t];
return 0;
}
}
return 1;
}
void init()
{ int i;
for(i=1; i<=p+1; i++)
st[i]=0;
}
int valid(int k)
{
int i;
if(k>1)
for(i=1; i<=k -1; i++)
if(st[k]==st[i])
return 0;
if((k>1)&& (a[st[k]][st[k -1]]==0))
return 0;
return 1;
}
void tipar()
{
int i;
if(caut()==0)
{
for(i=1;i<=p+1;i++)
cout<<st[i]<<' ';
cout<<endl;
}
}
void bktr(int k)
27 Grafuri neorientate -optimizarea procesului de predare
{
int i;
for(i=1; i<=n; i++)
{
st[k]=i;
if(valid(k))
if(k==p+1)
tipar();
else
bktr(k+1);
}
}
void introducere()
{
int i,j;
cout<<"n=";
cin>>n;
m=0;
for(i=1; i<=n; i++)
a[i][i]=0;
for(i=1; i<=n -1; i++)
for(j=i+1; j<=n; j++)
{
cout<<i<<" "<<j<<"1/0 exista/nu exista muchia i -j ";
cin>>a[i][j];
a[j][i]=a[i][j];
m++;
}
}
void init1()
{
int i,j;
r=0;
for(i=1;i<=10;i++)
for(j=1;j<=10;j++)
v[i][j]=0;
}
28 Grafuri neorientate -optimizarea procesului de predare
void meniu()
{char c,w;
do
{
clrscr();
cout<<"0 -Introducere date"<<endl;
cout<<"1 -Afisarea solutii"<<endl;
cout<<"2 -Parasire program"<<endl;
cout<<"Introduceti optiunea: ";
cin>>c;
if(c=='0')
{
introducere();
}
if(c=='1')
{
for(p=1;p<=m;p++)
{
init1();
init();
bktr(1);
}
cout<<endl;
cout<<"apasati o litera";
cin>>w;
}
}while(c!='2');
}
void main()
{
meniu();
}
1.2.4. Ciclu
[12]Definiție :
Într-un graf oarecare G=(X,U), noțiunea de ciclu se definește ca fiind o succesiune de
noduri C={x 1, x2, x3, …, x k} , unde x 1, x2, x3, …, x k aparțin mulțimii X cu proprietatea că:
29 Grafuri neorientate -optimizarea procesului de predare
– oricare două noduri consecutive sunt legate printr -o muchie aparținând mulțimii U;
– primul nod este este egal cu ultimul(x 1=xk);
– muchiile ( x1,x2), (x2,x3), …, ( xk-1,xk) sunt distincte două câte două.
Astfel, x 1 și x k sunt extremitățile ciclului , numărul de muchii dintre acestea ce leagă
componentele ciclului între ele reprezentând lungimea ciclului .
Ciclurile se clasifică în: – elementare;
– neelementare.
Ciclurile elementare sunt cele care, în afară de primul și ultimul, au toate nodurile
distincte.
Ciclurile neelementare , spre deosebire de cele elementare, au proprietatea că cel
puțin un nod se repetă în cadrul succesiunii, făcând abstracție de ultimul nod.
Figura 7
Graful G=(X,U)
În graful G=(X,U) (reprezentat în fig. 7) cu X={1,2,3,4,5,6,7,8} putem deosebi
mai multe cicluri; de exemplu C1=(4,8,7,1,2,5,8,3,4), C2=(6,7,5,8,2,1,6)
C3=(7,5,8,4,3,2,7) și C4=(1,2,3,4,5,6,7,1). Dintre acestea, C2, C3, C4 sunt elementare
(deoarece se observă faptul că traseul pe care îl descriu fiecare dintre cicluri a u primul nod
egal cu ultimul iar nici un nod nu se repetă). C1 (colorat în albastru ) este ciclu neelementar
pentru că succesiunea de noduri începe și se termină în același nod și există un nod care se
repetă (nodul 8).
Programul C++ de generare a tuturor ciclurilor elementare dintr -un graf G(X,U) dat
prin matricea de adiacență este următorul:
– Programul utilizează tehnica Backtracking în varianta recursivă;
– Se generează toate ciclurile elementare distincte ;
– Soluțiile sunt prezentate sub forma unor șiruri de noduri. 2 3
4 7 8
5 6 1
30 Grafuri neorientate -optimizarea procesului de predare
#include <iostream.h>
#include<conio.h>
int a[10][10],st[10],n,k,t;
void init()
{ int i;
for(i=1;i<=t+1;i++)
st[i]=0;
}
int valid(int k)
{int i;
if((k>1)&&(a[st[k -1]][st[k]]==0))
return 0;
if((k>1)&&(k<t+1))
{
for(i=1;i< =k-1;i++)
if(st[k]==st[i])
return 0;
if(st[k]<st[k -1])
return 0;
}
if((k==t+1)&&(st[k]!=st[1]))
return 0;
return 1;
}
void tipar()
{int i;
for(i=1;i<=t+1;i++)
cout<<st[i]<<" ";
cout<<endl;
}
void bktr(int k)
{int i;
for(i=1;i< =n;i++)
{
31 Grafuri neorientate -optimizarea procesului de predare
st[k]=i;
if(valid(k))
if(k==t+1)
tipar();
else
bktr(k+1);
}
}
void citiri()
{int i,j;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
a[i][i]=0;
for(i=2;i<=n;i++)
for(j=1;j<=i -1;j++)
{
cout<<"a["<<i<< "]["<<j<<"]=";
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
void meniu()
{
cout<<"1 -Introducere date"<<endl;
cout<<"2 -Generari cicluri"<<endl;
cout<<"3 -Parasire program"<<endl;
}
void main()
{int q;
do
{meniu();
cin>>q;
if(q==1)
{
32 Grafuri neorientate -optimizarea procesului de predare
citiri();
getch();
clrscr();
}
if(q==2)
{
for(t=3;t<=n;t++)
{
init();
bktr(1);
}
getch();
clrscr();
}
}while(q!=3);
cout<<"SFARSIT!";
}
1.3. TIPURI SPECIALE DE G RAFURI
1.3.1. Graf complet
[9]Definiție :
Un graf G=(X,U) este complet, dacă și numai dacă oricare două noduri ale sale sunt
adiacente ( legate printr -o muchie).
Astfel gradul fiecărui nod va fi maxim (nr. noduri – 1).
Un graf complet se va nota cu K n, indicele n reprezentând numărul de noduri al
grafului. Ca exemplu am luat în considerare un graf complet cu 5 noduri reprezentat în
figura 8.
Figur a 8 4 1
5 2
3
33 Grafuri neorientate -optimizarea procesului de predare
[9]Teoremă :
Un graf G(X,U) complet, cu n noduri, are 𝒏∗(𝒏−𝟏)
𝟐 muchii.
Aceasta se poate demonstra cu ajutorul unui procedeu d e numărare suficient de
simplu. Astfe l, după cum observăm în figura 8 , primul nod este incident cu patru muchii
(colorate cu roșu), adică un număr de n -1 muchii, n reprezentând numărul nodurilor din
graf (5). Trecând la nodul al doilea se remarcă faptul că acesta are deja o muchie incidentă
care a fost numărată (incidentă cu primul nod, adică cu precedentul). Așadar vom număra
doar n-2 muchii (colorate cu albastru , în număr de trei) care vor fi incidente cu restul
nodurilor, exceptându -l pe 1. Raționamentul se continuă până când ajungem la ultimul nod.
Observăm că toate muchiile incidente cu acesta au fost deja numărate (colorate); d eci vom
număra n -n muchii, adică 0.
În fine, suma muchiilor numărate este S=(n -1)+(n -2)+(n -3)+(n -4)+(n -5), unde n=5.
O astfel de sumă este o progresie aritmetică cu rația 1 și cu primul termen nul.
Neluând în considerare primul termen al progresiei (nodul 5) suma va fi :
S=nr. noduri × (primul termen + ultimul termen) = (n-1)(n-4 + n -1) = 4×5 = 10
2 2 2
Generalizând, excluzân d primul termen al sumei de fiecare dată, aceasta va deveni:
Observație :
Numărul total de grafuri neorientate distincte cu n noduri este 𝟐𝒏∗(𝒏−𝟏)
𝟐 .
Demonstrația este sim plă, prin efectuarea calculelor. Notăm cu m=2𝑛∗(𝑛−1)
2 numărul de
muchii în graful complet cu n noduri.
nr=C m0+Cm1+…+C mm=2m= 2𝑛∗(𝑛−1)
2
1.3.2. Graf bipartit
[27]Definiție :
Graful G=(X,U) este bipartit dacă există două mulțimi A și B incluse în X astfel
încât:
A ∩ B = Ø și
A U B = X și
toate muchiile grafului au o extremitate în A și cealaltă în B. 𝑆=(𝑛−1)(𝑛−𝑛+1+𝑛−1)
2 = (𝑛−1)𝑛
2
34 Grafuri neorientate -optimizarea procesului de predare
Chiar după denumirea lor, ne putem imagina ce sunt grafurile bipartite. Acestea
sunt alcătuite din două „partiții”, mai exact mulțimi de noduri, care „comunică” între ele
prin toate muchiile grafului.
Așadar o caracteristică de bază a grafurilor bipartite este aceea că nodurile
aparținând aceleiași mulțimi nu sunt adiacente. Spre exemplificare, în figura 9 s -a construit
graful G=(X,U) cu X={1,2,3,4,5,6,7} și U={m1,m2,m3,m4}. Observăm conturarea
mulțimilor A={1,2,3,4} și B={5,6,7} care nu au noduri comune dar care reunite alcătuiesc
mulțimea X. De asemenea toate muchiile au câte un capăt în fiecare dintre cele două
mulțimi.
m1 m2 m3 m4
Figura 9
Graful bipartit G=(X,U)
[27]Definiție :
Se numește graf bipartit complet un graf bipartit care are proprietatea că între
orice nod α din A și orice nod β din B, există o muchie (α, β). Am notat cu A și B cele
două submulțimi care partiționează mulțimea nodurilor X.
Un exemplu de graf bipartit complet este cel din figura 10 cu X={1,2,3,4,5,6},
A={1,2,3} și B={4,5,6}. Se observă că orice nod din mulțimea A este adiacent cu orice
nod din mulțimea B (cara cteristică a grafului complet) dar că nu are legătură cu nici unul
dintre celelalte noduri ale mulțimii A (caracteristică a grafului bipartit). Acest lucru este
valabil și pentru orice nod din mulțimea B.
Figura 10
Graf bipartit complet 2 1 5 6 7 1 2 3 4
3
6 5 4
35 Grafuri neorientate -optimizarea procesului de predare
6 5 3 2
4 7 1 1.3.3. Graf Hamiltonian
[27]O problemă adesea întâlnită în studierea grafurilor neorientate se referă la
grafurile hamiltoniene . Înainte de a afla ce sunt grafurile hamiltoniene, trebuie să știm
cum au apărut.
Unul dintre matematicienii cei mai
importanți ai secolului al XI -lea, William
Hamilton , a inventat în 1857, un joc numit
jocul icosian, care constă în găsirea unui
ciclu – o succesiune de noduri cu
proprietățile că primul coincide cu ultimul și
muchiile sunt distincte – care să unească cele
20 de vârfuri ale unui dodecaedru (făcut din
lemn și care avea în fiecare vârf câte un cui
cu o floare mare), deplasarea făcându -se pe muchiile sale.
Rezultatele cercetăril or sale cu privire la existența algebrelor necomutative,
aplicate și la soluționarea jocului icosian, au fost comunicate public de către Hamilton în
1856 iar jocul său a fost comercializat în 1859 și era însoțit de instrucțiuni scrise de
Hamilton însuși, i nstrucțiuni care prezentau mai multe variante de joc. Astfel, se dădea
punctul de plecare, sau primele două puncte, sau primele trei puncte ale traseului.
[27]Definiție :
Într-un graf G(X,U,) se numește ciclu hamiltonian , un ciclu elementar (în care
nodurile sunt distincte) care conține toate nodurile grafului.
Un graf care conține un ciclu hamiltonian, se numește graf hamiltonian.
În fig.1 1 este reprezentat un graf care conține un ciclu hamiltonian:
C=[1,2,3,5,4,6,7,1].
Întrucât știm ce este un ciclu hamiltonian, putem înțelege ce este un graf
hamiltonian.
Graful prezentat în fig. 11 este un graf hamiltonian întrucât conține un ciclu
elementar care cuprinde toate nodurile grafului.
Trebuie menționat că un graf hamiltonian are cel puțin 3 noduri. Graful complet cu n
noduri este graf hamiltonian. În mod anal og se poate introduce noțiunea de lanț
hamiltonian. Figura 11
36 Grafuri neorientate -optimizarea procesului de predare
Un lanț elementar – în care nodurile nu se repetă – care conține toate nodurile
grafului, se numește lanț hamiltonian . În fig. 12 este reprezentat un astfel de lanț :
L=[1,4,2,6,5,3].
Figura 12
Revenind la grafurile hamilton -iene, putem determina dacă un graf este hamilton –
ian utilizând o teorem ă. Iată enunțul acesteia:
[27]Teoremă :
Dacă într -un graf G(X,U) cu numărul de noduri n>=3, gradul fiecărui nod este
mai mare sau egal cu n/2, atunci graful este hamiltonian.
Deși grafurile hamiltoniene au fost studiate de către mulți matematicieni, nu se
cunosc teoreme de caracterizare a lor (teoreme care să dea condiții necesare și suficiente
pentru ca un graf sa fie hamiltonian). Se cunosc doar condiți i suficiente care, într -un limbaj
simplist, exprimă faptul că un graf are "suficient de multe muchii".
Așadar condiția ca gradele tuturor nodurilor să fie mai mari sau egale cu n/2, este
suficientă, dar nu și necesară. Acest fapt se poate observa în fig. 13.
Graful este hamiltonian deși nu satisface condiția din teoremă, spre deosebire de
graful din fig. 14.
Figura 13 Figura 14
gr(1)=2 < 6/2=3 gr(1)=3 > 5/2=2.5 1 2
6
5
4 3
5
4 1 2
3 5 6 1 2
3
4
37 Grafuri neorientate -optimizarea procesului de predare
Programul C++ de verificare a proprietății de Hamiltonian a unui graf G(X,U) dat prin
matricea de adiacență este următorul:
– Programul utilizează tehnica Backtracking în varianta recursivă;
– Se generează toate ciclurile elementare distinc te ce cuprind toate nodurile grafului ;
– Soluția este prezentată sub forma unui șir de noduri reprezentând ciclul
Hamiltonian din graf, dacă acesta există, împreună cu mesajul de afirmare a
proprietății sau mesajul de infirmare a proprietății în caz contrar .
#include <iostream.h>
#include<conio.h>
int sw,a[10][10],st[10],n,k,t;
void init()
{ int i;
for(i=1;i<=t+1;i++)
st[i]=0;
}
int valid(int k)
{int i;
if((k>1)&&(a[st[k -1]][st[k]]==0))
return 0;
if((k>1)&&(k<t+1))
{
for(i=1;i<=k -1;i++)
if(st[k]==st[i])
return 0;
if(st[k]<st[k -1])
return 0;
}
if((k==t+1)&&(st[k]!=st[1]))
return 0;
return 1;
}
void tipar()
{int i;
for(i=1;i<=t+1;i++)
38 Grafuri neorientate -optimizarea procesului de predare
cout<<st[i]<<" ";
cout<<endl;
sw=1;
}
void bktr(int k)
{int i;
for(i=1;i<=n;i ++)
{
st[k]=i;
if(valid(k))
if(k==t+1)
tipar();
else
bktr(k+1);
}
}
void citiri()
{int i,j;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
a[i][i]=0;
for(i=2;i<=n;i++)
for(j=1;j<=i -1;j++)
{
cout<<"a["<<i<<"]["<<j< <"]=";
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
void meniu()
{
cout<<"1 -Introducere date"<<endl;
cout<<"2 -Generari cicluri"<<endl;
cout<<"3 -Parasire program"<<endl;
}
39 Grafuri neorientate -optimizarea procesului de predare
void main()
{int q;
do
{meniu();
cin>>q;
if(q==1)
{
citiri();
getch();
clrscr();
}
if(q==2)
{
sw=0;
t=n;
init();
bktr(1);
if(sw)
cout<<"Graful este Hamiltonian";
else
cout<<"Graful nu este Hamiltonian";
getch();
clrscr();
}
}while(q!=3);
cout<< "SFARSIT!";
}
1.3.4. Graf Eulerian
Pentru a înțelege utilitatea grafurilor euler -iene, în cadrul grafurilor neorientate,
plecăm de la definiția unui ciclu euler -ian.
[10]Definiție :
Având un graf G(X,U) neorientat, se numește ciclu euler -ian un ciclu care conține
toate muchiile grafului.
Un graf care conține un ciclu euler -ian se numește graf euler -ian.
40 Grafuri neorientate -optimizarea procesului de predare
Figura 15
Graful desenat în figura 15 este eulerian deoarece el conține un ciclu eulerian
C=[1,10,2,3,4,5,6,3,7,8,10,9,13,11,10,12,1].
Figura 16
Primul care s -a ocupat de acest tip de grafuri a fost Leonard Euler. El a plecat de la
o problemă practică. În orașul Konigsberg (azi Kaliningrad) existau peste râul Pregel șapte
poduri, ca în figura 16. Euler s -a întrebat dacă poate face o plimbare care să includă în
traseul său toate cele șapte poduri, astfel încât fiecare pod să fie traversat o singură dată.
Dacă asociem un graf în care vârfurile reprezintă cele șapte poduri a, b, c, d, e, f, g și cele
patru regiuni A,B,C,D iar muchiile indică posibilit ăți de trecere de pe un mal pe un pod și
invers, graf reprezentat în figura 17, existența traseului din enunțul problemei presupune
existența în graf a unui ciclu euler -ian. Să observăm că dacă un astfel de ciclu ar exista, la
fiecare trecere printr -un vâr f el ar utiliza două muchii, una pe care intră în vârf și una pe
care pleacă. Ar rezulta deci că în fiecare vârf muchiile s -ar grupa în perechi și, deci, pentru 3 10 1 2 4
5
6 7 8 9
13 11 12
41 Grafuri neorientate -optimizarea procesului de predare
d
X fiecare vârf ar exista un număr par de muchii incidente cu el, lucru neadevărat în graful din
figură: de exemplu d(A)=5.
Euler a soluționat această problemă și altele de același tip în anul 1736. Pentru
contribuția lui la studierea clasei grafurilor care posedă cicluri ce conțin toate muchiile,
aceste grafuri au fost numite mai târziu eulerie ne, la fel ca și ciclurile care caracterizează
aceste grafuri. Așa cum rezultă și din prezentarea succintă a istoriei teoriei grafurilor, de
grafurile euler -iene s -au ocupat mai mulți matematicieni în secolul XVIII și secolul XIX.
Dar rezultatele esențiale fuseseră descoperite de Euler.
Figura 17
În continuare vom da o condiție necesară și suficientă ca un graf care nu conține vârfuri
izolate să fie euler -ian.
[10]Teoremă:
Un graf G fără vârfuri izolate este euler -ian, dacă și numai dacă este conex și
gradele tuturor vârfurilor sunt numere pare.
Reamintim că un graf neorientat G(X,U) este conex dacă oricare ar fi două noduri
x, y din X există un lan ț de la x la y.
Figura 18
e A D
B C
c f
g
a b
1 2
3
4 5 8 7 6
42 Grafuri neorientate -optimizarea procesului de predare
Pe baza teoremei, graful din figura 18, este graf euler -ian deoarece nu are noduri
izolate, iar gradele tuturor vârfurilor sunt numere pare. Din matricea de adiacență putem
afla gradele nodurilor, astfel încât în figura de mai sus dăm ca exemplu gradul nod ului 2
care este egal cu 2, număr par (din nodul 2 pleacă două muchii 2 -1 și 2 -3), la fel avem și
pentru nodurile 1,4,5,6,7,8, cu excepția nodului 3 care are gradul egal cu 4 (tot număr par).
Denumirea de euler -ian este datorată și conexității grafului. D in definiția
conexității, observăm în exemplul din figura 18 existența lanțurilor între oricare două
noduri, formând un ciclu euler -ian (C=[1,2,3,6,7,8,3,4,5,1]) cu muchii distincte două câte
două (altfel spus, ciclul nu trece de două ori prin aceiași much ie) și consecutive, adică
muchiile [1,2], [2,3], [3,6], [6,7], [7,8], [8,3], [3,4], [4,5], [5,1].
1.3.5. Graf ponderat
[10]Definiție :
Considerăm un graf G=(X,U) și o funcție f:U R+ care asociază fiecărei muchii un
număr real pozitiv (care poate avea semnificația de cost, distanță, timp, durată).
[10]Definiție:
Un graf G=(X,U) pentru care s -a definit o funcție cost se numește graf ponderat.
Matricea costurilor
c, dacă există o muchie de cost c>0 între nodurile i și j, i j
a[i][j]= 0, dacă i=j
, dacă nu există muchie între vârfurile i și j, i j
c, dacă există o muchie de cost c>0 între nodurile i și j, i j
a[i][j]= 0, dacă i=j
-, dacă nu există muchie între vârfurile i și j, i j
[10]Algoritmul pentru crearea matricei costurilor – se citește pentru fiecare muchie
etichetele extr emităților ei și costul asociat(tabelul de mai jos).
43 Grafuri neorientate -optimizarea procesului de predare
1.4. NOȚIUNILE DE ARBORE ȘI ARBORE BINAR
1.4.1. Arbor i
Termenul de „arbore” din teoria grafurilor a fost folosit pentru prima dată de
Cayley în anul 1857 . El a plecat de la o analogie cu noțiunea de „arbore” din botanică.
Arborii au fost studia ți intensiv de numero și matematicieni și fizicieni, precum
matematicianul britanic Arthur Cayley , pe care l -au interesat aplica țiile lor în chimia
organică, de exemplu grafurile chimice, sau fi zicianul german G. R. Kirchhoff, care a
studiat această categorie pornind de la studiul re țelelor electrice .
Definiție .[6] Se numește arbore un graf neorientat conex și fără cicluri .
Exemplu de arbore
Graful G=(V,M) unde V={1,2,3,4}; M={[1,2],[2,3], [1,4]}, a cărui reprezentare grafică
este figurată mai jos, este arbore.
Graful prezentat mai sus este arbore, deoarece este conex și fără cicluri .
Proprietățile arborilor
[6]. Următoarele definiții sunt echivalente pentru un graf G cu n noduri și m muchii,
G=(V,M).
1. G este arbore .
2. G este un graf aciclic cu n-1 muchii .
Fig.19/ Exemplu de arbore 1
2 4
3
44 Grafuri neorientate -optimizarea procesului de predare
3. G este un graf conex cu n-1 muchii .
4. G este un graf conex , minimal cu această proprietate (dacă se elimină orice
muchie, se obține un graf neconex).
5. G este fără cicluri, maximal cu această proprietate(dacă se adaugă o muchie, se
obține un graf care are cel puțin un ciclu).
6. Orice pereche de noduri este legată printr -un lanț și numai unul.
Graf conex
Definiție . Fie G=(V,M), un graf neorientat. Graful G se numește conex , dacă pentru oricare
două vârfuri x, y, x ≠y, există un lanț în G de la x la y.
Lanț
Definiție . Fie G=(V, M) un graf neorientat. Se numește lanț, în graful G, o succesiune de
noduri, notată L=[x i1, xi2,……,x in], cu proprietatea că oricare două noduri consecutive sunt
adiacente, altfel spus [xi1,xi2],…..,[x ik-1,xik]∈M.
Exemplu : Pentru graful din fig.1 9, se verifică foarte ușor echivalența afirmațiilor din
teoremă.
Demonstrație :
Graful este arbore (conex și fără cicluri).
Graful este conex, minimal cu această proprietate, deoarece orice muchie s -ar elimina,
graful nu ar mai fi conex (fig.2 0).
Graful este fără cicluri, maximal cu această proprietate , deoarece orice muchie s -ar
adăuga graful ar conține cel puțin un ciclu (fig. 21).
s-a eliminat muchia [1,2] 4 1
2 3
s-a eliminat muchia [2,3] 4 1
2 3
s-a eliminat muchia[1,4] 4 1
2 3
Fig.20 / proprietatea 2 a arborilor
s-a adăugat muchia [4,3] 1
2 3 4
s-a adăugat muchia[2,4] 1
2 3 4
s-a adăugat muchia[1,3] 1
2 3 4
Fig.21 / proprietatea 3 a arbo rilor
45 Grafuri neorientate -optimizarea procesului de predare
[5]Demonstrație. Este suficient să se demonstreze implicațiile (1) ⟹(2), (2) ⟹(3), (3)
⟹(4), (4) ⟹(5), (5) ⟹(6), (6) ⟹((1). Prin tranzitivitatea acestor implicații rezultă
implicațiile : (2) ⟹(1), (3) ⟹(2), (4) ⟹(3), (5) ⟹(4),(6) ⟹(5) și (1) ⟹(6). Din aceste
implicații rezultă : (1) ⟺ (2), (2) ⟺ (3), (3) ⟺ (4), (4) ⟺ (5), (5) ⟺ (6), (6) ⟺(1). Din
tranzitivitatea relației de echivalență rezultă că oricare două din cele 6 propoziții sunt
echivale nte.
(1) ⟹(2). Ipoteză : Graful G este conex și aciclic – din definiția arborelui (1)
Concluzie: Graful G este aciclic și are n -1 muchii.
Proprietatea că graful G este aciclic este comună ipotezei și concluziei. Trebuie demonstrat
că un graf aciclic are n-1 much ii. Dacă G este un graf conex aciclic, nu trebuie eliminată
nici o muchie pentru a obține un graf parțial conex aciclic. Cum numărul de muchii care
trebuie eliminate dintr -un graf conex pentru a obține un graf parțial conex aciclic este
m-n+1, înseam nă că în acest caz m-n+1=0 . Rezultă că m=n -1.
(2) ⟹(3).Ipoteză: Graful G este aciclic cu n-1 muchii, din definiția arborelui (2).
Concluzie : Graful G este conex și are n-1 muchii (3).
Proprietatea că graful G are n-1 muchii este comună ipotezei și concluziei. Trebuie
demonstrat că un graf cu n-1 muchii fiind aciclic este și conex. Într-un graf cu p
componente conexe, numărul de muchii care trebuie eliminate pentru a obține un graf
parțial aciclic este egal cu m-n+p. Graful G este aciclic (m-n+p=0) și are n-1 muchii (m=n –
1) și (n-1)-n+p=0 . Rezultă că p=1 (graful are o singură componentă conexă, deci este
conex).
(3) ⟹(4). Ipoteză : Graful G este conex și are n-1 muchii (3).
Concluzie: Graful G este aciclic maximal .(4).
G este conex, numărul de componente conexe p este egal cu 1. Numărul de muchii m ale
grafului G este egal cu n-1. Rezultă că numărul de muchii care trebuie eliminate din graful
G ca să se obțină un graf aciclic este egal cu: m-n+1=(n -1)+n+1=0 , adică nici o muchie.
Rezultă că graful G este aciclic . Graful este maximal cu această pr oprietate , deoarece fiind
conex, orice muchie [xi,xj] care se va adăuga va forma un ciclu cu lanțul L(x i,xj)– existența
acestui lanț rezultă din conexitatea grafului G.
(4) ⟹(5). Ipotez a:Graful G este aciclic maximal (4).
Concluzie: Graful G este conex minimal (5).
a) Presupunem că graful G nu este conex. El are cel puțin două componente conexe: C1 și
C2. Înseamnă că există două noduri x ∈𝑪𝟏 și y ∈𝑪𝟐 pe care le putem lega cu muchia
[x,y]. Dar, din ipoteză, rezultă că orice muchie am adăuga la graf, el va conține un
46 Grafuri neorientate -optimizarea procesului de predare
ciclu. Rezultă că prin adăugarea muchie i [x,y] graful va conține un ciclu și că, între
nodurile x, y există deja un lanț și ele aparțin aceleiași componente conexe, ceea ce
contrazice presupunerea făcută. Rezultă că graful G este conex .
b) Presupunem că graful G care este conex nu este minimal cu această proprietate.
Înseamnă că prin eliminarea unei muchii se obține graful parțial H care are n noduri și
m-1 muchii, este conex și ac iclic. Graful G fiind conex și aciclic, înseamnă că numărul
de muchii care trebuie eliminate pentru a obține un graf parțial conex și aciclic este
egal cu 0, adică m-n+1=0 și m=n -1. Fiind aciclic înseamnă că numărul de muchii care
trebuie eliminate pentru a obține un graf parțial aciclic este 0, adică (n-2)-n+p=0 .
Rezultă că p=2, adică graful parțial H conține două componente conexe, ceea ce
contrazice presupunerea că el este conex .
(5) ⟹(6) Ipoteză: Graful G este conex minimal (5).
Concluzie: Orice pereche de noduri este legată printr -un lanț și numai unul (6).
Graful G fiind conex, înseamnă că există cel puțin un lanț care leagă oricare două noduri x
și y. Presupunem că există cel puțin două lanțuri între nodurile x și y : L1 și L2. Înseamnă
că, suprimând o muchie din lanțul al doilea , graful rămâne conex, deoarece nodurile x și y
vor fi legate prin lanțul L1, ceea ce contrazice ipoteza că graful G este conex minimal.
Rezultă că cele două noduri x și y nu sunt legate decât printr -un lanț.
(6) ⟹ (5) Ipoteza :Orice pereche de noduri este legată printr -un lanț și numai unul (6).
Concluzie: Graful G este conex și aciclic.
Deoarece în graful G, orice pereche de noduri x și y este legată printr -un lanț, înseamnă că
graful G este conex. Presupunem că graful G conține cel puțin un ciclu. Considerăm două
noduri oarecare x, y care aparțin acestui ciclu, înseamnă că între cele două există două
lanțuri diferite, ceea ce contrazice ipoteza. Rezultă că graful G este aciclic.
[6]Teor emă. Orice arbore, cu n ≥2vârfuri, conține cel puțin două noduri terminale.
Demonstrație. Presupunem că există un arbore A, cu n ≥ 2 vârfuri, care conține un singur
nod terminal; fie acesta x1.
Alegem în A cel mai lung lanț elementar, adică lanțul care conț ine numărul de muchii
maxim posibil, care -l admite pe x1 ca extremitate , fie acesta L=[x 1, x2, x3, …, x p-1, xp].
Deoarece x1 este singurul nod terminal, înseamnă că xp are gradul ≥ 2, deci pe lângă nodul
xp-1, mai este legat de cel puțin un alt nod, fie acesta y. Există două situații:
a) y nu aparține lanțului L , și atunci lanțul nu ar fi cel mai mare deoarece s -ar mai
putea prelungi cu muchia [xp,y]. Contradicție, deoarece am presupus că L este cel
mai lung.
47 Grafuri neorientate -optimizarea procesului de predare
b) y aparține lanțului L , și atunci am putea scoate în evidență ciclul [xp,y, … , x p-1, xp].
Contradicție, deoarece A este arbore și, deci nu conține cicluri.(fig. 22)
Contradicția provine din faptul că am presupus că A conține un singur nod terminal. În
concluzie, A are cel puțin două noduri terminale.
Teoremă . Orice arbore cu n noduri are n-1 muchii.
Demonstrație:
Fie A un arbore cu nvârfuri și A(n) numărul muchiilor acestuia. Enunțul teoremei
cere să se demonstreze că A(n)=n -1. Demonstrația teoremei se realizează recurgând la
principiul inducției matematice.
I. Verificare
Dacă n=1 ⇒ A(n)=A(1)=1 -1=0. Adevărat, deoarece arborele format dintr -un singur
nod nu are nici o muchie.
II. Demonstrația P(n) ⇒P(n+1)
P(n): A(n)=n -1
P(n+1): A(n+1)=(n+1) -1
Dacă se știe că un arbore cu n noduri are n-1 muchii, trebuie să se demonstreze că
un arbore cu n+1 noduri are n muchii.
Fie arborele A1 cu n+1 vârfuri, și xk un nod terminal al său. Dacă se elimină nodul
xk și muchia incidentă cu acesta se obține un arbore A cu n vârfuri care are conform
ipotezei, n-1 muchii (fig. 23).
y
xp
xp-1
x1
x2
xp
xp-1
x1
x2
y
Fig.22
A
xk xk A1
Fig.23
48 Grafuri neorientate -optimizarea procesului de predare
Ținând cont de faptul că A1 se obține adăugând la A nodul și muchia eliminată tragem
concluzia :
Arborele A1, cu n+1 noduri, are cu una mai multe muchii decât A, care are n-1
muchii, deci A1are 1+(n -1) muchii, adică n muchii.
Definiție . Fie G=(V,M) un graf. Graful G se numește aciclic dacă nu conține cicluri .
Definiție . Fie G=(V,M) un graf. Graful G se numește pădure dacă nu conține cicluri .
1.4.2. Arbori binari
[15].Se numește arbore binar un arbore cu rădăcină pozițional care are
proprietatea că fiecare nod are cel mult doi descendenți direcți (succesori).
Terminologie
Cei doi succesori ai unui nod (dacă există) se numesc succesorul stâng (subarborele
stâng) și succesorul drept (subarborele drept).
Caracteristici
Deoarece, oricare ar fi un nod al arborelui, el nu are mai mult de doi descendenți
direcți, ordinul unui nod dintr -un arbore binar poate fi 0 (nod terminal), 1 (unul din
subarbori este vid) sau 2.
Definiția arborelui binar este recursivă. Există un nod privilegiat – numit rădăcină, iar
celelalte noduri (dacă există) sunt repartizate în două grupuri disjuncte și, fiecare dintre
ele formează, la rândul său, un arbore binar.
Arbor ele binar strict.
[5]. Se numește arbore binar strict un arbore care are proprietatea că fiecare nod,
cu excepția nodurilor terminale, are exact doi descendenți (succesori).
Propoziția 1. Un arbore binar strict care are n noduri terminale , are în total 2xn-1 noduri . 5
9 10 rădăcina
6 3
8 1
2
4
7 11 Subarborele
stâng Subarborele
drept
Noduri terminale
(frunze)
Fig.24/Exemplu de arbore binar
49 Grafuri neorientate -optimizarea procesului de predare
Demonstrație . Notăm k numărul de nivele din arbore, cu xk, xk-1, …, x 2, x1, numărul de
noduri terminale de pe fiecare nivel, și cu yk, yk-1,…, y 2, y1, numărul de noduri de pe
fiecare nivel (cu excepția nivelului 0 pe care se găsește rădăcina), cu N – numărul total de
noduri din arbore ( N=y k + y k-1 + …+y 2 + y 1 + 1), cu n – numărul total de noduri terminale
(n=x k + xk-1 +….+ x 2 +x1). Nivelul k conține nu mai noduri terminale, yk = x k.. Pentru
fiecare alt nivel există relația: yi=yi+1/2+x i. Arborele fiind strict, yi+1/2 este un număr întreg
deoarece pe fiecare nivel există un număr par de noduri. Adunând relațiile obținem :
yk = x k
yk-1 = y k/2+x k-1
yk-2 = y k-1/2 + x k-2
……………………..
y2 = y 3/2 + x 2
y1 = y 2/2 + x 1
Rezultă că N=1+ y k + y k-1 + …+y 2 + y 1 + y 0 = 1 + 2*(x k+xk-1+…+x 2+x1) = 2xn+1
Proprietate. Un arbore binar strict are un număr impar de noduri.
Demonstrație . Pe fiecare nivel k+1, pentru fiecare nivel k există câte doi descendenți sau
nici un descendent. Rezultă că pe fiecare nivel, cu excepția nivelului 0, există un număr par
de noduri. Numărul total de noduri va fi impar deoarece la aceste noduri se adaugă nodul
rădăcină.
Arbore binar echilibrat
[5].Se numește arbore binar echilibrat un arbore binar care are proprietate a că
diferența dintre înălțimile celor doi subarbori ai oricărui nod este cel mult 1.
Arbore binar perfect echilibrat
[5].Se numește arbore binar perfect echilibra t un arbore binar care are proprietatea
că diferența dintre numărul nodurilor celor doi subarbori ai oricărui nod este cel mult 1.
Proprietate . Un arbore binar cu n noduri este perfect echilibrat dacă subarborele stâng are
[n/2] noduri și subarborele drept are n – [n/2] -1 noduri.
Arbore binar complet
[5]. Se numește arbore binar complet un arbore binar strict care are toate nodurile
terminale pe același nivel.
Proprietate. Un arbore binar complet , care are n noduri terminale, are în total 2xn-1
noduri.
Demonstrație . Folosind principiul inducției matematice, demonstrăm că într -un arbore
binar complet, pe nivelul k sunt 2k noduri.
50 Grafuri neorientate -optimizarea procesului de predare
P0 – pe nivelul 0 există un singur nod (nodul rădăcină) 20=1.
P1 – pe nivelul 1 există 2 noduri 21=2
………………………………………………..
Pk = pe nivelul k există 2k noduri
Pk+1– Considerăm propoziția Pk adevărată, trebuie să demonstrăm că pe nivelul k+1 există
2k+1 noduri. Dacă nivelul k+1 aparține arborelui, atunci pe acest nivel există doi
descendenți pentru fiecare nod de pe nivelul k, în total 2 x 2k = 2k+1.
Considerăm că arborele are k niveluri și că numărul de noduri de pe nivelul k este
n, numărul total de noduri din arbore se obține adunând nodurile de pe cele k niveluri:
20 + 21 + 22 + … + 2k = 2k+1-1= 2 x (2k)-1= 2n -1
Arbore binar aproape complet
[25].Se numește arbore binar aproape comple t un arbore binar complet până la
penultimul nivel, la care completarea pe ultimul nivel, se face de la stânga la dreapta.
Arbori de intervale.
Un arbore de intervale este un arbore binar în care fiecare nod poate avea asociată o
structură auxiliară (anumite informații).
Dându -se două numere st și dr , cu st < dr atunci arborele de interval T(st, dr) se
construiește recursiv astfel:
considerăm rădăcina nod având asoci at intervalul [st, dr];
dacă st < dr atunci, vom avea asociat subarborele stâng T(st, mij) , respectiv
subarborele drept T(mij+1, dr) , unde mij este mijlocul intervalului [st, dr] .
intervalul [st, dr] asociat unui nod se numește interval standard. Frunzel e arborelui
sunt considerate intervale elementare, ele având lungimea 1.
Proprietate. Un arbore de intervale este un arbore binar echilibrat ( diferența absolută
între adâncimea subarborelui stâng și a subarborelui drept este cel mult 1). Astfel
adâncimea unui arbore de intervale care conține N intervale este [log2 N] +1.
Fig.25/Arbori de intervale
51 Grafuri neorientate -optimizarea procesului de predare
1.4.3. Implementarea arborilor binari
[5].Implementarea structurilor de date tip arbore binar se poate face :
a) Static – folosind vectori
b) Dinamic – folosind pointeri
a) Implementarea statică a arborelui binar
Există două metode de implementare statică a arborilor binari (pentru exemplificare se
folosește arborele binar din fig. 24)
1. Folosind cei doi vectori în care se memorează cei doi succesori ai unu i nod
vectorul st – în elementul i se memorează eticheta nodului succesor stâng al
nodului i;
vectorul dr – în elementul i se memorează eticheta nodului succesor drept al
nodului i;
Dacă nodul i nu are succesor stâng, respectiv drept, elementul din vectorul st, respectiv dr,
va avea valoarea 0.
Pentru arborele din fig.24 cei doi vectori sunt :
Nodul i 1 2 3 4 5 6 7 8 9 10 11
st[i] 2 4 5 0 9 0 8 0 0 0 0
dr[i] 3 0 6 7 10 11 0 0 0 0 0
Observație . Din cei doi vectori putem obține următoarele informații:
Eticheta nodului rădăcină r – nodul i pentru care, oricare ar fi indicele j, st[j] ≠i și
dr[j] ≠i (nodul a cărui etichetă nu există nici în vectorul st, nici în vectorul dr).
Etichetele nodurilor ter minale – nodurile i pentru care st[i]+dr[i]=0;
eticheta părintelui unui nod i – indicele j pentru care st[j]=i sau dr[j]=i;
etichetele fiilor unui nod i – st[i] și dr[i] (dacă sunt diferiți de 0);
eticheta fratelui unui nod i – st[j] pentru dr[j]=i sau dr[j] pentru st[j]=i.
2. Folosind doi vectori în care se memorează filiația nodurilor
Vectorul tata – în elementul i se memorează numărul de ordine al nodului predecesor
(părinte) al nodului i;
Vectorul fii – în elementul i se memorează ce fel de succesor al părintelui este, dacă
fii[i]= -1, atunci nodul i este succesorul stâng al părintelui său, dacă fii[i]=1 , atunci
nodul i este succesorul drept al părintelui său. Dacă nodul i este nodul rădăcină,
elementul din vectorul tata, respectiv fii va avea valoarea 0. Pentru arborele din fig.24
cei doi vectori sunt:
52 Grafuri neorientate -optimizarea procesului de predare
nodul i 1 2 3 4 5 6 7 8 9 10 11
tata[i] 0 1 1 2 3 3 4 7 5 5 6
fii[i] 0 -1 1 -1 -1 1 1 -1 -1 1 -1
Observație . Din vectorul tata putem obține următoarele informații:
eticheta nodului rădăcină r – indicele i pentru care tata[i]=0 ;
etichetele nodurilor terminale – nodurile i a căror etichetă nu există în vectorul tata;
eticheta părintelui unui nod i – tata[i];
etichetele fiilor unui nod i – fiul stâng: indicele j pentru care tata[j]=i și fii[j]= -1,
iar fiul drept: indicele j pentru care tata[j]=i și fii[j]=1 ;
Eticheta fratelui unui nod i – indicele j pentru care tata[i]=tata[j] ;
b) Implementarea dinamică a arborelui binar
[5]. Se face prin definirea unui tip de dată pentru un nod din arbore (tipul nod) și a adresei
unui nod (un pointer către tipul de dată nod – nod*). Tipul de dată este definit ca o
înregistrare care conține 3 categorii de câmpuri:
Informația utilă – poate fi compusă din mai multe câmpuri (<tip> info) ;
Adresa subarborelui stâng – (nod *s →s este adresa rădăcinii subarborelui stâng);
Adresa subarborelui drept – (nod *d →s este adresa rădăcinii subarborelui drept);
Absența unui fiu (stâng sau drept) se marchează prin valoarea Null (0) a pointer -ului
corespunzător.
Se numește arbore vid un arbore care are adresa NULL.
Pascal
type nod=^inr;
inr=record
info:integer;
st, dr:nod
end; C++
struct nod{<tip> info:;
Nod *s, *d;}
nod *r; //adresa rădăcinii
53 Grafuri neorientate -optimizarea procesului de predare
CAPITOLUL II
ALGORITMI DE PRELUCRARE A GRAFURILOR NEORIENTATE
2.1.PARCURGEREA GRAFURILOR NEORIENTATE
Prin parcurgerea unui graf neorientat se înțelege examinarea(în ordinea numărului)
în mod sistematic a nodurilor sale plecând dintr -un vârf dat x i, astfel încât fiecare nod
acces ibil din x i pe muchii adiacente două câte două să fie atins o singură dată.
2.1.1. Parcurgerea în lățime
[27]Algoritmul de parcurgere în lățime BF(Breadth First) se bazează pe noțiunea de
coadă . Prin coadă înțelegem o succesiune ordonată de elemente, în care adăugarea
elementelor se face pe la un capăt, numit ”capăt de introducere”, iar eliminarea elementelor
se realizează la celălalt capăt, numit “capăt de extragere”. În orice moment putem scoa te
elementul aflat la capătul de extragere. Altfel spus, elementele ies din coadă în ordinea în
care au fost introduse. Datorită acestor proprietăți se vor numi cozi FIFO (“First In First
Out”), în traducere “primul intrat primul ieșit”.
Exemplu concret de coadă:
Pentru fiecare zbor de călători, o companie aviatică întocmește o listă a persoanelor
care încă mai solicită bilete după epuizarea acestora. Lista este organizată sub forma unei
cozi de așteptare, ce cuprinde numele si numărul actului de identitate al fiecărui solicitant.
În momentul în care o persoană dorește un bilet, este introdusă în coadă. Dacă în urma
unei renunțări apare un bilet disponibil, acesta este atribuit primei persoane care a fost
introdusă în coadă. Beneficiarul iese din coadă, iar capătul de extragere avansează cu o
poziție.
Coada poate fi implementată cu ajutorul unui vector. Vom nota:
-pi: poziția capătului pe la care se introduc elementele în coadă;
-ps: poziția capătului pe la care se extrag (se scot) elementele din coadă;
-max: numărul maxim de elemente din coadă;
Pentru o înțelegere mai bună, vom prezenta un exemplu:
const max=50 ;
var c:array [1..max ] of integer;
54 Grafuri neorientate -optimizarea procesului de predare
pi ps
Figura 26
În cazul în care nu avem elemente(pi <ps) vom considera coada ca fiind coadă
vidă, iar dacă nu se mai pot adăuga elemente(p i=max) vom numi coadă plină .
Adăugarea elementelor poate fi descrisă astfel:
a) adăugarea unui element: înseamnă creșterea lui pi cu o unitate și memorarea
elementului pe noua poziție pi(elementul c[pi]). Se poate face numai în cazul în
care coada nu este plin ă(pi ≠max).
b) Extragerea unui element: î nseamnă creșterea lui ps cu o unitate. Poate avea loc
numai în cazul în care coada nu este vidă(pi > ps).
Să urmărim evoluția unei cozi în care introducem și extragem aleator câteva elemente.
În coada inițial vidă, introducem elementul cu valoarea 5.
5
ps=pi=1
Pe la același capăt introducem în coadă elementul 7.
5 7
ps=1 pi=2
Adăugăm și elementul -4.
5 7 -4
ps=1 pi=3
și în final extragem un element din coadă, cel introdus primul, adică 5.
7 -4
ps=2 pi=3 Figura 27 Figura 27
Figura 2 8
Figura 29
Figura 30
55 Grafuri neorientate -optimizarea procesului de predare
Pentru un graf G(X,U) se procedează astfel:
Se pornește de la un vârf de start care se vizitează, apoi se vizitează toți vecinii lui.
Pentru fiecare dintre aceste vârfuri, se vizitează vecinii lui care nu au fost încă vizitați.
Pentru noile vârfuri, se procedează la fel: se vizitează vecinii acestora care nu au
fost încă vizitați. Procedeul continuă până când s -au vizitat toate vârfurile.
Fie graful G=(X,U) din figura 31. Presupunem că vârful de start este 1. Pașii
parcurgerii: Noduri vizitate
a)vizităm mai întâi vârful de start 1; 1
b)vizităm apoi vecinii lui 1 care sunt 2,5,6; 2,5,6
c)pentru fiecare dintre acești vecini ai lui 1, vizităm vecinii
săi nevizitați încă:
-vecinii lui 2 sunt 1,3 și 4,dar nevizitați sunt numai 3 și 4; 3,4
-vecinii lui 5 sunt 1,2,7 dar nevizitat este numai 7 7
-vârful 6 nu mai are vecini nevizitați
d)am vizitat până acum vecinii vârfurilor 1,2,5 și 6. Mai trebuie vizitați vecinii noilor
vârfuri vizitate la p asul anterior și anume vecinii vârfurilor 3,4 și 7. Dar observăm că
vârfurile 3,4 și 7 nu mai au vecini nevizitați, deci parcurgerea se încheie.
Ordinea vizitării vârfurilor în parcurgerea BF este 1,2,5,6,3,4,7.
Vom folosi o coadă implementată cu ajutorul unui vector c. Capetele de introducere
și extragere vor fi identificate prin pozițiile pi respectiv ps. Introducem mai întâi nodul de
start în coadă, apoi în mod repetat până la vizitarea tuturor nodurilor:
– extragem din coadă vârful aflat în capătul de ext ragere și îl vizităm;
– introducem în coadă, pe la celălalt capăt, capătul de introducere, vecinii nevizitați ai
vârfului tocmai extras.
Să urmărim “evoluția” cozii pentru același graf din exemplul de mai sus:
Introducem în coadă vârful de start 1.
Figura 31
Figura 32
56 Grafuri neorientate -optimizarea procesului de predare
Extragem vârful 1 și introducem
vecinii săi nevizitați(neintroduși încă) 2,5 și 6.
Extragem 2 și introducem
vecinii săi nevizitați
Extragem 5 și introducem
unicul său vecin nevizitat 7.
În continuare, se vor extrage pe rând vârfurile 6,3,4,7. Nici unul dintre aceste vârfuri nu
mai are vecini nevizitați, deci nu se va mai introduce nimic în coadă. În concluzie capătul
de introducere pi nu se mai modifică.
Observație: După fiecare extragere a unui vârf, capătul de extragere ps se va muta
la poziția următoare celei de pe care s -a făcut extragerea. De exemplu, după ce am extras
vârful 5 de pe poziția 3, ps s -a mutat la poziția următoare lui 3, adică 4. Așa se face că după
extragerea ultimului vârf de pe poziția 7, capătul de extragere ps va deveni 8, d eci se va
muta dincolo de capătul de introducere pi (care ramâne 7).
Concluzia? Ciclul ai cărui pași au fost descriși mai sus, se execută cât timp pi>=ps!
Ordinea în care au fost extrase
nodurile este 1,2,5,6,3,4,7.
Implementarea algoritmului
Funcția pentru afișarea succesiunii nodurilor la aplicarea algoritmului B.F. pe un
graf neorientat G(X,U) cu n noduri dat prin matricea de adiacență a este următoarea:
void bf(int a[10][10],int n)
{
int i,viz[10],c[10],pi,ps,pstart;
cout<<"Nodul de start: ";
Figura 33
Figura 34
Figura 35
Figura 36
57 Grafuri neorientate -optimizarea procesului de predare
cin>>pstart;
for(i=1;i<=n;i++)
viz[i]=0;
pi=1;
ps=1;
viz[pstart]=1;
c[pi]=pstart;
while(pi>=ps)
{
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
cout<<"Ordinea nodurilor este: ";
for(i=1;i<=pi;i++)
cout<<c[i]<<' ';
}
2.1.2.Parcurgerea în adâncime
[15]Implementarea acestei metode de parcurgere se face folosind o structură de
date de tip stivă . Stivele sunt structuri de date în care elementele sunt inserate și eliminate
pe la un capăt numit vârful stivei . Ele sunt structuri de tip LIFO ( Last In First Out –
ultimul venit, primul ieșit). Asupra un ei stive acționează operatori specifici cum ar fi:
inițializare stivă, test de stivă vidă, ad augă un element la stivă, scoate un element din stivă .
Stivele pot fi implementate static(cu variabile de tip tablou unidimensional) sau dinamic,
sau se pot utiliza tehnicile recursive. În acest caz stiva este inițializată cu un nod oarecare
al grafului, nod considerat și nod de start. La fiecare pas, pentru nodul aflat în vârful stivei,
se adaugă la stivă primul vecin nevizitat al nodului respectiv. În situația în care nodul din
vârful stivei nu mai are vecini nevizitați atunci el se va elimina din stivă.
Algoritmul continuă în același mod pâna când au fost vizitate toate nodurile
grafului.
Fie graful din figura 37 care are n = 5 noduri ; vom considera ca nod de start ns=1:
58 Grafuri neorientate -optimizarea procesului de predare
Vom folosi un vector v, cu un număr de elemente egal cu numărul de noduri din graf,
pentru a marca nodurile vizit ate. Fiecare element din vectorul v poate lua următoarele
valori:
v[i]=0, pentru nodul i nevizitat
v[i]=1, pentru nodul i vizitat, unde i poate fi oricare nod din graf.
Inițial toate nodurile grafului sunt nevizitate. După fixarea unui nod de start ns=1 acesta
va fi marcat ca fiind vizitat (v[ns]=1) și va fi așezat în stivă. Din nodul de start plecăm
către primul nod adiacent cu el și nevizitat. Pentru exemplul luat mai sus acest nod este 2:
Nodul 2 se va marca vizitat și va fi adăugat la stivă. În acest moment în vârful stivei este
situat nodul 2. Aplicând în continuare algoritmul dat nodul care va fi adăugat la stivă va fi
nodul de informație 4.
Următorul nod adăugat la stivă va fi nodul cu informația 3. El va fi marc at ca vizitat și va
fi afișat. Figura cu succesiunea nodurilor parcurse este:
Figura 39 Figura 38 Figura 37
59 Grafuri neorientate -optimizarea procesului de predare
În acest moment nodul din vârful stivei nu mai are noduri adiacente nevizitate și deci
el trebuie eliminat din stivă . Revenim la nodul 4 și care mai are un nod adiacent nevizitat
și anume nodul de informație 5. Acestui nod i se aplică același algoritm: este trecut în stivă,
marcat vizitat și afișat.
În acest moment toate nodurile grafului vor fi eliminate rând pe rând din stivă, deoarece ele
nu mai au noduri adiacente și nevizitate, iar la final stiva este vidă . În acest moment
algoritmul se termină, rezultatul parcurgerii în adâncime pentru graful luat ca exemplu
fiind: 1, 2, 4, 3, 5. Este posibil ca după un apel al funcției de parcurgere în adâncime
începând cu un anumit vârf ns, să rămână în graf vârfuri neparcurse. În această situație
graful nu este conex, ci este alcătuit din mai multe componente conexe, iar apelul funcției
se va repeta pentru un alt no d ales dintre vârfurile neparcurse până la parcurgerea tuturor
nodurilor grafului. Programul apelant trebuie să asigure parcurgerea vârfului utilizat în
apel.
Varianta iterativă a algoritmului de parcurgere în adâncime este:
1. citește n numărul de noduri din graf
2. memorează graful folosind matricea de adiacență
3. citește pstart nodul de start
4. marchează pstart ca fiind nod vizitat
5. afișează pstart
6. afișează nodul de start ca prim nod în stivă
7. cât timp nu ai vizitat toate nodurile execută
dacă nodul din vârf mai are noduri adiacente nevizitate atunci
– îl adaugi la stivă pe primul nod adiacent cu nodul din vârf
– îl marchezi vizitat
– îl afișezi
altfel
– ștergi din stivă primul nod
Figura 40
Figura 41
60 Grafuri neorientate -optimizarea procesului de predare
sfărșit dacă
sfărșit cât timp
Implementarea algoritmului
Funcția pentru afișarea succesiunii nodurilor la aplicarea algoritmului D.F. pe un
graf neorientat G(X,U) cu n noduri dat prin matricea de adiacență a este următoarea:
void df(int a[10][10],int n)
{
int i,viz[10],st[10],k,pstart,sw;
cout<<"Nodul de start: ";
cin>>pstart;
for(i=1;i<=n;i++)
viz[i]=0;
k=1;
viz[pstart]=1;
st[k]=pstart;
cout<<"Ordinea nodurilor este: ";
cout<<pstart<<' ';
while(k>0)
{
sw=0;
for(i=1;i<=n&&sw==0;i++)
if(a[st[k]][i]==1&&viz[i]==0)
{
sw=1;
k++;
st[k]=i;
viz[i]=1;
cout<<i<<' ';
}
if(sw==0)
k–;
}
}
61 Grafuri neorientate -optimizarea procesului de predare
2.2. CONEXITATE ÎN GRAFURI NEORIENTATE
2.2.1. V erificarea conexității unui graf
[27]Definiție :
Un graf G(X,U) este conex, dacă oricare ar fi două vârfuri ale sale există un lanț
care le leagă.
Fie graful G(X,U) din figura 42:
Aplicarea algoritmului de parcurgere în lățime B.F. pe graful de mai sus,
furnizează, indiferent de nodul ales ca punct de start, un șir de valori ce conține toate
nodurile grafului.
Ordinea vizitării vârfurilor în parcurgerea BF cu nod de start 1 este 1, 2, 5, 6, 3, 4, 7.
Șirurile obținute sunt de fapt lanțuri, ce unesc două noduri, trecând prin (n -2)
noduri intermediare. Rezultă că luând oricare două noduri, ele pot fi unite printr -un lanț,
ceea ce arată că graful din figură este conex.
Verificarea proprietății de graf conex se f ace simplu prin aplicarea algoritmului de
parcurgere în lățime B.F.; ulterior, dacă au fost vizitate toate nodurile (echivalent cu
depunerea în coadă a tuturor nodurilor), graful are proprietatea de conex.
Programul C++ pentru verificarea proprietății de conex a unui graf G(X,U) cu n
noduri dat prin matricea de adiacență a, este următorul:
#include<iostream.h>
#include<conio.h>
int viz[30],n,k,u,v,p,a[20][20],c[30],pstart;
void introducere()
{
int i,j;
cout<<"Dati numarul de varfuri n=";
Figura 42
62 Grafuri neorientate -optimizarea procesului de predare
cin>>n;
for(i= 1;i<=n -1;i++)
for(j=i+1;j<=n;j++)
{
cout<<"a["<<i<<"]["<<j<<"]'=";
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
int bf()
{
int i,viz[10],c[10],pi,ps;
cout<<"Nodul de start: ";
cin>>pstart;
for(i=1;i<=n;i++)
viz[i]=0;
pi=1;
ps=1;
viz[pstart]=1;
c[pi]=pstart;
while(pi>=ps)
{
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
return(pi==n);
}
void main()
{
clrscr();
introducere();
if(bf())
cout<<"Graful este conex";
63 Grafuri neorientate -optimizarea procesului de predare
else
cout<<"Graful NU este conex";
getch();
}
2.2.2. D escompunerea în componente conexe a unui graf neorientat
[27]Definiție :
Se numește componentă conexă a grafului G =(X,U), un subgraf G1 =(X1,U1)
a lui G, conex, cu proprietatea că NU există LANȚ care să lege un nod din X1 cu unul
din X -X1.
Dacă se consideră nodul 1 ca punct de start la aplicarea algoritmului B.F. pe graful
din figura 43, atunci:
– vecinii lui 1 sunt 2 și 4
– vecinul nevizitat a l lui 2 este 3
– vecinul nevizitat a l lui 4 este 5
Ordinea vizitării nodurilor este 1,2,4,3,5 iar nodurile nevizitate sunt: 6,7,8,9.
Similar, dacă se consideră exemplul nodului 6 ca punct de start , se pot vizita numai
nodurile 6, 7, 8, 9, rămânând nevizitate următoarele noduri: 1,2,3,4,5.
Prin urmare, la o parcurgere nu se pot vizita toate nodurile , consecința fiind
clară : nu oricare două noduri pot fi legate printr -un traseu de tip lanț , rezultând că
graful nu este conex, acesta deținând componente conexe.
Din definițiile și exemplele anterioare , se desprind următoarele concluzii care sunt
foarte importante: 2
1 3
5
4 6 7
9 8
Figura 43
64 Grafuri neorientate -optimizarea procesului de predare
-Dacă numărul componentelor conexe dintr -un graf este mai mare decât 1, atunci
graful nu este con ex.
-Un graf conex are o singură componentă conexă, care cuprinde toate n odurile sale.
– Un nod izolat reprezintă o componentă conexă.
Programul C++ pentru descompunerea în componente conexe a unui graf G(X,U)
cu n noduri dat prin matricea de adiacență a, este următorul:
#include<iostream.h>
#include<conio.h>
int viz[ 30],n,k,u,v,p,a[20][20],c[30],pstart;
void introducere()
{
int i,j;
cout<<"Dati numarul de varfuri n=";
cin>>n;
for(i=1;i<=n -1;i++)
for(j=i+1;j<=n;j++)
{
cout<<"a["<<i<<"]["<<j<<"]'=";
cin>>a[i][j];
a[j][i]=a[i][j];
}
cout<<"Dati varful de plecare ";
cin>>pstart;
for(j=1;j<=n;j++)
viz[j]=0;
}
void bf()
{
int i,pi,ps;
pi=1;
ps=1;
viz[pstart]=1;
c[pi]=pstart;
while(pi>=ps)
{
65 Grafuri neorientate -optimizarea procesului de predare
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
if(pi==n)
cout<<"Graful este conex";
else
{
cout<<"Componenta conexa"<<endl;
for(i=1;i<=pi;i++)
cout<<c[i]<<' ';
cout<<endl;
}
}
void meniu()
{char c1,w;
do
{
clrscr();
cout<<"0 -Introducere date"<<endl;
cout<<"1 -Afisarea rezultatelor"<<endl;
cout<<"2 -Parasire program"<<endl;
cout<<"Introduceti optiunea: ";
cin>>c1;
if(c1=='0')
{
introducere();
}
if(c1=='1')
{
do
{
bf();
pstart=1;
66 Grafuri neorientate -optimizarea procesului de predare
while(viz[pstart]==1&&pstart<=n)
pstart++;
}while(pstart<=n);
cout<<endl;
cout<<"apasati o litera";
cin>>w;
}
}while(c1!='2');
}
void main()
{
meniu();
}
67 Grafuri neorientate -optimizarea procesului de predare
CAPITOLUL III
METODE ȘI STRATEGII DIDACTICE DE ÎNVĂȚARE ȘI
EVALUARE
„Nu exista metode bune sau rele ci metode adecvate, bine sau prost utilizate”
(I. Cerghit)
3.1. METODE DIDACTICE
[18]. Reforma în învățământ se referă la toate aspectele sale, de la conținuturile
programelor și manualelor până la formele de organizare și desfășurare a activității de
predare – învățare – evaluare, metodele și mijloacele folosite, știut fiind că școala activă și
eficientă are la bază anumite trebuințe: a face, a ști ceea ce faci și cum faci precum și a face
și a simți ceea ce faci.
Reușita în atingerea scopurilor vizate de activitatea de instrucție și educație este
dependentă direct sau indirect, dar în mod hotărâtor, de abilitatea profesorului pentru ce are
de făcut.
Metodele de învățământ sunt o componentă importantă a strategiilor didactice,
reprezentând sistemul de căi, modalități, procedee, tehn ici și mijloace adecvate de instruire,
care asigură eficiența procesului de predare -învățare.
Metoda este calea urmată pentru atingerea unui scop, pentru obținerea unui rezultat,
un mod sistematic de lucru și gândire. Prin metodă de învățământ se înțeleg e un anumit
mod de organizare sau raționalizare a unei acțiuni determinate de predare și învățare.
Metoda de învățământ precizează „în ce fel”, „cum”, anume trebuie să acționeze profesorul
împreună cu elevii săi pentru a realiza obiectivele propuse la un n ivel de performanță cât
mai înalt.
Datorită complexității situațiilor de predare -învățare, metodele de învățământ nu se
pot folosi în mod izolat, ci ele se structurează în complexe de metode, mijloace și tehnici în
raport de situația pe care o servesc. Ace astă combinare între metode, mijloace și tehnici
adecvate situațiilor de predare -învățare este cunoscută sub numele de strategie didactică.
3.2. FUNCȚIILE PEDAGOGICE ALE METODELOR DIDACTICE
[18]. Vizează interdependența celor trei acțiuni care asigură uni tatea informativ –
formativă, a activității de instruire. Ele reflectă, în același timp, corespondentele curriculare
68 Grafuri neorientate -optimizarea procesului de predare
necesare și perfectibile permanent între obiectivele pedagogice -conținuturile instruirii și
metodologia activității de predare – învățare – evaluare.
Funcțiile metodelor didactice evidențiază valoarea acestora de „modele
pedagogice”, situate la diferite „poluri” de referință:
Funcția normativă a metodelor didactice corespunde „ polului axiologic ” al
activității de predare -învățare -evaluare. Acea stă funcție evidențiază resursele
generale ale metodelor didactice, interne și externe care asigură premisa optimizării
permanente a activității didactice.
Funcția cognitivă a metodelor didactice corespunde „ polului științific al activității
de predare -învățare -evaluare ”. Această funcție evidențiază rolul specific al
metodelor didactice angajate în activitatea de predare -învățare -evaluare.
Funcția formativă a metodelor didactice, corespunde „ polului psihologic ”al
activității de predare -învățare -evaluare. Ac eastă funcție evidențiază contribuția
metodelor didactice la dezvoltarea capacităților de învățare ale elevului. Calitatea sa
rezultă din faptul că, în mod obiectiv, „calea pe care se face transmiterea
cunoștințelor este totodată și un proces educativ”.
Funcția operațională a metodelor didactice corespunde „ polului praxiologic ” al
activității de predare -învățare -evaluare. Această funcție evidențiază valoarea
instrumentală a metodelor didactice care sunt proiectate ca intermediar între subiectul
și obiectu l procesului de învățământ, între obiectivele inițiale și rezultatele finale.
3.3. CLASIFICAREA METODELOR DE INVĂȚĂMÂNT
[18]. A. METODE TRADIȚIONALE DE PREDARE -INVĂȚARE
I. Metode de comunicare orală:
expozitive : explicația, povestirea, descrierea, prelegerea.
conversative: conversația, dezbaterea, problematizare a.
II. Metode de comunicare scrisă:
tehnica lecturii;
instructajul scris.
III. Metode de explorare directă a realității:
Studiul de caz;
Experimentul;
Observarea sistematică și independent ă.
IV. Metode de explorare indirecta a realității:
69 Grafuri neorientate -optimizarea procesului de predare
Demonstrația;
Modelarea.
V. Metode de acțiune reală asupra realității:
Exercițiul;
Proiectul;
Metoda lucrărilor practice.
VI. Metode de acțiune fictivă (simulată) asupra realității:
Jocul didactic;
Metoda dramatizării;
Învățarea pe simulatoare.
VII. Metode de raționalizare a predării – învățării:
Metoda activității cu fișele;
Metode algoritmice de instruire;
Instruirea programată;
Instruirea asistată pe calculator.
[18]. B. METODE ACTIVE DE PREDARE -INVĂȚARE
I. Metode pentru dezvoltarea gândirii critice:
Prelegerea intensificată;
SINELG(Sistemul Interactiv de Notare pentru Eficientizarea Lecturii și a Gândirii);
Jurnalul dublu;
Știu/Vreau să știu/Am învățat;
Organizatorul grafic;
Cubul;
Cvintetul.
II. Metode de învățare prin cooperare:
Gândiți/Lucrați în perechi/Comunicați;
Predarea reciprocă;
Mozaicul;
Rețeaua de discuții;
Controversa academică;
Linia valorilor;
Turul galeriei;
Unul stă, trei circulă.
70 Grafuri neorientate -optimizarea procesului de predare
3.4 METODE SPECIFICE DE PREDARE A INFORMATICII
[17].Diferite domenii ale informaticii necesită abordarea unor metode specifice de
predare care se vor combina optim cu metodele generale de predare – învățare (tradiționale,
moderne).
Metodele specifice informaticii se pot clasifica în func ție de domeniul clar unde se
aplică:
1. Metode de predare a algoritmilor și tehnicilor de programare;
2. Metode de predare a unui limbaj de programare;
3. Metode de predare a sistemelor utilitare;
Fiecare din clasele de metode menționate pot fi divizate în funcție de orientarea dorită
astfel:
Clasă
de
modele Orientare Specific Metode de predare a algoritmilor și tehnicilor de programare 1.Orientat pe
algoritmi accent pe conceperea algoritmului;
proces de programare indivizibil;
dezvoltarea de aplicații indiferent de limbaj;
formarea gândirii algoritmice;
2.Orientat pe tipuri
de probleme seturi de probleme cu dificultate gradată;
fiecare set specific unei clase de probleme;
dezvoltarea algoritmică treptată, unul din celălalt;
specifice învățării pe unități de învă țare distincte cu
accent deosebit pe programarea modulară;
3.Orientat pe limbaj rezolvarea problemelor vine în ajutorul testării
posibilității limbajului de programare;
limbajul de programare este prezentat riguros până în
cele mai mici amănunte;
nu se recomandă traducerea unui algoritm în mai
multe limbaje de programare decât după stăpânirea
perfectă a unui limbaj și doar în scopul comparării
anumitor particularități ale acestora;
4.Orientat pe
structuri și Se introduc concepte generale v alabile pentru o clasă
de limbaje (programarea structurată, programarea
71 Grafuri neorientate -optimizarea procesului de predare
instrucțiuni orientată pe obiecte, sisteme de gestiune a bazelor de
date); Metode de predare a algoritmilor și tehnicilor de
programare 5.Orientat pe
matematică apar din necesitatea rezolvării problemelor de
matematică cu ajutorul calculatorului. Cunoașterea
teoriei matematice este absolut necesară în cazul
rezolvării anumitor probleme, dar nu toate problemele
de informatică sunt din domeniul matematicii (trans și
interdisciplinaritatea informat icii)
este necesară stăpânirea temeinică a unor cunoștințe
de matematică (teoria numerelor, polinoame,
recursivitate, etc);
6.Orientat pe
hardware cunoașterea perfectă a unui limbaj de programare
până în detaliu presupune cunoștințe ample despre
limbajul cod-mașină, procesoare, memorii, alte
componente hardware. Metode de predare a unui limbaj de programare 1.Orientat pe
instrucțiuni limbajul de programare este considerat ca fiind
alcătuit dintr -o mulțime de instrucțiuni care sunt
învățate treptat într -o ordine prestabilită;
2.Orientat pe
utilizare ținând cont de punctele de vedere generale se va preda
după un anumit concept și apoi se va dezvolta după
anumite concepte;
elementele de limbaj sau de mediu de programare sunt
introduse treptat în funcție de cerințele conceptului de
bază;
3.Orientat pe
problemă problemele sunt gradate și cu rolul de a fixa
cunoștințe specifice limbajului de programare și cu
mic accent pe algoritmi;
tehnicile de rezolvare a problemelor reprezintă
instrumente de dobândire și testare a posibilităților
limbajului;
4.Orientat pe limbaj
elementele de limbaj capătă o importanță deosebită;
5.Orientat pe modele pe baza unor exemple concrete de rezolvare de
72 Grafuri neorientate -optimizarea procesului de predare
de probleme probleme;
prezentarea avantajelor unor tehnici de rezolvare în
raport cu dezavantajele alteia ; Metode de predare a sistemelor utilitare 1.Orientat pe
problemă predarea conceptelor de bază a componentelor și a
modului de utilizare se face treptat, gradat, pornind de
la necesitatea rezolvării unei probleme pe baza unui
instrument informatic: sistemul de operare Windows,
editoare de texte, calcul tabelar etc;
2.Orientat pe
meniuri pe baza meniurilor unei anumit utilitar se pot rezolva
aplicații ce combină comenzile și/sau opțiunile
acestora în scopul fixării lor.
3.Orientat pe funcții în urma determinării funcțiilor generale ale unui
utilitar sau ale unei aplicații se va prezenta apoi modul
concret în care acestea se realizează de către utilitar;
4.Orientat pe
concepte se definesc concepte care stau la baza utilitarului;
se prezintă funcțiile care stau la baza acestor
concepte;
asimilarea se va face treptat pe măsura utilizării
repetate a utilitarului sau mediului de informație;
3.5 PREDAREA PRIN METODA CONVERSAȚIEI
[20]. Instruirea elevilor prin metode conversative se realizează pe baza unor convorbiri
organizate și desfășurate sub conducerea profesorului.
Conversația este metoda care vehiculează cunoștințele prin intermediul dialogului
(întrebărilor și răspunsurilor), d iscuțiilor sau dezbaterilor. Pe parcursul lecției ea se
folosește în toate etapele acesteia: ver ificare, transmitere și fixare.
Conversația se realizează prin dialogul dintre cadrul didactic și elevi. Aceasta îi
ajută pe tineri să exprime, să judece (să gândească) și să răspundă, să reproducă și să
folosească cunoștințele asimilate, caracteristici absolut necesare comunicării efici ente între
oameni. Condusă cu măiestrie și competență pedagogică, conversația stabilește o relație și
o comunicare intimă și eficientă între inteligența profesorului și cea a elevului, permițând o
activitate intelectuală și profesională elevată, care poate asigura progresul învățării și
satisfacția acesteia.
73 Grafuri neorientate -optimizarea procesului de predare
Conversația angajează un sistem determinat de interacțiuni verbale profesor -elevi,
și are o multitudine de funcții, cum ar fi:
a. funcția euristică , de descoperire a noi adevăruri (de asimilare a noi cunoștințe) și
formativă în același timp (conversație de tip euristic);
b. funcția de clarificare , de sintetizare și a profundare a cunoștințelor, cu care elevii
au avut un anumit contact cognitiv în prealabil (conversația de aprofundare);
c. funcția de verificare sau de control (de examinare și evaluare) a performanțelor
învățării (conversația de verificare).
Metoda conversației favorizează perfecționarea relației profesor -elev, stimulează
efortul elevilor pentru exprimări clare și răspunsuri corecte și dezvoltă ambiția elevilor de
exprimare intelectuală, curiozitatea și inițiativa lor.
Conversația euristică .
Acest tip de conversație se desfășoară pe baza unei succesiuni de întrebări puse de
profesor, în alternanță cu răspunsurile elevilor. Întrebăril e enunțate, au menirea:
– să succinte curiozitatea, necesitatea de cunoaștere;
– să incite la căutări, la sesizarea unor relații cauzale, la descoperirea notelor
caracteristice și comune unui grup de obiecte sau categorii de fenomene;
– să conducă la în sușirea de noi generalizări, la formularea de noi concluzii;
– să imagineze și să propună soluții și variante originale de rezolvare;
– să prelucreze propriile cunoștințe și să ajungă la noi structuri cognitive .
Această metodă nu poate fi aplicată la în sușirea unui material complet nou pentru
elevi, despre care aceștia nu posedă nici un fel de informație anterioară.
3.6 ÎNVĂȚAREA PRIN DESCOPERIRE
[17]Instruirea prin metode de explorare/investigare directă este înțeleasă ca
modalitate de lucru datorită căreia elevii sunt puși să descopere adevărul refăcând drumul
elaborării cunoștințelor prin activitate proprie, independentă. A apărut ca necesitate de a -l
situa pe elev în iposta za de subiect al cunoașterii științifice.
Aceste metode au un caracter participativ și euristic, fiind folosite cu succes pentru
pregătirea studiului teoretic al unui utilaj, privind construcția și funcționarea sa. Astfel,
observarea poate merge până la executarea schemelor tehnologice și cinematice ale
utilajelor de către elevi și explicarea funcționării acestora.
Descoperirea la care îi duce această metodă pe elevi este o descoperire școlară sau
redescoperire dirijată în care rolul profesorului (cadrulu i didactic) este de a asigura o
74 Grafuri neorientate -optimizarea procesului de predare
îndrumare suficientă și stimulatoare, de a conduce etapele activităților elevilor și de a grada
sarcinile.
Instruirea prin explorare se realizează prin variantele:
– observarea dirijată are drept obiect observarea unor materiale, fenomene,
utilaje, sc ule etc., descrierea și interpretarea rezultatelor;
– observarea independentă urmărește în afara scopului informațional și formarea
deprinderilor de a sesiza ușor ce este esențial și semnifica tiv în realitatea
înconjurătoare, necesitatea de prim ordin în formarea omului modern;
– efectuarea de încercări;
– efectuarea de experiențe .
Instruirea prin efectuarea de încercări și experiențe (dirijată sau independentă ) are
ca obiect realizarea de activită ți de tip experimental. Această metodă implică realizarea
unui plan de încercări succesive pentru toate posibilitățile de rezolvare. Are un pronunțat
caracter științific, având la bază fapte certe. Necesită însă investigații paralele și deci se
poate aplic a la fenomene cu complexitate redusă.
Instruirea prin căutare de soluții noi vizează rezolvarea de probleme practice prin
formularea unor soluții care încorporează elemente creative noi pentru momentul instruirii.
Instruirea prin experimentare are ca scop inițierea elevilor în aplicarea metodei
experimentale. În acest caz elevii concep și efectuează observații, verificări, măsurători
pentru raporturile cauză -efect.
Elementele caracteristice acestei metode sunt:
– formularea unei ipoteze de cercetare;
– desfăș urarea unui plan experimental;
– compararea rezultatelor cu ipoteze.
Avantajele metodelor de explorare directă sunt:
– asigură însușirea unei metodologii de descoperire a cerințelor prin investigație
științifică individuală;
– dezvoltă spiritul de observaț ie, gândire, logică, creativitate;
– formează spiritul analitic (deprinderea de a analiza cu ușurință situații diferite);
– asigură posibilitatea ca elevul să surprindă legăturile cauzale dintre fenomene;
– solicită elevii pentru atitudini active, îmbin ând gândirea cu activități motrice;
– favorizează gândirea, diminuând tendința de memorare;
– sporește motivația și crește încrederea în forțele proprii;
– asigură remanența cunoștințelor, ușurează transferul lor ulterior;
75 Grafuri neorientate -optimizarea procesului de predare
– deschide posibilitatea participării active la educația permanentă.
Dezavantajul metodei este timpul îndelungat necesar rezolvării problemei,
comparativ cu celelalte metode de învățământ.
3.7 INSTRUIREA ASISTATĂ DE CALCULATOR
[28]În anii 1950, B.F.Skinner și Norman Crowder, teoreticieni americani, au emis idei
despre instruirea programată, aceștia fiind considerați pionierii modernelor tehnici de
instruire cu ajutorul calculatorului.
Principiile instruirii programate au fost aplicate într -o metodă de instruire numită
sistem de învățare personalizată.
Aceasta este o metodă de instruire, în care elevul învață în ritm propriu, materialul
educațional este structurat în secvențe mici de studiu, urmate de chestionare, instruitul și
instructorul put ând să observe imediat evoluția p rocesului de instruire.
Folosirea calculatorului în procesul de învățăm ânt se dovedește a fi o necesitate în
condițiile dezvoltării în ritm accelerat a tehnologiei informației. Pentru noile generații de
elevi și studenți, a devenit o cerință conceptul de a sistare a procesului de învățăm ânt cu
calculatorul, în condițiile avalanșei de informații multimedia.
Conceptul de asistare a procesului de învățăm ânt cu calculatorul include :
Predarea unor lecții de comunicare de cunoștințe ;
Aplicarea, consolidarea, sistematizarea noilor cunoștințe;
Verificarea automată a unei lecții sau a un ui grup de lecții.
Numită și « inovația tehnologică cea mai importantă a pedagogiei moderne », instruirea
asistată de calculator – IAC – contribuie la eficiența instruirii, este u n rezultat al
introducerii treptate a informatizării în învățăm ânt.
Calculatorul poate fi utilizat în procesul de predare –învățare de către profesor și elev în
scopul intermedierii activității de predare interumană ce are loc între cei doi poli
educaționa li : profesor și elevi.
«Mișcarea pedagogică de învățăm ânt programat a fost inaugurată de B.F. Skinner ca
fiind o aplicare a principiilor cunoscute ale instruirii, care înseamnă organizarea condițiilor
de învățare prin m ânuirea balanței, recompensei și pen alizării, în alegera răspunsului
corect. Simplificat putem spune că în secvența de învățare prin instruire programată apare
în evidență succesiunea : stimul – răspuns – confirmare».
Învătăm ântul programat permite două modalități de programare pedagogică :
76 Grafuri neorientate -optimizarea procesului de predare
1. Programare liniară (tip Skinner)
2. Programarea ramificată (tip Crowder)
În "Dicționarul de pedagogie contemporană" se regăsesc următoarele principii, ce stau la
baza instruirii programate:
Principiul participării active și independente a elevului;
Principiul pașilor mici;
Principiul progresului gradat;
Principiul întăririi imediate a răspunsului;
Principiul ritmului individual de studiu;
Principiul răspunsurilor corecte ;
Principiul repetiției.
Metoda instruirii programate dezvoltă propriile sale principii, valabile la nivel strategic în
orice variantă de organizare cibernetică a învă țării, într-o structură liniară sau ramificată:
Principiul pașilor mici – se referă la divizarea materiei în unități de conținut, care
asigură elevului șansa reușitei și a continu ității în activitatea de predare – învățare –
evaluare;
Principiul comportamentului activ – vizează dirijarea efortului elevului în direcția
selecționării, înțelegerii și aplicării informației necesare pentru elaborarea unui
răspuns corect;
Principiul eval uării imediate a răspunsului – înseamnă întărirea pozitivă sau
negativă a comportamentului elevului în funcție de reușita sau nereușita în
îndeplinirea sarcinii de învățare corespunzătoare fiecărui «pas».
După constituirea ciberneticii ca știință au fost r ealizate numeroase mașini de învățat și au
fost puse bazele teoretice ale instruirii programate; printre acestea se remarcă lucrările lui
B.F.Skinner, care au inițiat și au fundamentat instruirea programată cu programe liniare și
ale lui N.A.Crowder, inițiatorul programelor ramificate.
Programarea ramificată – varianta N.A.Crowder – "solicită un efort intelectual mai mare"
necesar elevului pentru "recunoașterea răspunsului corect din cîteva răspunsuri date, pe
baza testului alegerii repetate" (Okon,Vicenty, 1974).
77 Grafuri neorientate -optimizarea procesului de predare
Acest tip de programare nu urmărește numai preînt âmpinarea gre șelilor – ca în cazul
variantei liniare – ci tratarea acestora în diferite modalități de întărire negativă, care
reorientează activitatea elevului în direcția recuperării, reselecționării , reinterpretării,
reaplicării informației necesare pentru parcurgerea "pasului" respectiv.
Secvența de instruire, proiectată în cazul instruirii ramificate are următoarea structură de
organizare:
a. Informarea elevului;
b. Prezentarea sarcinii didactice;
c. Rezervarea spațiului și timpului pentru alegerea răspunsului;
d. Întărirea pozitivă, în cazul răspunsului corect, care asigură trecerea la informația
necesară pentru parcurgerea secvenței următoare/"pasului" următor, sau întărirea negativă,
în cazul alegerii răspunsului incorect, care orientează elevul spre o "programă secundară",
obligatorie pentru corectarea răspunsului, după care urmează trecerea la informația
necesară pentru parcurgerea secvenței următoare , "pasului" următor;
e. Confirmarea răspun sului (corect sau incorect în varianta de întărire pozitivă, respectiv în
cea de întărire negativă);
f. Informarea din secvența următoare (Țîrcovnicu,1975).
Reușita acestei metode, în varianta sa liniară, ramificată sau combinată, depinde de
calitatea mijloacelor didactice necesare pentru proiectarea și realizarea activității de
predare – învățare – evaluare în spiritul principiilor cibernetice și pedagogice evocate
anterior: manualele programate și mașinile de instruire. În toate situațiile, însă, rolul
profesorului rămîne determinant.
Avantajele și dezavantajele instruirii asistate de calculator.
Această metodă depinde nu numai de calitatea calculatorului, ci și de condiția pedagogică
asumată la nivelul programelor elaborate special pentru :
Conștienti zarea valorii interactive a informației alese ;
Sistematizarea rapidă a unui volum mare de informații ;
Difuzarea eficientă a unor informații esențiale solicitate de un număr ridicat de
participanți la actul didactic;
Individualizarea reală și completă a a ctului învățării, adaptabilă la ritmul fiecărui
elev prin asistență pedagogică imediată, realizată/realizabilă de/prin calculator;
78 Grafuri neorientate -optimizarea procesului de predare
Stimularea capacității profesorului de "a deveni un adevărat educator : ghid și
animator, evaluator și îndeosebi formator preocupat de cul tivarea atitudinilor
superioare” (Văideanu, 1988).
Valoarea instruirii programate constă în faptul că, prin organizarea procesului de
învățare, principiile didactice (al însușirii conștiente și active, al sistematizării și
continuității, al accesibilității și însușirii temeinice a cunoștințelor) acționează concomitent
și în fiecare moment al activității elevului cu programa, stimul ând formarea și dezvoltarea
capacităților intelectuale, precum și deprinderi de muncă independentă. De asemenea, se
reduc în mod simțitor timpul necesar însușirii cunoștințelor și redundanța inerentă
procesului de transmisiune a informațiilor de la profesor sau de la manual , la elev.
În instruirea asistată de calculator rolul esențial revine educatorului. Pe l ângă o serie de
avantaje, această modernă și eficientă formă de învățare are și anumite limite :
Individualizarea excesivă a învățării duce la negarea dialogului elev -profesor și la
izolarea actului de învățare în contextul său psihosocial ;
Segmentează și atomi zează prea mult materialul de învățat;
Duce prea mult la ,,tutela re”, dirijând pas cu pas activitatea mentală a subiectului și,
prin aceasta, împiedic ându-l să-și dezvolte capacitățile creatoare.
Totodată, instruirea programată nu poate cuprinde întregul p roces instructiv -educativ și
nu poate constitui o metodă generală și universală în pedagogie, în primul r ând din cauză
că modelul cibernetic al procesului de învățăm ânt pe care se bazează îl reprezintă, ca orice
model, numai din anumite puncte de vedere și nu cuprinde toate reacțiile elevului la
perturbațiile interne și externe, dar și pentru că nu toate obiectele de învățăm ânt sau
disciplinele științifice pot fi programate, pentru că accentuează verbalismul (în scris) fără a
dezvolta suficient intuiția, pe ntru că elevul nu are imaginea conturată a obiectului în
ansamblu și pentru că, dificultățile fiind fragmentate, se limitează formarea unor motivații
superioare, spiritul critic și g ândirea independentă. De asemenea, instruirea programată
prezintă, datorit ă formalizării procesului de instruire, și pericolul formalismului și al
standardizării cunoștințelor.
Cu toate acestea, integrarea noilor tehnologii – dependente de capacitatea de asistență
pedagogică a calculatorului – în structura de acțiune specifică m etodei didactice conferă
activității elevului un caracter reactiv și proactiv, în raport cu informația vehiculată, cu
timpul real de învățare, cu valoarea formativă a cunoștințelor dob ândite.
79 Grafuri neorientate -optimizarea procesului de predare
Modalități de utilizare a calculatorului electronic în procesul de predare – învățare.
Calculatorul oferă posibilități reale de individualizare a instruirii. El nu este doar un mijloc
de transmitere a informației ci poate oferi programe de învățare adaptate conduitei și
cunoștințelor elevului.
Realizarea unei metodolog ii care să facă eficientă asistarea procesului de învățămâ nt cu
calculatorul a solicitat folosirea instrumentelor psihopedagogiei.
« Conceptul de asistare a procesului de învățăm ânt cu calculatorul include :
Predarea unor lecții de comunicare de noi cunoștințe ;
Aplicarea, consolidarea, sistematizarea noilor cunoștințe;
Verificarea automată a unei lecții sau a unui grup de lecții ;
Verificarea automată a unei discipline școlare sau a unei anumite programe
școlare.
Utilizarea calculatorului în procesu l de învățăm ânt devine din ce în ce mai importantă
(chiar indispensabilă) deoarece:
Are loc o informatizare a societății;
Mediile de instruire bazate pe informatică oferă un puternic potențial educativ ».
Calculatorul – instrument didactic
Din acest punct de vedere remarcăm mai multe modalități de apariție a calculatorului în
demersul didactic:
Utilizarea calculatorului pentru tehnoredactarea computerizată a documentelor
școlare cum ar fi cele care reprezintă rezultate ale proiectării didactice la nivel
micro, adică planificări, proiecte de unități de învățare, proiecte de lecție, c ât și a
unor documente de evidență școlară cum ar fi cele legate de prezența la anumite
activități didactice sau notarea evoluției elevilor la activitățile de verificare și
evalua re a cunoștințelor ;
Utilizarea calculatorului ca mijloc de predare în cadrul lecțiilor de comunicare de
noi cunoștințe, de recapitulare sau a prelegerilor în care calculatorul poate
reprezenta suport al unor sinteze, imagini, figuri ce pot fi proiectate î n scopul
transmiterii de cunoștințe. În felul acesta elevii au posibilitatea să vizioneze o
80 Grafuri neorientate -optimizarea procesului de predare
expunere concretă și clară a teoremelor, pot să aibă pe ecran imaginea unor
fenomene sau procese simulate pe calculator ;
Realizarea unor calcule numerice, mai mult sau mai puțin complicate, în scopul
formării deprinderilor de calcul sau al eliberării de etapa calculatorie în rezolvarea
unor probleme, prelucrarea unor date ;
Realizarea unor bănci de date, adică stocarea de informații dintr -un domeniu
oarecare într -o modalitate care să permită ulterior regăsirea informațiilor după
anumite criterii ;
Învățarea unui limbaj de programare ;
Realizarea unor laboratoare asistate de calculator .
ABILITĂȚI NECESARE ÎN SECOLUL XXI
Responsabilitate și capacitate de adaptare : exersarea responsabilității și
flexibilității personale în contexte variate: personal, î n comunitate, la locul de
muncă;
Comunicare: înțelegerea, crearea unei comunicări efective, orale, scrise sau
multimedia în contexte variate ;
Creativitate și curiozitat e intelectuală : formularea, implementarea și comunicarea
noilor idei; deschidere spre perspective noi și variate ;
Gândire critică și gândire sistemică : exersarea raționamentului pentru înțelegere și
alegere complexă; înțelegerea i nterconexiunilor dintre si steme;
Informare și abilități media : accesarea , integrarea, analizarea, evaluarea și crearea
informațiilor dintr -o multitudine de forme și din media;
Abilități interpersonale și de colaborare : adaptarea la roluri și responsabilități
variate; munca productivă în echipă; exersarea empatiei; res pectarea diverselor
perspective;
Autonomie în învățare : automonitorizarea nevoilor proprii de înțelegere și învățare;
localizarea resurselor corespunzătoare; transferul de cunoștințe de la un domeniu, la
altul;
Responsabilizare socială : acțiune responsabilă în concordanță cu interesele
comunității; demonstrarea unui comportament etic în contexte variate: personal, în
comunitate, la locul de muncă.
3.8 EVALUAREA
3.8.1 Conceptul de evaluare
81 Grafuri neorientate -optimizarea procesului de predare
[18]. Evaluarea este u n proces complex etapizat , desfășurat în timp, care asigură
evidențierea cuantumului de cunoștințe dobândite de elevi, valoarea și eficiența acestora la
un moment dat. Scopul ei este măsurarea și aprecierea rezultatelor obținute de elevi în
raport cu obiectivele proiectate, spre a interveni în timp util pentru ameliorarea activității
didactice.
3.8.2 Forme de evaluare
Forme de evaluare determinate de procedeele de efectuare :
a) verificare orală
Reprezintă metoda cea mai utilizată la clasă și reprezintă o “ formă de conversare pri n
care profesorul urmărește volumul și calitatea cunoștințelor, priceperilor și deprinderilor
elevilor și capacitatea de a opera cu ele “.(I. Nicola)
b) verificarea prin lucrări scrise
Profesorul poate verifica cunoștințele întregii clase prin:
– lucrări de control de 10 -15 minute (extemporale);
– lucrări de control la sfârșitul capitolului;
– lucrări scrise semestriale (teze);
– teste de evaluare;
Probele scrise sunt practicate și u neori chiar preferate, datorită unora dintre avantajele lor
imposibil de ignorat, în condițiile în care se dorește eficientizarea procesului de instruire și
creșterea gradului de obiectivitate în apreciere. Ioan Cerghit, consideră că probele scrise se
datorează unor “considerente obiective (număr redus de ore la unele discipline, programă
și clase aglomerate) cât și unor considerente psihopedagogice, deoarece lucrările scrise
dau posibilitatea elevilor să lucreze în ritm propriu, relevând mai pregnant ca pacitatea
lor de organizare a cunoștințelor după un plan logic, expunere, disciplină în gândire,
deprindere de muncă, independență, putere de sinteză și de exprimare în scris etc ”. Un alt
avantaj al probelor scrise ar fi acela că au o valoare de obiectiv itate și imparțialitate mai
mare decât cele orale.
Dezavantaje
• oferă elevului o slabă retroinformare utilă;
• îngrădesc sever sfera cunoștințelor ce urmează a fi verificate;
• lipsește climatul psihologic și cel afectiv.
c) verificarea temelor pentru acasă
82 Grafuri neorientate -optimizarea procesului de predare
Verificarea temei se face la începutul lecției, profesorul controlând personal fiecare
elev sau prin sondaj. Tema se corectează cu ajutorul elevilor. Pentru a înlătura tendința de
copiere a elevilor se îmbină verificarea temei cu cea orală.
d) Veri ficarea prin lucrări practice
Oferă posibilitatea evaluării capacităților elevilor de a aplica cunoștințele în practică
precum și a gradului de stăpânire a priceperilor și a deprinderilor formate. Sunt cunoscute
multiple forme de realizare a verificărilor prin lucrări practice: experiențe de laborator,
lucrări experimentale, desene, schițe, grafice etc. Activitățile practice oferă elevului
posibilitatea de a -și dezvolta atât competențele generale (comunicare, analiză , sinteză), cât
și pe cele specific aplic ative (prelucrarea datelor, folosirea instrumentelor de lucru,
interpretarea rezultatelor).
Forme de optimizare a evaluării
Testul docimologic –instrument de evaluare
Testul docimologic reprezintă o modalitate de examinare care cuprinde un set de
probe sau întrebări cu ajutorul cărora se verifică și se evaluează nivelul asimilărilor
cunoștințelor și al capacităților de a opera cu ele, prin raportarea răspunsurilor la o scară
etalon de apreciere, elaborată ulterior. Testul este instrumentul de măsurare a cuno ștințelor,
deprinderilor, aptitudinilor, prin intermediul căr uia obținem informații necesare
fundamentării științifice a unor decizii. Principalele obiective ale utilizării testelor sunt:
prognoza, diagnoza și cercetarea. Testul de evaluare vizează cunoașterea fondului
formativ – informativ dobândit de elev în procesul de instruire -învățare. Elaborarea unui
test este o activitate complexă, redactarea itemilor făcându -se conform comportamentelor
asumate potrivit programei, grupate pe niveluri diferite .
Pentru realizarea evaluării unei anumite capacități se poate propune un număr diferit
de itemi.
Itemii subiectivi testează obiective ce vizează originalitatea, creativitatea, gândirea
divergentă și capacitatea de a generaliza (eseul, rezolvarea de probleme).
Itemii obiectivi sunt acele solicitări care au răspunsuri închise (alegere,
adevărat/fals, corect/incorect, da /nu). Ei verifică mai ales cunoștințele acumulate,
mai puțin abilitățile, capacitățile, deci învățările realizate la nivelul primelor clase
comportamentale ale obiectivelor.
Din categoria itemilor obiectivi fac parte următoarele tipuri de itemi:
a) itemi cu a legere duală,
83 Grafuri neorientate -optimizarea procesului de predare
b) itemi de asociere (de tip pereche),
c) itemi cu alegere multiplă.
Itemi semiobiectivi – se îndepărtează, într -o oarecare măsură, de la maxima
obiectivitate în corectare și notare asigurate de itemii obiectivi. Acești itemi,
solicită din partea e levului „producerea” unui răspuns, de obicei scurt, care va
permite din partea profesorului evaluator examinarea unei judecăți de valoare
privind corectitudinea răspunsului oferit.
Din această categorie fac parte:
a) itemi cu răspuns scurt,
b) itemi de completa re,
c) cu răspuns stucturat.
Forme de evaluare determinate de perioada de studiu
a) evaluarea inițială (parțială) – permite diagnosticarea nivelului de pregătire al elevilor
la începutul anului , pentru a cunoaște de unde pornește și ce mai trebuie perfecționat.
b) evaluarea curentă (continuă) – asigură o pregătire sistematică și continuă,
identificându -se pe parcursul actului de învățare dificultățile întâmpinate de către elevi
(acest tip de evaluare nu se anunță din timp, deoarece datoria elevului este să învețe zilnic).
c) evaluarea finală (cumulativă sau sumativă) – constă în verificarea și aprecierea
periodică încheiată prin control final, asupra rezultatelor actului pedagogic. Se efectuea ză
la sfârșitul semestrului sau a anului școlar pentru o apreciere globală a rezultatelor
învățării, a valorii programului, a metodelor de predare -învățare.
3.8.3 Metode alternative de evaluare
[18]. Cele mai importante finalități ale evaluării procesului instructiv -educativ, în
ultimul timp, se concretizează în :
cunoștințe și capacitate;
atitudini (practice, sociale, științifice);
capacitatea de a face aprecieri de valoare (opinii, adaptări atitudinale și
comportamentale , etc);
Pornind de la această rea litate, strategiile moderne de evaluare caută să accentueze acea
dimensiune a acțiunii evaluative care să ofere elevilor suficiente și variate posibilități de a
demonstra ceea ce știu dar, mai ales, ceea ce pot să facă.
Metodele moderne de evaluare sunt :
investigația;
84 Grafuri neorientate -optimizarea procesului de predare
chestionarul;
proiectul ( miniproiectul );
portofoliul;
tema pentru acasă;
tema de lucru în clasă;
grile de evaluare;
scale de evaluare;
autoevaluarea.
3.9 TESTUL DOCIMOLOGIC
[17]Testul docimologic este una din tehnicile cele mai eficiente de evaluare. El
constituie un set de probe sau întrebări cu ajutorul cărora se evaluează nivelul cunoștințelor
și al competențelor de a opera cu ele prin raportarea răspunsurilor la o scară de apreciere
etalon, ela borată în prealabil. Probele sau întrebările din test se numesc itemi .
Elaborarea unui test pedagogic/docimologic presupune parcurgerea mai multor etape:
Stabilirea scopului probei (diagnostic sau prognostic) determină structura și
conținutul acesteia.
Selectarea conținuturilor și a obiectivelor corespunzătoare care vor fi vizate prin
intermediul testului este sintetizată într -un tabel/matrice de specificații.
Stabilirea unei grile de corectare care să includă răspunsurile corecte pentru fiecare
item .
Elaborarea baremului de corectare sau a modalității de calculare a scorurilor.
Pretestarea are în vedere verificarea calităților globale ale testului – obiectivitate,
aplicabilitate, fidelitate și validitate, precum și a calităților fiecărui item –
dificulta te și putere de discriminare.
În ultima etapă de construire a unui test – revizuirea acestuia o parte dintre itemi
sunt fie reformulați, fie eliminați în funcție de rezultatele analizei privind
caracteristicile prezentate anterior .
Din perspectiva evaluări i școlare prin teste docimologice, itemul poate fi definit ca
unitate de măsurare care include un stimul și o formă prescriptivă de răspuns . Itemii
trebuie să respecte aceleași exigențe de proiectare, administrare și scorare, indiferent de
natura testului în care sunt incluși.
Tipologia itemilor include: itemi obiectivi, semiobiectivi și subiectivi.
1. Itemii obiectivi. Exigențe de proiectare.
85 Grafuri neorientate -optimizarea procesului de predare
Itemii obiectivi presupun întotdeauna alegerea răspunsului/răspunsurilor corecte dintr -o
listă anterior elaborată p usă la dispoziție celui examinat, fiind denumiți și itemi cu răspuns
dat. Răspunsul corect este identic pentru toți cei examinați, iar evaluatorii corectează acești
itemi strict identic.
1.1. Itemii cu răspuns dual
Itemii cu răspuns dual se elaborează sub forma unor enunțuri complete, pe care
examinatul trebuie să le accepte sau să le respingă. Răspunsurile corecte sunt marcate cu
ajutorul unor ințiale ( A – F, dacă răspunsul este considerat adevărat, respectiv fals;
menționăm că se poate introduce și varia nta O reprezentând faptul că enunțul este o opinie,
nefiind nici adevărat, nici fals) sau al cuvintelor DA – NU, plasate în fața fiecărui enunț sau
după acesta. Există și alternativa ca examinatul să plaseze (nu să bifeze) aprecierile de tip A
– F, Da – Nu, în relație cu itemii corespunzători. În general, itemii cu răspuns dual conduc
la evaluarea unor comportamente corespunzătoare nivelelor taxonomice inferioare
(cunoașterea și înțelegerea), însă pot fi utilizați în elaborarea testelor pentru majoritatea
disciplinelor de învățământ. Teoretic, există 50% „șanse” ca elevul să ghiceasă răspunsul
corect.
1.2. Itemii cu răspuns de tip alegere multiplă
Itemii cu răspuns de tip alegere multiplă pot servi atât la măsurarea unor
comportamente specifice nivelelor taxonomice inferioare, cât și a comportamentelor
asocite cu analiza și evaluarea. Acest tip de item este alcătuit din două elemente:
tulpina, problema, sau premisa, formulată printr -o întrebare directă sau printr -un
enunț incomplet;
o serie de a lternative de răspunsuri propuse examinatului, din care una este corectă
sau cea mai bună, iar celelalte au rolul de distractori, constituind obstacole ce
trebuie depășite de către examinați în alegerea răspunsului corect .
Având în vedere natura răspunsu lui care se poate solicita examinatului, itemii cu
răspuns de tip alegere multiplă pot fi proiectați în două variante:
Itemii cu răspuns corect presupun alegerea răspunsului corect care completează un
enunț, dintr -o listă de alternativă pusă la dispoziție elevului. Se aseamănă cu itemii
semiobiectivi tip răspuns scurt, singura diferență constând în faptul că elevul alege
răspunsul, nu îl elaborează el însuși.
Itemii cu răspunsul cel mai bun sunt preferați pentru evaluarea pe nivele
taxonomice mai înalte. Ma i multe dintre răspunsurile pe care elevul trebuie să le
86 Grafuri neorientate -optimizarea procesului de predare
analizeze sunt acceptabile, dar în măsură diferită, elevul trebuind să indice cea mai
potrivită variantă.
1.3. Itemii de asociere
Itemii de asociere sau tip pereche solicită elevului să stabilească c orespondența între
două seturi de concepte, date, informații etc., plasate de regulă în două coloane diferite: o
primă coloană este destinată premiselor sau stimulilor, iar în a doua coloană sunt incluse
răspunsurile. Premisele și răspunsurile pot fi perec hi de evenimente și date, termeni și
definiții, reguli și exemple, simboluri și concepte, autori și tiluri de cărți, plante, animale și
clasificări, principii și aplicații, cauze și efecte, afirmații teoretice și experimente etc.
2. Itemii semiobiectivi
Itemii de tip semiobiectivi sunt incluși în unele clasificări alături de cei subiectivi
într-o categorie mai largă de itemi – cu răspunsuri elaborate de către cel examinat . Dat
fiind faptul că răspunsurile sunt construite de către elev, scorarea/notarea a cestora
respectă alte exigențe decât itemii obiectivi, antrenând calitățile de evaluator ale
corectorilor. Se pot delimita trei categorii de itemi semiobiectivi: itemii de tip răspuns
scurt, cei de tip completare și cei de tip întrebări structurate.
2.1. I temii tip răspuns scurt si de completare
Itemii cu răspuns scurt și cei de completare sunt similari; proiectarea, administrarea
și notarea răspunsurilor se supun acelorași exigențe. În cazul itemilor cu răspuns scurt,
acesta se solicită printr -o întrebare directă sau printr -un enunț direct, în timp ce itemii de
completare constau în enunțuri lacunare, incomplete, răspunsul costând din completarea
spațiilor libere. Cele două tipuri de itemi permit evaluarea de rezultate diverse ale activității
de învățare, d ar la nivele taxonomice inferioare: cunoașterea de terminologii, de reguli, de
metode și procedee de acțiune, interpretarea simplă a unor date, abilitatea de a reda
conținuturi prezentate prin desene, hărți, diagrame etc., capacitatea de a utiliza simbolur i
matematice sau utilizate în științele naturii, capacitatea de rezolvare a unor probleme
simple din științele exacte .
Reguli de proiectare a itemilor tip răspuns scurt de completare:
Sarcina de rezolvat trebuie formulată concis, dar suficient de explicit pentru a nu
lăsa loc de interpretare.
Itemii nu trebuie să includă prea multe spații albe, pentru că se îngreunează
procesul de înțelegere a sarcinii.
Nu se recomandă decontextualizarea definițiilor, deoarece s -ar putea ajunge la
confuzii în formularea ră spunsului.
87 Grafuri neorientate -optimizarea procesului de predare
Se recomandă ca spațiile albe să fie egale ca lungime, chiar dacă dimensiunea
răspunsurilor este diferită, pentru a nu determina fie răspunsuri prea scurte, fie
răspunsuri de tip eseu.
Este preferabil ca spațiile albe să fie plasate la finalul e nunțului.
2.2. Întrebările structurate
Întrebările structurate sunt definite ca „sarcini formate din mai multe subîntrebări, de
tip obiectiv și semiobiectiv, legate între ele printr -un element comun", menite să acopere
spațiul liber aflat între itemii obie ctivi și cei subiectivi . Un asemenea item este alcătuit
dintr -un material -stimul (care poate fi reprezentat dintr -un desen, un text, un tabel etc.) și o
suită de subîntrebări care sunt conectate prin conținut cu materialul -stimulul.
3. Itemii subiectivi.
Itemii de tip subiectiv sunt prezentați în maniere diverse în literatura pedagogică,
diferențele putând fi identificate chiar și la nivelul denumirii lor (itemi cu răspuns elaborat
de către elev, itemi nonobiectivi, itemi cu răspuns deschis ). Clasificare:
Itemi de tip rezolvare de probleme;
Itemi de tip eseu, cu patru variante rezultând din combinarea criteriului de
clasificare dimensiune (restrâns și extins) și cu cel de nivel de structurare a sarcinii
(eseu structurat și eseu liber).
Deși elaborarea s chemelor de notare este evident mai dificilă decât în cazul itemilor
obiectivi și semiobiectivi și antrenează toate resursele de obiectivitate ale evaluatorului,
itemii subiectivi nu pot fi evitați mai ales în evaluările sumative de tipul examenelor
națion ale, date fiind avantejele lor în evaluarea competențelor complexe.
3.1. Itemi de tip rezolvare de probleme .
Itemii de tip rezolvare de probleme presupun prezentarea unor situații -problemă,
nefamiliare, inedite pentru elev, care nu dispun de o soluție pr edeterminată, precum și
antrenarea acestuia pentru identificarea unor soluții prin parcurgerea unor etape:
identificarea problemei, culegerea și selectarea datelor de bază (relevante), formularea și
validarea unor ipoteze, identificarea metodei de rezolvar e, propunerea unei soluții,
evaluarea soluției, formularea concluziei asupra rezolvării realizate . Aceste etape de
soluționare a situațiilor -problemă nu pot fi strict parcurse în toate ipostazele de prezentare a
acestei categorii de itemi, constituind doa r o etapizare orientativă a procesului rezolutiv.
Situațiile problemă pot fi simple, „închise”, atunci când elevului îi sunt puse la dispoziție
toate datele necesare rezolvării, scopul este precizat clar, iar succesiunea cerințelor
sugerează și etapele de rezolvare; și situații problemă „deschise”, atunci când elevul
88 Grafuri neorientate -optimizarea procesului de predare
dispune doar de datele cele mai importante, procesul de rezolvare este doar sugerat, iar
demersul propriu -zis trebuie ales de către cel examinat.
3.2. Itemii de tip eseu
Itemii de tip eseu pres upun elaborarea de către elev a unor răspunsuri complexe, acesta
având suficientă libertate în jalonarea liniilor de explicare, argumentare etc., având
avantajul de a surprinde comportamente plasabile la nivele taxonomice înalte . Deși se
vehiculează patru categorii de itemi de tip eseu, clasificate după două criterii distincte – cu
răspuns restrâns și cu răspuns extins, după dimensiunea așteptată a răspunsului; eseu
structurat și eseu liber, după natura cerințelor specificate în cadrul itemului, ele sunt
coextensive în sensul că eseul cu răspuns restrâns se apropie de eseul structurat, iar cel cu
răspuns extins se apropie de eseul liber.
3.2.1. Itemii tip eseu cu răspuns restrâns
Itemii tip eseu cu răspuns restrâns (eseu scurt, minieseu) implică respectarea de către
elev a unor cerințe în elaborarea răspunsului, care pot viza forma și/ sau conținutul
acestuia. Exigențele de formă se pot referi la numărul de pagini, linii sau pragrafe, în timp
ce reperele privind conținutul pot face trimitere la anumite eleme nte de conținut care
trebuie să se regăsească în răspuns.
3.2.2. Itemii eseu cu răspuns extins
Itemii eseu cu răspuns extins solicită elevului să elaboreze un răspuns amplu,
valoricând toate achizițiile anterioare, dar introducând și elemente de originalit ate.
3.2.3. Itemii de tip eseu structurat
Itemii de tip eseu structurat includ în enunțul lor cerințe, repere explicite care să
orienteze elevul într -o anumită manieră în organizarea, argumentarea ideilor expuse. Acest
tip de itemi trebuie întotdeauna completat cu o schemă de corectare și de notare care să
indice punctajele aferente elementelor de reper, care să fie aduse la cunoștință elevului într –
o formă sau alta.
3.2.4. Itemii de tip eseu liber
Itemii de tip eseu liber prezintă în manieră explicită un enunț, fără a include precizări
explicite cu privire la maniera de organizare a răspunsului și fără a aduce precizări cu
privire la evaluarea analitică a acestuia.
89 Grafuri neorientate -optimizarea procesului de predare
CAPITOLUL I V
PROIECTAREA DIDACTICĂ
4.1 PLANUL UNITĂȚII DE ÎNVĂȚARE
Conexitate, componente conexe -folosind metoda conversației și învățarea prin
descoperire .
Autor unitate : Prof. Gheorghiu Carmen Adina
Județ : Galați
Denumire școală : Colegiul Național „Spiru Haret”
Localitate : Tecuci
Prezentare generală a unității de învă țare:
Titlul planului unității de învățare:
”Conexitate, componente conexe în grafuri neorientate”
Unitatea presupune studiul – ca element de conținut – a următoarelor subunități:
– Conexitate în grafuri neorientate;
– Descompunerea grafurilor neorientate în componente conexe.
Aria tematică : informatică
Tipul lecției : dobândire de noi cunoștințe
Locul de desfășurare : laboratorul de informatică
Clasa : a XI-a A matematică -informatică, neintensiv
Timp necesar : 50 minute
Competențe generale :
Identificarea datelor care intervin într -o problemă și aplicarea algoritmilor
fundamentali de prelucrare a acestora;
Elaborarea algoritmilor de rezolvare a problemelor;
Implementarea algoritmilor într -un limbaj de programare.
Competențe specifice :
Descrierea operațiilor specifice structurii de coadă și elaborarea unor
programe care să implementeze aceste operații;
Aplicarea algoritmului B.F. pentru verificarea conexității unui graf
neorientat;
Identificarea componentelor conexe.
90 Grafuri neorientate -optimizarea procesului de predare
Obiective operaționale și rezultate aștept ate:
o Să utilizeze terminologia specifică grafurilor neorientate;
o Să utilizeze algoritmi de implementare a grafurilor neorientate;
o Să rezolve aplicațiile propuse prin utilizarea cunoștințelor dobândite;
o Să descrie în limbajul de programare studiat algoritmul B.F.;
o Să definească noțiunea de graf conex;
o Să definească noțiunea de componentă conexă;
o Să implementeze în limbajul de programare studiat verificarea proprietății
de graf conex și descompunerea în componente conexe.
Aptitudini obligatorii :
Cunoștințe generale pe ntru ca elevul să poată începe studiul unității de învățare:
Elevii și -au însușit noțiunile fundamentale:
a. definiție, incidență, adiacență, grad;
b. metode de reprezentare: matricea de adiacență,
vectorul de muchii, listele de adiacență;
c. graf parțial, subgraf, graf complet;
Elevii utilizează și operează corect cu algoritmul B.F.;
Elevii utilizează corect calculatorul și aplicația C++.
Strategii didactice :
Principii didactice :
– Pricipiul participării și învățării active;
– Principiul asigurării progresului gradat al performanței;
– Principiul conexiunii inverse.
Metode de învățământ :
– Metode de comunicare orală: expunere, conversație;
– Metode de acțiune: exercițiul, învățarea prin descoperire, rezolvarea
de probleme;
– Instruirea asistată de calculator: utilizarea aplicației C++ în predare.
Procedee de instruire :
– Conversația de verificare a cunoștințelor;
– Conversația euristică, cu scopul de a redescoperi cunoștințele;
– Învățarea prin descoperire , prin rezolvarea de probleme;
– Conversația de con solidare în etapa de fixare a cunoștințelor.
91 Grafuri neorientate -optimizarea procesului de predare
Forme de organizare :
– Frontală;
– Individuală.
Forme de dirijare a învățării : dirijată de profesor sau independentă.
Resurse materiale :
– Material bibliografic: Tudor Sorin, Manual pentru clasa a XI -a,
Editura L&S, INFOMAT, București, 2001;
– Fișe de lucru;
– Calculator .
Metode de evaluare :
– Evaluare inițială: întrebări orale și exerciții;
– Evaluare finală: fișe de lucru.
Desfășurarea lecției :
Moment organizatoric :
Pregătirea lecției:
– Întocmirea proiectului didactic;
– Pregătirea setului de întrebări;
– Pregătirea setului de aplicații;
– Pregătirea temei.
Organizarea și pregătirea clasei: 2 min
o verificarea frecvenței.
o Captarea atenției clasei:
– Anunțarea subiectului pentru tema propusă;
– Anunțarea obiectivelor urmărite;
– Anunțarea modului de desfășurare a activității.
Reactualizarea cunoștințelor : 10 min
Se reactualizează cunoștințele cu ajutorul fișei 1. Evaluarea în etapa de
reactualizare se realizează frontal.
FIȘA 1
1. Ce este coada și ce operații putem efectua în acea sta?
2. Se consideră coada cu elementele 1, 2, 3 introduse în această ordine și operațiile AD(x), EL de
adăugare a unui element x în coadă și eliminare. Enumerați elementele din coadă în urma efectuării
operațiilor: AD(4), EL, AD(5), EL, EL.
3. Fie graful neorientat din figură:
92 Grafuri neorientate -optimizarea procesului de predare
a) specificați secvența de noduri în urma parcurgerii în lățime, considerându -se nod de start 2;
b) parcurgeți în lățime graful, alegând nod de start 6. Ce observați?
4. Fie coada cu elementele a, b, c, d introduse în această ordine. Specificați forma cozii după fiecare
din operațiile: AD(e), AD(f), AD(g), EL, EL.
5. În algoritmul B.F., ce rol are vectorul VIZ ?
RĂSPUNSURI AȘTEPTATE
1.Coada este reprezentată printr -un vector, care funcționează pe principiul „primul intrat – primul
ieșit” (FIFO). Aceasta deține două capete, unul de intrare a datelor, celălalt de extragere. Operațiile
ce se pot efectua sunt de adăugare a informațiilor pe la un capăt, respectiv ex tragerea acestora pe la
capătul opus.
2.Elementele rămase sunt: 4 și 5.
3.a) Secvența obținută este: 2, 1, 3, 4, 5
b) Secvența obținută este: 6
Observăm că nu există lanț de legătură între nodul 6 și celelalte noduri din graf.
4.
AD(e)
AD(f)
AD(g)
EL
EL
5.Vectorul VIZ are rolul de reține în VIZ[i] valorile 1 sau 0 după cum nodul i a fost sau nu vizitat.
93 Grafuri neorientate -optimizarea procesului de predare
Comunicarea noilor cunoștințe : 20 min
VERIFICAREA CONEXITĂȚII UNUI GRAF
Definiție :
Un graf G(X,U) este conex, dacă oricare ar fi două vârfuri ale sale există un lanț
care le leagă.
Fie graful G(X,U) din figura de mai jos:
Aplicarea algoritmului de parcurgere în lățime B.F. pe graful de mai sus,
furnizează, indiferent de nodul ales ca punct de start, un șir de valori ce conține toate
nodurile grafului.
Ordinea vizitării vârfurilor în parcurgerea B.F. cu nod de start 1 este 1,2,5,6,3,4,7.
Șirurile obținute sunt de fapt lanțu ri, ce unesc două noduri, trecând prin (n -2)
noduri intermediare. Rezultă că luând oricare două noduri, ele pot fi unite printr -un lanț,
ceea ce arată că graful din figură este conex.
Verificarea proprietății de graf conex se face simplu prin aplicarea al goritmului de
parcurgere în lățime B.F.; ulterior, dacă au fost vizitate toate nodurile (echivalent cu
depunerea în coadă a tuturor nodurilor), graful are proprietatea de conex.
DESCOMPUNEREA ÎN COMPONENTE CONEXE A UNUI GRAF NEORIENTAT
Definiție :
Se numește componentă conexă a grafului G =(X,U), un subgraf G1 =(X1,U1)
a lui G, conex, cu proprietatea că NU există LANȚ care să lege un nod din X1 cu unul
din X -X1.
94 Grafuri neorientate -optimizarea procesului de predare
Dacă se consideră nodul 1 ca punct de start la aplicarea algoritmului B.F. pe graful
din figura de mai sus, atunci:
– vecinii lui 1 sunt 2 și 4
– vecinul nevizitat a l lui 2 este 3
– vecinul nevizitat a l lui 4 este 5
Ordinea vizitării nodurilor este 1,2,4,3,5 iar nodurile nevizitate sunt: 6,7,8,9.
Similar, dacă se consideră exemplul nodului 6 ca punct de start , se pot vizita numai
nodurile 6,7,8,9, rămânând nevizitate următoarele noduri: 1,2,3,4,5.
Prin urmare, la o parcurgere nu se pot vizita toate nodurile , consecința fiind
clară : nu oricare două noduri pot fi legate printr -un traseu de tip lanț , rezultând că
graful nu este conex, acesta deținând componente conexe.
Din d efinițiile și exemplele anterioare , se desprind următoarele concluzii care sunt
foarte importante:
-Dacă numărul componentelor conexe dintr -un graf este mai mare decât 1, atunci
graful nu este con ex.
-Un graf conex are o singură compon entă conexă, care cuprinde toate nodurile sale.
– Un nod izolat reprezintă o componentă conexă.
Dirijarea învățării pentru obținerea performanței : 15 min
Se realizează cu ajutorul fișei 2.
2
1 3
5
4 6 7
9 8
95 Grafuri neorientate -optimizarea procesului de predare
FIȘA 2
1.Fie graful din figura alăturată:
a.verificați dacă graful este conex;
b.câte componente conexe are graful?
c.câte muchii minim trebuie adăugate astfel încât graful să devină conex?
d.câte componente conexe minim se pot obține în graful din figură, prin redistribuirea muchiilor?
2.Constru iți în C++ programul de verificare a conexității unui graf neorientat G(X,U), dat prin
numărul ”n” de noduri și matricea de adiacență ”a”.
RĂSPUNSURI AȘTEPTATE
1.
a.Ordinea nodurilor la aplicarea algoritmului B.F. cu nod de start 3 este următoarea: 3, 2, 4, 1. Nu
au fost introduse în coadă toate nodurile grafului, deci acesta NU este conex.
b.Graful are două componente conexe: CC1: 1, 2, 3, 4
CC2: 5
c.Numărul minim de muchii ce pot fi adăugate într-un graf neconex astfel încât acesta să devină
conex, este de (x -1), unde x=numărul de componente conexe ale grafului. Deci sunt necesare
minim o muchie.
d.Prin redistr ibuire, se poate obține o componentă conexă, chiar graful, acesta devenind conex.
2.
#include<iostream.h>
#include<conio.h>
int viz[30],n,k,u,v,p,a[20][20],c[30],pstart;
void introducere()
{
96 Grafuri neorientate -optimizarea procesului de predare
int i,j;
cout<<"Dati numarul de varfuri n=";
cin>>n;
for(i=1;i <=n-1;i++)
for(j=i+1;j<=n;j++)
{
cout<<"a["<<i<<"]["<<j<<"]'=";
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
int bf()
{
int i,viz[10],c[10],pi,ps;
cout<<"Nodul de start: ";
cin>>pstart;
for(i=1;i<=n;i++)
viz[i]=0;
pi=1;
ps=1;
viz[pstart]=1;
c[pi]=pstart;
while(pi>=ps)
{
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
return(pi==n);
}
void main()
{
clrscr();
introducere();
97 Grafuri neorientate -optimizarea procesului de predare
if(bf())
cout<<"Graful este conex";
else
cout<<"Graful NU este conex";
getch();
}
Tema pentru acasă : 3 min
Construiți programul C++ pentru generarea componentelor conexe ale unui graf
neorientat G(X,U), dat prin numărul de noduri ”n” și matricea de adiacență ”a”.
4.2 PLANUL UNITĂȚII DE ÎNVĂȚARE
Conexitate, componente conexe -folosind metoda instruirii asistată de
calculator(IAC) .
Autor unitate : Prof. Gheorghiu Carmen Adina
Județ : Galați
Denumire școală : Colegiul Național „Spiru Haret”
Localitate : Tecuci
Prezentare generală a unității de învățare :
Titlul planului unității de învățare:
”Conexitate, componente conexe în grafuri neorientate”
Unitatea presupune studiul – ca element de conținut – a următoarelor subunități:
– Conexitate în grafuri neorientate;
– Descompunerea grafu rilor neorientate în componente conexe.
Aria tematică : informatică
Tipul lecției : dobândire de noi cunoștințe
Locul de desfășurare : laboratorul de informatică
Clasa : a XI-a B matematică -informatică, neintensiv
Timp necesar : 50 minute
Competențe generale :
Identificarea datelor care intervin într -o problemă și aplicarea algoritmilor
fundamentali de prelucrare a acestora;
Elaborarea algoritmilor de rezolvare a problemelor;
Implementarea algoritmilor într -un limbaj de programare.
98 Grafuri neorientate -optimizarea procesului de predare
Competențe specifice :
Descrier ea operațiilor specifice structurii de coadă și elaborarea unor
programe care să implementeze aceste operații;
Aplicarea algoritmului B.F. pentru verificarea conexității unui graf
neorientat;
Identificarea componentelor conexe.
Obiective operaționale și re zultate așteptate :
o Să utilizeze terminologia specifică grafurilor neorientate;
o Să utilizeze algoritmi de implementare a grafurilor neorientate;
o Să rezolve aplicațiile propuse prin utilizarea cunoștințelor dobândite;
o Să descrie în limbajul de programare stu diat algoritmul B.F.;
o Să definească noțiunea de graf conex;
o Să definească noțiunea de componentă conexă;
o Să implementeze în limbajul de programare studiat verificarea proprietății
de graf conex și descompunerea în componente conexe.
Aptitudini obligatorii :
Cunoștințe generale pentru ca elevul să poată începe studiul unității de învățare:
Elevii și -au însușit noțiunile fundamentale:
d. definiție, incidență, adiacență, grad;
e. metode de reprezentare: matricea de adiacență,
vectorul de muchii, listele de adiacență;
f. graf parțial, subgraf, graf complet;
Elevii utilizează și operează corect cu algoritmul B.F.;
Elevii utilizează corect calculatorul și aplicația C++.
Strategii didactice :
Principii didactice :
– Pricipiul participării și învățării active;
– Princip iul asigurării progresului gradat al performanței;
– Principiul conexiunii inverse.
Metode de învățământ :
– Metode de comunicare orală: expunere, conversație;
– Metode de acțiune: exercițiul, învățarea prin descoperire, rezolvarea
de probleme;
99 Grafuri neorientate -optimizarea procesului de predare
– Instruirea asistat ă de calculator: utilizarea aplicației C++ și Power
Point în predare.
Procedee de instruire :
– Conversația de verificare a cunoștințelor;
– Conversația euristică, cu scopul de a redescoperi cunoștințele;
– Învățarea prin descoperire, prin rezolvarea de probleme;
– Conversația de consolidare în etapa de fixare a cunoștințelor.
Forme de organizare :
– Frontală;
– Individuală.
Forme de dirijare a învățării : dirijată de profesor sau independentă.
Resurse materiale :
– Material bibliografic: Tudor Sorin, Manual pentru clasa a XI-a,
Editura L&S, INFOMAT, București, 2001;
– Fișe de lucru;
– Calculator;
– Videoproiector.
Metode de evaluare :
– Evaluare inițială: întrebări orale și exerciții;
– Evaluare finală: fișe de lucru.
Desfășurarea lecției :
Moment organizatoric :
Pregătirea lecției:
– Întocmirea proiectului didactic;
– Pregătirea setului de întrebări;
– Pregătirea setului de aplicații;
– Pregătirea temei.
Organizarea și pregătirea clasei: 2 min
o verificarea frecvenței.
o Captarea atenției clasei:
– Anunțarea subiectului pentru tema propusă;
– Anunța rea obiectivelor urmărite;
– Anunțarea modului de desfășurare a activității.
100 Grafuri neorientate -optimizarea procesului de predare
Reactualizarea cunoștințelor : 10 min
Se reactualizează cunoștințele cu ajutorul fișei 1. Evaluarea în etapa de
reactualizare se realizează frontal.
FIȘA 1
1. Ce este coada și ce operații putem efectua în aceasta?
2. Se consideră coada cu elementele 4, 9, 2, 1 introduse în această ordine și operațiile AD(x), EL de
adăugare a unui element x în coadă și eliminare. Enumerați elementele din coadă în urma efectuării
operațiilor: AD( 7), EL, EL, AD(11), AD(8), EL, EL , EL și precizați care va fi următorul element ce
poate extras .
3. Fie graful neorientat din figură:
a) specificați secvența de noduri în urma parcurgerii în lățime, considerându -se nod de start 2;
b) parcurgeți în lățime graful, alegând nod de start 7. Ce observați?
4. Fie coada cu elementele a, b, c, d introduse în această ordine. Specificați forma cozii după fiecare
din operațiile: AD(e), AD(f), AD(g), EL, EL. Câte elemente rămân în coadă și care sunt acestea?
5. În algoritmul B.F., ce rol are vectorul VIZ ?
RĂSPUNSURI AȘTEPTATE
1.Coada este reprezentată printr -un vector, care funcționează pe principiul „primul intrat – primul
ieșit”(FIFO). Aceasta deține două capete, unul de intrare a datelor, c elălalt de extragere. Operațiile
ce se pot efectua sunt de adăugare a informațiilor pe la un capăt, respectiv extragerea acestora pe la
capătul opus.
2.Elementele rămase sunt: 8 și 11. Elementul ce poate fi extras este 11.
3.a) Secvența obținută este: 2, 1, 3, 4, 5
b) Secvența obținută este: 7, 6, 8
Observăm că nu există lanț de legătură între subgrafurile: 1, 2, 3, 4, 5 și 6, 7, 8 .
101 Grafuri neorientate -optimizarea procesului de predare
4.
AD(e)
AD(f)
AD(g)
EL
EL
În coadă rămân 5 elemente: c, d, e, f, g.
5.Vectorul VIZ are rolul de reține în VIZ[i] valorile 1 sau 0 după cum nodul i a fost sau nu vizitat.
Comunicarea noilor cunoștințe : 20 min
Profesorul comunică noile cunoștințe prin intermediul unui soft educațional
conexitategn.ppt (listing în anexa I ), proiectat de acesta în Power Point, fiind structurat în
10 slide -uri, după cum urmează:
În primul slide, se comunică titlul lecției: ”Conexitate în grafuri neorientate”.
În al II-lea și al III-lea slide, se începe actualizarea cunoștințelor cu noțiunea de coadă,
exemplificându -se operațiile posibile cu aceasta.
Actualizarea continuă în al IV-lea slide, cu noțiuni teoretice privitoare la algoritmul
B.F.
102 Grafuri neorientate -optimizarea procesului de predare
În cel de -al V-lea slide se prezintă noțiunea de graf conex(definiția), continuând în
slide -ul VI cu evidențierea proprietății d e conex, prin aplicarea algoritmului B.F. pe un graf
neorientat.
În cel de -al V II-lea slide se prezintă noțiunea de componentă conexă (definiția),
continuând în slide -ul VI II cu evidențierea componentelor conex e, prin aplicarea succesivă
a algoritmului B.F. pe un graf neorientat, precum și evidențierea în slide -ul IX a unor
concluzii privitoare la conexitate -componente conexe.
Slide -ul X, conține link -ul către o aplicație demonstrativ ă pentru evidențierea
proprietății de conex sau a componentelor conexe, în formă text sau grafică, pentru un
graf cu maximum 5 noduri, aplicație originală .
Dirijarea învățării pentru obținerea performanței : 15 min
Se realizează cu ajutorul fișei 2.
FIȘA 2
1.Fie graful din figura alăturată:
a.verificați dacă graful este conex;
b.câte componente conexe are graful?
c.câte muchii minim trebuie adăugate astfel încât graful să devină conex?
d.câte componente conexe minim se pot obține în graful din figură, prin redistribuirea muchiilor?
2.Construiți în C++ programul de ve rificare a conexității unui graf neorientat G(X,U), dat prin
numărul ”n” de noduri și matricea de adiacență ”a”.
103 Grafuri neorientate -optimizarea procesului de predare
RĂSPUNSURI AȘTEPTATE
1.a.Ordinea nodurilor la aplicarea algoritmului B.F. cu nod de start 3 este următoarea: 3, 2, 4, 1. Nu
au fost introduse în coadă toate nodurile grafului, deci acesta NU este conex.
b.Graful are două componente conexe: CC1: 1, 2, 3, 4
CC2: 5
c.Numărul minim de muchii ce pot fi adăugate într -un graf neco nex astfel încât acesta să devină
conex, este de (x -1), unde x=numărul de componente conexe ale grafului. Deci sunt necesare
minim o muchie.
d.Prin redistribuire, se poate obține o componentă conexă, chiar graful, acesta devenind conex.
2.
#include<iostrea m.h>
#include<conio.h>
int viz[30],n,k,u,v,p,a[20][20],c[30],pstart;
void introducere()
{
int i,j;
cout<<"Dati numarul de varfuri n=";
cin>>n;
for(i=1;i<=n -1;i++)
for(j=i+1;j<=n;j++)
{
cout<<"a["<<i<<"]["<<j<<"]'=";
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
int bf()
{
int i,viz[10],c[10],pi,ps;
cout<<"Nodul de start: ";
cin>>pstart;
for(i=1;i<=n;i++)
viz[i]=0;
pi=1;
ps=1;
viz[pstart]=1;
104 Grafuri neorientate -optimizarea procesului de predare
c[pi]=pstart;
while(pi>=ps)
{
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
return(pi==n);
}
void main()
{
clrscr();
introducere();
if(bf())
cout<<"Graful este conex";
else
cout<<"Graful NU este conex";
getch();
}
Tema pentru acasă : 3 min
Construiți programul C++ pentru generarea componentelor conexe ale unui graf
neorientat G(X,U), dat prin numărul de noduri ”n” și matricea de adiacență ”a”.
105 Grafuri neorientate -optimizarea procesului de predare
4.3 TEST DE EVALUARE – conexitate în grafuri neorientate
Obiectiv cadru:
Realizarea de aplicații utilizând algoritmi specifici
Obiective de referință:
o Să aplice algoritmul de parcurgere în lățime B.F.;
o Să urmărească etapele de rezolvare a unei probleme.
Obiective educaționale:
o Să utilizeze corect definițiile însușite;
o Să utilizeze corect structura de coadă;
o Să aplice corect algoritmul de parcurgere în lățime a unui graf neorientat;
o Să identifice componentele conexe ale unui graf neorientat;
o Să elaboreze algoritmi pentru problemele propuse;
o Să utilizeze subprogramele pentru rezolvarea unor probleme.
Subiectul I
Pentru graful din figură, precizați :
a. ordinea nodurilor la aplicarea algoritmului B.F. cu nod de start 3;
b. ordinea nodurilor la aplicarea algoritmului B.F. cu nod de start 5;
c. câte componente conexe are graful precum și nodurile din alcătuirea fiecăreia;
d. câte muchii minim trebuie adăugate astfel încât graful să devină conex?
Subiectul al II-lea
Completați spațiile libere :
a.Un graf neorientat cu ”p” componente conexe are nevoie de adăugarea a
minim……..muchii astfel încât să devină conex;
b.Un graf neorientat cu n=12 noduri și m=8 muchii poate avea maxim……..componente
conexe;
106 Grafuri neorientate -optimizarea procesului de predare
c.Un graf neorientat cu n=12 noduri și m=7 muchii , fără noduri izolate, în care exact 3
noduri au gradul 2, poate avea maxim……..componente conex e;
d. Un graf neorientat cu n=10 noduri și m=45 muchii are……….componente conexe.
Subiectul al III -lea
Răspundeți cu adevărat(A)/fals(f):
a. O componentă conexă a unui graf neorientat G(X,U) este un graf parțial G1(X,U1) al lui
G, cu proprietatea de conex;
b. Știind că un graf neorientat cu n=10 noduri are în una din componentele sale conexe
nodurile 4, 5, 8, 1, forma vectorului VIZ în urma primei aplicări a algoritmului B.F. pe
graf, cu nod de start=5 este: (1, 0, 0, 1, 1, 0, 0, 1, 0, 0) ;
c. O componentă conexă a unui graf neorientat cu ”n” noduri, are minim un nod și maxim
”n” noduri;
d. Pentru graful din figură:
aplicarea algoritmului B.F. cu nod de start=3 duce la obținerea următoarei succesiuni de
noduri: 3, 1, 4, 2.
Subiectul al IV -lea
Alegeți răspunsul corect:
1.Care este numărul maxim de componente conexe într -un graf neorientat cu n=9 noduri și
m=12 muchii?
a.3
b.4
c.2
d.5
2. Care este numărul minim de componente conexe într -un graf neorientat cu n=12 noduri
și m=7 muchii?
a.4
b.3
c.5
d.6
107 Grafuri neorientate -optimizarea procesului de predare
3.Pentru graful din figură:
ordinea nodurilor la aplicarea algoritmului B.F. cu nod de start=2 este:
a.2, 4, 5, 3, 1
b.2, 4, 5, 1, 3
c.2, 5, 4, 3, 1
d.2, 5, 4, 1, 3
4.Fie graful neorientat din figură:
Numărul minim de muchii ce pot fi eliminate astfel încât graful obținut să aibă două
componente conexe este:
a.4
b.3
c.2
d.6
Subiectul al V -lea
Pentru un graf neorientat G(X,U), dat prin numărul de noduri ”n” și matricea de adiacență
”a”, realizați funcții care:
a.să afișeze componenta conexă cu număr maxim de noduri;
b.să afișeze nodul maxim din fiecare component ă conexă.
108 Grafuri neorientate -optimizarea procesului de predare
REZOLVAREA TESTULUI DE EVALUARE
Subiectul I
a.3, 6
b.5, 2, 8, 7, 4, 1
c.Graful are două componente conexe:
CC1: 1, 2, 4, 5, 7, 8
CC2: 3, 6
d.Sunt necesare minim 1 muchie.
Subiectul al II -lea
a.(p-1)
b.8 componente conexe
c.5 componente conexe
d.1 componentă conexă
Subiectul al III -lea
a.F
b.A
c.A
d.F
Subiectul al IV -lea
1.b
2.c
3.a
4.b
Subiectul al V -lea
a.
void afis(int a[10][10],int n)
{
int viz[10],i,pi,ps,pstart,max,v[10];
for(i=1;i<=n;i++)
viz[i]=0;
109 Grafuri neorientate -optimizarea procesului de predare
pstart=1;
max=0;
do
{
pi=1;
ps=1;
viz[pstart]=1;
c[pi]=pstart;
while(pi>=ps)
{
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
if(pi>max)
{
max=pi;
for(i=1;i<=pi;i++)
v[i]=c[i];
}
pstart=1;
while(pstart<=n&&viz[pstart]==1)
pstart++;
}while(pstart<=n);
for(i=1;i<=max;i++)
cout<<v[i]<<' ';
}
b.
int maxim(int v[10],int p)
{
int j,m1;
110 Grafuri neorientate -optimizarea procesului de predare
m1=v[1];
for(j=2;j<=p;j++)
if(v[j]>m1)
m1=v[j];
return m1;
}
void afisare(int a[10][10],int n)
{
int viz[10],i,pi,ps,pstart;
for(i=1;i<=n;i++)
viz[i]=0;
pstart=1;
do
{
pi=1;
ps=1;
viz[pstart]=1;
c[pi]=pstart;
while(pi>=ps)
{
for(i=1;i<=n;i++)
if(a[c[ps]][i]==1&&viz[i]==0)
{
pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
cout<<maxim(c,pi)<<' ';
pstart=1;
while(pstart<=n&&viz[pstart]==1)
pstart++;
}while(pstart<=n);
}
111 Grafuri neorientate -optimizarea procesului de predare
BAREM DE CORECTARE
Subiectul I 16 p
a, b, c, d 4 p/răspuns corect
Subiectul II 20 p
a, b, c, d 5 p/răspuns corect
Subiectul III 16 p
a, b, c, d 4 p/răspuns corect
Subiectul IV 20 p
1, 2, 3, 4 5 p/răspuns corect
Subiectul V 18 p
a 9 p
3 p-antet corect
3 p-algoritm corect
3 p-corectitudinea sintaxei
b 9 p
3 p-antet corect
3 p-algoritm corect
3 p-corectitudinea sintaxei
OFICIU 10 p
TOTAL 100 p
112 Grafuri neorientate -optimizarea procesului de predare
4.4 CONCLUZII
În urma aplicării testului de evaluare la clasa a XI -a A, unde predarea noilor
cunoștințe s -a realizat prin metode clasice, s -au obținut următoarele rezultate:
Număr elevi: 30
Nota Numă de elevi
10 5
9 4
8 7
7 7
6 7
În urma aplicării testului de evaluare la clasa a XI -a B, unde predarea noilor
cunoștințe s -a realizat cu ajutorul instruirii asistată de calculator(IAC) , s-au obținut
următoarele rezultate:
Număr elevi: 31
Nota Numă de elevi
10 7
9 7
8 9
7 8
Este evidentă creșterea randamentului elevilor de la clasa unde am folosit IAC, așa
cum reiese și din graficul de mai jos:
0 0 0 0 07 7 7
45
0 0 0 0 0 089
7 7
012345678910
1 2 3 4 5 6 7 8 9 10Clasa a XI-a A
Clasa a XI-a B
113 Grafuri neorientate -optimizarea procesului de predare
În urma utilizării IAC, am remarcat și dezvoltarea creativității elevilor, aceștia fiind
capabili să dezvolte aplicații mult mai complexe și mai atractive, prin utilizarea modului
grafic al mediului de programare(Anexa 2, Anexa 3).
Utilizarea IAC mărește interesul elevilor, informațiile fiind prezentate într -o formă
nouă, atractivă, profesorul având posibilitatea de a lărgi domeniul creativ și de a
interacționa mai mult cu elevii, aceștia adresând întrebări despre modul de realizare a
programelor precum și despre domeniile în care pot utiliza noile forme de prezentare.
Datorită interesului crescut, informațiile sunt mult mai bine aprofundate , asimilate
și exploatate, rezultatele ulterioare fiind considerabil mai bune.
Tehnologia progresează, știința impulsionează dezvolatrea sa, zilnic apar meserii
noi, la unele dintre ele nici nu ne gândim deocamdată. Mulți dintre elevii aflați a cum pe
băncile școlii vor îmbrățișa aceste meserii, poate nu le vor putea învăța în școală pentru că
nu se vor fi inventat încă, totuși, ei le vor deprinde cumva…Dar pentru asta, gândirea și
cunoașterea lor trebuie să fie adaptabile, competențele pe care l e dobândesc în școală
trebuie să permită ancorarea fiecărui individ în lumea reală.
Creativitatea și interesul elevilor sunt fără limite, profesorul constituind factorul
principal al dinamizării eforturilor depuse de aceștia.
114 Grafuri neorientate -optimizarea procesului de predare
ANEXE
1.Soft IAC
115 Grafuri neorientate -optimizarea procesului de predare
116 Grafuri neorientate -optimizarea procesului de predare
117 Grafuri neorientate -optimizarea procesului de predare
Listing -ul programului demonstrativ:
program conexitate_grafuri_neorientate;
uses crt,graph;
type
vector=array[1..100] of integer;
var
gd,gm:integer;
nr,n:integer;
viz,c:vector;
a,d:array [1..10,1..10] of integer;
ch:char;
procedure initgr;
begin
gd:=detect;
initgraph(gd,gm,'d: \bp\bgi');
end;
procedure citire;
var
i,j:integer;
begin
write('Numarul de varfuri din graf:');
readln(n);
writeln('Introduceti matricea de adiacenta');
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;
118 Grafuri neorientate -optimizarea procesului de predare
procedure desen;
var i:integer;
begin
initgr;
cleardevice;
setlinestyle(0,0,3);
settextstyle(1,0,2);
setcolor(12);
circle(100,70,15);
delay(400);
outtext xy(95,57,'1');
delay(400);
if (n>=2) then
begin
circle(440,70,15);
delay(400);
outtextxy(435,57,'2');
delay(400);
end;
if (n>=3) then
begin
circle(270,150,15);
delay(400);
outtextxy(265,138,'3');
delay(400);
end;
if (n>=4) then
begin
circle(100,400,15);
delay(400);
outtextxy(95,387,'4');
delay(400);
end;
if (n=5) then
begin
circle(440,400,15);
delay(400);
outtextxy(435,387,'5');
delay(400);
end;
if (a[1,4]=1) then
begin
line(97,85,97,384);
delay(400);
end;
if (a[2,5]=1) then
begin
line(437,85,437,384);
delay(400);
end;
119 Grafuri neorientate -optimizarea procesului de predare
if (a[1,3]=1) then
begin
line(115,70,270,136);
delay(400);
end;
if (a[2,3]=1) then
begin
line(425,70,270,136);
delay(400);
end;
if (a[3,4]=1) then
begin
line(115,400,270,167);
delay(400);
end;
if (a[3,5]=1) then
begin
line(425,400,270,167);
delay(400);
end;
if (a[1,2]=1) then
begin
line(115,70,425,70);
delay(400);
end;
if (a[1,5]=1) then
begin
line(115,70,425,400);
delay(400);
end;
if (a[2,4]=1) then
begin
line(425,70,115,400);
delay(400);
end;
if (a[4,5]=1) then
line(115,400,425,400);
outtextxy(480,70,'Evidentierea ');
outtextxy(480,130,'componentelor');
outtextxy(480,190,'conexe');
end;
procedure desen1(q:vector;w:integer);
var i:integer;
begin
if(nr=1)then
setcolor(green)
120 Grafuri neorientate -optimizarea procesului de predare
else
if(nr=2)then
setcolor(yellow)
else
if(nr=3)then
setcolor(blue)
else
if(nr=4)then
setcolor(brown)
else
if(nr=5)then
setcolor(23);
for i:=1 to w do
begin
case q[i] of
1:begin
circle(100,70,15);
delay(400);
outtextxy(95,57,'1');
end;
2:begin
circle(440,70,15);
delay(400);
outtextxy(435,57,'2');
end;
3:begin
circle(270,150,15);
delay(400);
outtextxy(265,138,'3');
end;
4:begin
circle(100,400,15);
delay(400);
outtextxy(95,3 87,'4');
end;
5:begin
circle(440,400,15);
delay(400);
outtextxy(435,387,'5');
end;
end;
end;
end;
procedure conex;
var
cont,pstart,pi,ps,i,j:integer;
begin
for i:=1 to n do
begin
c[i]:=0;
viz[i]:=0;
end;
pstart:=1;
cont:=0;
121 Grafuri neorientate -optimizarea procesului de predare
repeat
pi:=1;
ps:=1;
c[pi]:=pstart;
viz[pstart]:=1;
while ps<=pi do
begin
for i:=1 to n do
if (viz[i]=0) and (a[c[ps],i]=1) then
begin
inc(pi);
c[pi]:=i;
viz[i]:=1;
end;
inc(ps);
end;
if pi=n then
writeln('Graful este conex')
else
begin
textcolor(white);
cont:=cont+1;
writeln('a ',cont,' -a componenta conexa');
textcolor(35);
for i:=1 to pi do
write(c[i],' ');
textcolor(white);
writeln;
writeln('&&&&&&&&&&&&&&&&&&&&&&&&&&');
end;
i:=0;
repeat
inc(i);
until (viz[i]=0) or (i=n+1);
if i<n+1 then
pstart:=i;
until i=n+1;
end;
procedure conex1;
var
cont,pstart,pi,ps,i,j:integer;
begin
for i:=1 to n do
begin
c[i]:=0;
viz[i]:=0;
end;
pstart:=1;
cont:=0;
repeat
pi:=1;
ps:=1;
c[pi]:=pstart;
122 Grafuri neorientate -optimizarea procesului de predare
viz[pstart]:=1;
while ps<=pi do
begin
for i:=1 to n do
if (viz[i]=0) and (a[c[ps],i]=1) then
begin
inc(pi);
c[pi]:=i;
viz[i]:=1;
end;
inc(ps);
end;
if pi=n then
begin
writeln('Graful este conex');
readkey;
desen;
end
else
begin
nr:=nr+1;
if(nr=1) then
begin
desen;
desen1(c,pi);
end
else
desen1(c,pi);
readkey;
end;
i:=0;
repeat
inc(i);
until (viz[i]=0) or (i=n+1);
if i<n+1 then
pstart:=i;
until i=n+1;
end;
procedure prezentare;
begin
initgr;
settextstyle(1,0,2);
setcolor(15);
outtextxy(10,10,'COLEGIUL NATIONAL "SPIRU HARET"');
outtextxy(120,40,'TECUCI');
setcolor(red);
settextstyle(1,0,4);
outtextxy(280,150,'TEMA');
settextstyle(1,0,2);
setcolor(green);
outtextxy(100,250,' CONEXITATE ');
outtextxy(100,290,' IN GRAFURI NEORIENTATE ');
readkey;
123 Grafuri neorientate -optimizarea procesului de predare
closegraph;
end;
procedure meniu;
begin
initgr;
settextstyle(1,0,2);
setbkcolor(2);
outtextxy(120,70,'MENIU PRINCIPAL');
outtextxy(100,140,'1 -Citire date intrare');
outtextxy(100,180,'2 -Conexitate in graf -rezolvare mod text');
outtextxy(100,220,'3 -Conexitate in graf -rezolvare mod grafic');
outtextxy(100,260,'4 -Parasire program');
ch:=readkey;
closegraph;
end;
begin
prezentare;
repeat
meniu;
case ch of
'1':begin
clrscr;
citire;
end;
'2':begin
conex;
readln;
end;
'3':begin
nr:=0;
conex1;
readln;
end;
end;
until ch='4';
end.
2.Program proprietatea de Hamilton -ian și Euler -ian
program hamiltonian_eulerian_grafuri_neorientate;
uses crt,graph;
type
vector=array[1..100] of integer;
var
gd,gm,tt,k,tt1,tt0:integer;
n,aux,m,aux1,i,cont:integer;
st,viz,c,v,v1,st1:vector;
a,d:array [1..10,1..10] of integer;
ch:char;
124 Grafuri neorientate -optimizarea procesului de predare
procedure initgr;
begin
gd:=detect;
initgraph(gd,gm,'d: \bp\bgi');
end;
procedure citire;
var
i,j:integer;
begin
m:=0;
write('Numarul de varfuri din graf:');
readln(n);
writeln('Introduceti matricea de adiacenta');
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];
if a[i,j]=1 then
inc(m);
end;
end;
procedure init;
var
i:integer;
begin
for i:=1 to n+1 do
st[i]:=0;
end;
function valid(k:integer):boolean;
var
i:integer;
begin
valid:=true;
if k>1 then
if a[st[k -1],st[k]]=0 then
valid:=false;
if (k>1) and (k<n+1) then
for i:=1 to k -1 do
if st[k]=st[i] then
valid:=false;
if k=n+1 then
if st[1]<>st[k] then
valid:=false;
end;
procedure tipar(k:integer);
var
125 Grafuri neorientate -optimizarea procesului de predare
i:integer;
begin
aux:=1;
inc(cont);
if cont=1 then
begin
tt:=k;
for i:=1 to k do
begin
write(st[i],' ');
v[i]:=st[i];
end;
end;
end;
procedure bktr(k:i nteger);
var
i:integer;
begin
for i:=1 to n do
begin
st[k]:=i;
if valid(k) then
if k=n+1 then
tipar(k)
else
bktr(k+1);
end;
end;
procedure init1;
var
i:integer;
begin
for i:=1 to m+1 do
st[i]:=0;
end;
function valid1(k:integer):boolean;
var
i:integer;
begin
valid1:=true;
if k>1 then
if a[st[k -1],st[k]]=0 then
valid1:=false;
if k>=3 then
for i:=1 to k -2 do
if ((st[i]=st[k -1]) and (st[i+1]=st[k])) or ((st[i]=st[k]) and (st[i+1]=st[k -1])) then
valid1:=false;
if k=m+1 then
if st[1]<>st[k] then
valid1:=false;
126 Grafuri neorientate -optimizarea procesului de predare
end;
procedure tipar1(k:integer);
var
i:integer;
begin
aux1:=1;
tt0:=k;
for i:=1 to tt0 do
v[i]:=st[i];
end;
procedure bktr1(k:integer);
var
i:integer;
begin
for i:=1 to n do
begin
st[k]:=i;
if valid1(k) then
if k=m+1 then
tipar1(k)
else
bktr1(k+1);
end;
end;
procedure desen;
var i:integer;
begin
initgr;
cleardevice;
setlinestyle(0,0,3);
settextstyle(1,0,2);
setcolor(12);
circle(100,70,15);
delay(400);
outtextxy(95,57,'1');
delay(400);
circle(100,400,15);
delay(400);
outtextxy(95,387,'4');
delay(400);
circle(270,220,15);
delay(400);
outtextxy(265,207,'3');
delay(400);
circle(440,70,15);
delay(400);
outtextxy(435,57,'2');
delay(400);
circle(440,400,15);
127 Grafuri neorientate -optimizarea procesului de predare
delay(400);
outtextxy(435,387,'5');
delay(400);
if a[1,4]=1 then
begin
line(97,85,97,384);
delay(400);
end;
if a[2,5]=1 then
begin
line(437,85,437,384);
delay(400);
end;
if a[1,3]=1 then
begin
line(115,70,270,205);
delay(400);
end;
if a[2,3]=1 then
begin
line(425,70,270,205);
delay(400);
end;
if a[3,4]=1 then
begin
line(115,400,270,235);
delay(400);
end;
if a[3,5]=1 then
begin
line(425,400,270,235);
delay(400);
end;
if a[1,2]=1 then
begin
line(115,70,425,70);
delay(400);
end;
if a[4,5]=1 then
line(115,400,425,400);
outtextxy(480,70,'Evidentierea ');
outtextxy(480,130,'ciclului');
outtextxy(480,190,'hamilt onian');
end;
procedure desen2;
var i:integer;
begin
initgr;
cleardevice;
setlinestyle(0,0,3);
settextstyle(1,0,2);
setcolor(12);
circle(100,70,15);
128 Grafuri neorientate -optimizarea procesului de predare
delay(400);
outtextxy(95,57,'1');
delay(400);
circle(100,400,15);
delay(400);
outtextxy(95,387,'4');
delay(400);
circle(270,220,15);
delay(400);
outtextxy(265,207,'3');
delay(400);
circle(440,70,15);
delay(400);
outtextxy(435,57,'2');
delay(400);
circle(440,400,15);
delay(400);
outtextxy(435,387,'5');
delay(400);
if a[1,4]=1 then
begin
line(97,85,97,384);
delay(400);
end;
if a[2,5]=1 then
begin
line(437,85,437,384);
delay(400);
end;
if a[1,3]=1 then
begin
line(115,70,270,205);
delay(400);
end;
if a[2,3]=1 then
begin
line(425,70,270,205);
delay(400);
end;
if a[3,4]=1 then
begin
line(115,400,270,235);
delay( 400);
end;
if a[3,5]=1 then
begin
line(425,400,270,235);
delay(400);
end;
if a[1,2]=1 then
begin
line(115,70,425,70);
delay(400);
end;
if a[4,5]=1 then
129 Grafuri neorientate -optimizarea procesului de predare
line(115,400,425,400);
outtextxy(480,70,'Evidentierea ');
outtextxy(480,130,'ciclului');
outtextxy(480,190,'eulerian');
end;
procedure desen1(tt1,tt2:integer);
var i:integer;
begin
if ((v[tt1]=1) and (v[tt2]=2)) or ((v[tt1]=2) and (v[tt2]=1)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(115,65,425,65);
delay(400);
setcolor(white);
line(115,65,425,65);
delay(400);
end;
setcolor(white);
line(115,65,425,65);
end;
if ((v[tt1]=1) and (v[tt2]=3)) or ((v[tt1]=3) and (v[tt2]=1)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(115,75,265,205);
delay(400);
setcolor(white);
line(115,75,265,205);
delay(400);
end;
setcolor(white);
line(115,75,265,205);
end;
if ((v[tt1]=3) and (v[tt2]=4)) or ((v[tt1]=4) and (v[tt2]=3)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(117,390,265,235);
delay(400);
setcolor(white);
line(117,390,265,235);
delay(400);
end;
setcolor(white);
line(117,390,265,235);
end;
130 Grafuri neorientate -optimizarea procesului de predare
if ((v[tt1]=4) and (v[tt2]=5)) or ((v[tt1]=5) and (v[tt2]=4)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(115,405,425,405);
delay(400);
setcolor(white);
line(115,405,425,405);
delay(400);
end;
setcolor(white);
line(115,405,425,405);
end;
if ((v[tt1]=5) and (v[tt2]=3)) or ((v[tt1]=3) and (v[tt2]=5)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(425,390,275,235);
delay(400);
setcolor(white);
line(425,390,275,235);
delay(400);
end;
setcolor(white);
line(425,390,275,235);
end;
if ((v[tt1]=3) and (v[tt2]=2)) or ((v[tt1]=2) and (v[tt2]=3)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(425,75,275,205);
delay(400);
setcolor(white);
line(425,75,275,205);
delay(400);
end;
setcolor(white);
line(425,75,275,205);
end;
if ((v[tt1]=1) and (v[tt2]=4)) or ((v[tt1]=4) and (v[tt2]=1)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
131 Grafuri neorientate -optimizarea procesului de predare
line(102,85,102,384);
delay(400);
setcolor(white);
line(102,85,102,384);
delay(400);
end;
setcolor(white);
line(102,85,102,384);
end;
if ((v[tt1]=2) and (v[tt2]=5)) or ((v[tt1]=5) and (v[tt2]=2)) then
begin
for i:=1 to 2 do
begin
setcolor(black);
line(432,85,432,384);
delay(400);
setcolor(white);
line(4 32,85,432,384);
delay(400);
end;
setcolor(white);
line(432,85,432,384);
end;
end;
procedure euler_teor;
var
cont,pstart,pi,ps,i,j,s:integer;
ok:boolean;
begin
for i:=1 to n do
begin
c[i]:=0;
viz[i]:=0;
end;
pstart:=1;
pi:=1;
ps:=1;
c[pi]:=pstart;
viz[pstart]:=1;
while ps<=pi do
begin
for i:=1 to n do
if (viz[i]=0) and (a[c[ps],i]=1) then
begin
inc(pi);
c[pi]:=i;
viz[i]:=1;
132 Grafuri neorientate -optimizarea procesului de predare
end;
inc(ps);
end;
ok:=true;
for i:=1 to n do
begin
s:=0;
for j:=1 to n do
s:=s+a[i,j];
if (s mod 2 <>0) or (s=0) then
ok:=false;
end;
if (pi=n) and (ok=true) then
writeln('Graful este EULERIAN')
else
writeln('Graful NU este EULERIAN')
end;
procedure ham_teor;
var
i,j,s:integer;
ok:boolean;
begin
ok:=true;
for i:=1 to n do
begin
s:=0;
for j:=1 to n do
s:=s+a[i,j];
if s<n/2 then
ok:=false;
end;
if (n>=3) and (ok=true) then
writeln('Graful este HAMILTONIAN')
else
writeln('Graful NU este HAMILTONIAN');
end;
procedure prezentare;
begin
initgr;
settextstyle(1,0,2);
setcolor(15);
outtextxy(10,10,'COLEGIUL NATIONAL "SPIRU HARET"');
outtextxy(20,40,'TECUCI');
setcolor(red);
settextstyle(1,0,4);
outtextxy(200,150,'TEMA LUCRARII');
settextstyle(1,0,2);
setcolor(green);
133 Grafuri neorientate -optimizarea procesului de predare
outtextxy(100,250,' PROPRIETATILE DE HAMILTONIAN SI EULERIAN ');
outtextxy(100,290,' IN GRAFURI NEORIENTATE ');
outtextxy(10,400,'Elev : Prof. Gheorghiu Carmen');
readkey;
closegraph;
end;
procedure meniu;
begin
initgr;
settextstyle(1,0,2);
setbkcolor(2);
outtextxy(120,70,'MENIU PRINCIPAL');
outtextxy(100,140,'1 -Citire date intrare');
outtextxy(100,180,'2 -Hamiltonian pe baza definitiei');
outtextxy(100,220,'3 -Hamiltonian pe baza teoremei');
outtextxy(100,260,'4 -Eulerian pe baza definitiei');
outtextxy(100,300,'5 -Eulerian pe baza teoremei');
outtextxy(100,340,'6 -Parasire program');
ch:=readkey;
closegraph;
end;
begin
prezentare;
repeat
meniu;
case ch of
'1':begin
clrscr;
citire;
end;
'2':begin
cont:=0;
aux:=0;
init;
bktr(1);
if aux=0 then
begin
writeln('Graful nu este Hamiltonian');
readln;
end
else
begin
desen;
for i:=1 to tt -1 do
desen1(i,i+1);
readln;
closegraph;
end;
end;
134 Grafuri neorientate -optimizarea procesului de predare
'3':begin
ham_teor;
readln;
end;
'4':begin
aux1:=0;
init1;
bktr1(1);
if aux1=0 then
begin
writeln('Graful nu este Eulerian');
readln;
end
else
begin
desen2;
for i:=1 to tt0 -1 do
desen1(i,i+1);
readln;
closegraph;
end;
end;
'5':begin
euler_teor;
readln;
end;
end;
until ch='6';
end.
135 Grafuri neorientate -optimizarea procesului de predare
BIBLIOGRAFIE
1. Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Introducere în algoritmi,
Editura Computer Libris Agora 1996;
2. Ioan Tomescu,Data Structures, Bucharest University Press, Bucharest 2004
3. Knuth, D.E., Tratat de programarea calculatoarelor, Editura Teora, București 2000
4. Tudor Sorin, Tehnici de programare, Editura L&S Infomat 2000
5. Mariana Miloșescu, Informatica C++, Editura Didactică și pedagogică, București
2002.
6. Cristian Udrea, Claudia Elena Udrea, Dan Cristian Ț acu, Diana Nicoleta Udrea,
Pascal.Teorie și Aplicații, Editura Arves 2003.
7. Ioan Tomescu, Introducere în Combinatorică, Editura Tehnică București 1972.
8. Ioan Tomescu, Probleme de combinatorică și teoria grafurilor, Editura didactică și
pedagogică, București 1984.
9. Ioan Tomescu, Grafuri și programare liniară, Editura didactică și pedagogică
București, 1975.
10. Ioan Tomescu, Combinatorică și teoria grafurilor, Tipografia Universității din
București, 1978.
11. Daniela Oprescu, Liana Bejan Ienulescu, Viorica Pătrașcu, Informatica, manual
pentru clasa a XI -a, Editura Niculescu, București 2001.
12. Emanuela Cerchez, Marinel Șerban, Programarea în limbajul C++, Editura Polirom,
Iași 2005.
13. Mihaela Runceanu, Carmen Negrea, Culegere de probleme de informatică, Editura
Donaris, Si biu 2003.
14. Georgie Daniel Vlad, Daniela Marcu, Culegere de probleme de informatică, Editura
Didactică și pedagogică, București 2003.
15. Severin Bumbaru, Structuri de date, algoritmi și tehnici de programare cu aplicații
Java, Universitatea Dunărea de Jos Galaț i
16. Doina Logofătu, Bazele programării în C. Aplicații, Editura Polirom, Iași 2006.
17. Carmen Petre, Ștefania Crăciunoiu, Daniela Popa, Camelia Iliescu, Metodica predării
informaticii și tehnologiei informației, Editura Arves, 2002.
18. Andrei Barna, Georgeta Antoh e, Curs de pedagogie, Editura Sinteze, Galați 2003.
136 Grafuri neorientate -optimizarea procesului de predare
19. Andonie R., Garbacea I. – Algoritmi fundamentali. O perspectivă C++. Editura Libris,
Cluj-Napoca, 1995.
20. Curs Intel® Teach – Instruirea în societatea cunoașterii (proiect implementat de
MECTS în parteneri at cu Siveco -România).
21. http://vega.unitbv.ro/~andonie/Cartea_WEB/toc.htm
22. http://ebooks.unibuc.ro/informatica/carabianu/CARA_STR.pdf
23. http://www.campion.edu.ro/arhiva/arhiva_2009/papers/papers30.pdf (Heap -uri, articol
de Emanuela Cerchez).
24. http://www.ginfo.ro/revista/147/focus.pdf (heap -uri binomiale, articol scris de Mihai
Scorța).
25. http://www.infobits.ro/materiale -on-line pentru profesori (arbori de
intervale(segments -tres), articol Dana Lica.)
26. http://www.scribd.com/doc/151635192/Curs -de-Structuri -de-Date -Florian -Moraru
27. George Daniel Matee scu, Pavel Florin Moraru – Informatica pentru liceu și
bacalaureat. Editura Donaris, Sibiu, 2006 .
28. http://instruireaasistatadecalculator.blogspot.ro/ , (Chira Elena)
137 Grafuri neorientate -optimizarea procesului de predare
DECLARAȚIE DE AUTENTICITATE A
LUCRĂRII METODICO – ȘTIINȚIFICE
DE GRAD DIDACTIC I
Subsemnata_ ________________________________________________________________
legitimat ă cu __________ seria _________ nr. ___________ CNP______________________
telefon _____________________ auto area lucrării__________________________________
__________________________________________________________________________
elaborată în vederea susținerii examenului de grad didactic I in anul universitar 2016 – 2017
organizat de către Departamentul pentru Pregătirea Personalului Didactic din cadrul
Universității “Transilvania” din Brașov, pentru seria 2015 – 2017, luând în considerare
Metodologia formării continue a personalului didactic din învățământul preuniversita r aprobată
prin O.M. nr. 5720/20.10.2009, respectiv Ordinul MECTS nr. 5561/07.10.2011 cu adaugiri,
declar pe proprie răspundere că această lucrare a fost elaborată în întregime de către mine, nu
au fost folosite alte surse decât cele menționate în bibliogr afie, nu au fost preluate texte, date
sau elemente de grafică din alte lucrări sau din alte surse fără a fi citate și fără a fi precizată
sursa preluării, inclusiv în cazul în care sursa o reprezintă alte lucrări ale mele și că lucrarea nu
a mai fost folos ită în alte contexte de examen sau de concurs.
Declar, de asemenea, că în lucrare nu există idei, tabele, grafice , hărți sau alte
surse folosite fără respectarea legii române și a convențiilor internaționale privind drepturile
de autor.
Brașov,
Data Semnătura
______________ _________________
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Rusu D. Carmen Adina (căs. Gheorghiu) [610835] (ID: 610835)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.