GRAFURINOTIUNI INTRODUCTIVE

Manualul Clasa a XI-a

CONCEPTIE SI IMPLEMENTARE in LABORATORUL AEL

Prof. Condor Iuliu-Zoltan

Lucrarea prezinta lectiile « AEL » realizate de firma Siveco, implementare in laboratoarele de informatica. Chiar daca sistemele nu functioneaza in totalitate, se pot extrage lectii valoroase din aceste pachete prezentindu-le separat ca teme individuale in cadrul unitatilor de invatare.

De asemenea sunt prezentate elemente de metodica, legate de acesta tema, care se pot folosi ca « MANUAL AL PROFESORULUI », elemente care structureaza si orienteaza profesorul in efortul sau de predare al disciplinei in speta al elementelor din « TEORIA GRAFURILOR ».

Cuprins

1. Terminologie2. Informatii generale 3. Obiective4. Structura generalaContinutRecomandari de structurare si predare5. Structura detaliata a continuturilorIntroducere – Drumul lui NapoleonConstructie – Istoricul grafurilorIncidentaGraf partialSubgrafGraf bipartitGraf completGraf conex6. Teste de evaluare7. Teme pentru acasa8. Bibliografie

9. Terminologie – Prezentarea elementelor de software Obiect de continut

Un fisier independent, care prezinta informatii grupate din punct de vedere tematic, ce nu pot fi prezentate separat. Poate fi format din mai multe pagini de continut .

In cadrul acestui ghid vom folosi si notiunea de componenta atunci cand vom face referire la un obiect de continut.Butoane Start animatie / Trecem la pasul urmator

Sunt amplasate in cadrul animatiilor si al aplicatiilor care contin mai multi pasi. Prin apasarea acestui buton se trece la pasul urmator al animatiei.Butonul Reluare animatie

Este amplasat in cadrul animatiilor si prin accesarea acestuia se poate relua animatia.Butonul de obiective

Este amplasat in partea de jos a ecranului si ofera utilizatorului, intr-o fereastra de detalii, obiectivele parcurgerii materialului din modulul respectiv.Buton Trecem la pasul anterior

Este amplasat in cadrul teoriei si prin accesarea acestui buton se revine la jocul interactiv care a utilizat teoria respectiva.

Butonul Teorie

Prin accesarea acestui buton se ofera elevului posibilitatea de a revedera notiunile teoretice necesare rezolvarii interactive a preoblemei amintite.Butonul Help

Se afla amplasat in partea dreapta sus a ecranului. Prin accesarea acestui buton se deschide fereastra Help care ofera indicatii despre modul de utilizare a mouse-ului in desfasurarea jocului interactiv propus.Buton de Demonstratie

Prin accesarea acestuia se ofera elevului demonstrarea unei anumite teoreme din teoria grafurilor, teorema care este enuntata si urmata apoi de butonul de demonstratie.Buton de Constructie

Este plasat in partea din dreapta jos a ecranului .Prin accesarea acestui buton se poate trece la momentul

construirii unui graf. Se ofera elevului posibilitatea de verificare interactiva a nivelului de intelegere a notiunii de graf.Buton de Verificare / Resetare

Ofera posibilitatea de verificare a modului de rezolvare a unei cerinte de catre elev si respectiv reluarea rezolvarii problemei daca elevul acceseaza butonul Resetare.

Ferestre de meniuriSunt utilizate in cadrul construirii de grafuri neorientate.

Aceste ferestre ofera elevului posibilitatea de a construi nodurile si muchiile pentru un graf neorientat, precum si posibilitatea de a determina anumite marimi specifice cum ar fi : gradul unui varf

Ferestre mesajSe deschid in urma realizarii unei anumite sarcini de catre

elev sau in urma comiterii unei greseli de catre elev. In aceasta fereastra se indica subiectului aprecierea rezultatului sau/si se dau eventual informatii suplimentare.

Buton de pauza Prin accesarea acestui buton se opreste animatia pentru a observa mai multe detalii.

Fereastra de detaliiAceasta fereastra ofera informatii suplimentare sau detalii

despre un anumit element, termen, concept, imagine, personalitati, etc.)

2. Informatii generale pentru tema prezentataProdusul informatic realizat ofera posibiliatea includerii in

didactica de predare a teoriei grafurilor, a unor mijloace de invatare si comunicare performante, prin utilizarea calculatorului.

In acest mod procesul de predare – invatare este "personalizat", pentru fiecare elev in parte, avand in vedere particularitatile psiho-individuale si psiho-sociale ale acestuia.

In cadrul temei tratate – grafuri – notiuni introductive – au fost puse in evidenta urmatoarele aspecte :

Definirea notiunii de graf , cu accent pe problemele practice care se pot reprezenta prin grafuri ;

Prezentarea terminologiei legate de teoria grafurilor si antrenarea elevului in intelegera acesteia odata cu formarea unui vocabular de specialitate. ;

Folosirea unor metode activ – participative de tip "joc " pentru implicarea afectiva a elevului in procesul de invatare ;

Adaptarea lectiei la ritmul de invatare, atentiei si oboselii fiecarui subiect

Cuvintele cheie la aceasta tema sunt : graf, incidenta , grad, graf complet, graf bipartit, graf conex, lant.

Materialul are o structura modulatizata, care permite folosirea in mai multe variante a instrumentelor puse la dispozitie.

Momentele de evaluare faciliteaza munca profesorului in realizarea unui feedback continuu, permanent, corectiv.3. Obiective

Obiectiv DetaliereCompetente generale

CG1 Definirea si recunoasterea conceptelor specifice teoriei grafurilor.

CG2 Folosirea corecta a rationamentelor si algoritmilor de rezolvare a unor probleme care utilizeaza teoria

grafurilor.CG3 Elaborarea de algoritmi complecsi care folosesc

teoria grafurilor.CG4 Intelegera cunostintelor si metodelor din teoria

grafurilor in rezolvarea unor probleme cu aplicatie practica.

Competente specifice

CS1 Identificarea unor notiuni specifice si terminologii utilizate in teoria grafurilor.

CS2 Exemplificarea pe baza unor probleme cunoscute, a termenilor legati de teoria grafurilor.

CS3 Cunoasterea si intelegera proprietatilor specifice diverselor tipuri de grafuri.

CS4 Prelucrarea datelor de tip calitativ si cantitativ cuprinse in problemele care se rezolva prin teoria grafurilor

Obiective OperationaleOP1 Sa defineasca notiunea de graf , precum si terminologia

corespunzatoare.OP2 Sa identifice si sa recunoasca un graf neorientat,

proprietatile acestuia si aplicabilitatea practica a grafurilorOP3 Sa reprezinte graful neorientat al unei probleme practice

in care trebuie sa distinga caracteristicile esentiale si sa aplice teoreme specifice.

OP4 Sa aplice notiunile de teoria grafurilor in situatii ‘problema’ create prin intermediul unor jocuri

atractive si captivanteOP5 Sa poata rezolva probleme in care grafurile neorientate au

anumite proprietati

4. Structura generala4.1 Continut

Se prezinta lista obiectelor de continut (notate cu M ) si carateristicile lor generale .

M1 –Introducere – Drumul lui Napoleon - jocObiective didactice OP1, OP2

Timp 5 minuteTip de interactiune cu

elevulExercitiu, problematizare, descoperire

Descriere -prin acest joc elevul este pus in fata unei probleme cunoscute, care-l determina sa caute in graful prezentat un drum intre Nancy si Viena in care Napoleon sa piarda cat mai putini soldati.

M2 – Constructie – Istoricul grafurilor

Obiective diactice OP1, OP3, OP4Timp 15 minute

Tip de interactiune cu elevul

Expunere, observare, problematizare, modelare, simulare

Descriere -este prezentata intr-o forma atractiv-captivanta problema celor sapte poduri din orasul Kaliningrad-se defineste notiunea de graf si se dau cateva exemple-se verifica interactiv modul de intelegere al notiunii de graf neorientat

M4- Graf partialObiective diactice OP2, OP3, OP4, OP5

Timp 6 minuteTip de interactiune cu elevul Problematizare, descoperire, exercitiu ,

M3 – IncidentaObiective diactice OP2, OP3, OP4

Timp 15 minuteTip de interactiune cu

elevulObservare, problematizare , modelare, simulare

Descriere -prin jocul prezentat se insista asupra reprezentarii sub forma de graf neorienat a unei prbleme practice-elevul este condus spre notiunea de incidenta-in interactiunea cu calculatorul elevul particpa activ la intelegerea notiunii de grad al unui varf

modelare si simulareDescriere - modulul contine un joc prin care este

pusa in evidenta o succesiune de operatii mentale care duc elevul spre intelegerea clara a notiunii de graf

partial;- se prezinta elevului sub o forma atractiva si animata notiunea de graf

partial.

M5 – SubgrafObiective diactice OP2, OP3, OP4, OP5

Timp 10 minuteTip de interactiune cu elevul Problematizare, descoperire, exercitu,

modelare si simulare

Descriere - modulul contine un joc prin care elevul este condus spre construirea unui

subgraf al unui graf dat, intr-o problema practica.

- In continuare elevului i se explica partea tehnica a notiunii de subgraf pe care l-a

intalnit deja la jocul anterior

-M6 – Graf bipartite

Obiective diactice OP2, OP3, OP4, OP5Timp 6 minute

Tip de interactiune Problematizare, descoperire, exercitu, modelare si simulare

Descriere - modulul este interactiv- pe baza unei scheme elevul este condus spre

notiunea de graf bipartit- dupa realizarea cerintei se dau detalii asupra

teoriei.

M7 – Graf completObiective diactice OP2, OP3, OP4, OP5

Timp 8 minuteTip de interactiune

cu elevulproblematizare, descoperire, exercitiu, modelare si simulare

Descriere -este un modul interactiv de tip joc-prin acest joc elevul descopera notiunea de graf complet-se trece la o pagina de continut care pune bazele teoretice ale grafului complet

4.2. Recomandari de structurare si predareImbinarea modulelor realizate pentru aceasta lectie este la

latitudinea fiecarui profesor, in functie de particularitatile psiho-individuae ale clasei.

1. Lectia 1 (Notiuni introductive in teoria grafurilor)Obiect de continut Timp (minute)

M1 5 minuteM2 15 minuteM3 15 minute

Test 1 10 minuteTema 1 5 minute

2. Lectia 2 (Tipuri de grafui)Obiect de continut Timp (minute)

M4 6 minuteM5 10 minuteM6 6 minuteM7 8 minuteM8 5 minute

Test 2 10 minuteTema 2 5 minute

5. Stuctura detaliata a contnutului

M3 – Graf conexObiective diactice OP2, OP3, OP4, OP5

Timp 5 minuteTip de interactiune cu

elevulproblematizare, descoperire, exercitiu,

modelare si simulareDescriere - notiunea de graf conex este

introdusa prin intermediul unui joc care mentine o interactiune

permanenta a elevului cu calculatorul

5.1. Introducere – Drumul lui NapoleonEste un obiect interactiv care se prezinta sub forma de joc .

Elevul trebuie sa gaseasca drumul pe care trebuie sa-l parcurga Napoleon din orasul Nancy pana la Viena. Se stie cati soldati poate pierde Napoleon daca parcurge un traseu sau altul.

Se cere elevului sa determine drumul dintre Nancy si Viena astfel incat sa se piarda un numar minim de soldati. Este un exemplu practic de utilizare a grafurilor.

Folosind butonul (resetare) jocul poate fi reluat.Prin parcurgerea acestui modul se pune in evidenta o

succesiune de operatii mintale care conduc elevul la descoperirea notiunii de graf.

5.2. Constructie –Istoricul grafurilorAcest obiect familiarizeaza elevul cu notiunea de graf.

Obiectul este interactiv si se prezinta pentru inceput sub forma unui joc “problema celor sapte poduri din orasul Kaliningrad”.

Aceasta problema celebra a fost enuntata de matematicianul Euler, care impreuna cu Hamilton au fost cei care au pus bazele teoriei grafurilor. Punand mouse-ul pe cuvintele Euler si respectiv Hamilton se deschide o fereasta in care elevul afla mai multe detalii despre cei doi matematicieni.

In partea de jos a ecranului , prin apasarea pe cuvintele Legile lui Kirchoff si respectiv reprezentarea unor harti se face link la doua pagini distincte care dau explicatii asupra unor aplicatii practice a teoriei grafurilor.

In partea de jos a ecranului, dreapta, se afla doua butoane importante:

Definitie – prin accesarea acestui buton se trece la prezentarea definitiei notiunii de graf. Animatia folosita conduce si mai bine la intelegerea acestei definitii. In acest moment in patea

de jos a ecranului exista doua butoane care au semnificatia ( )

inainte, respectiv ( ) inapoi.

Constructie – prin accesarea acestui buton se trece la constructia interactiva a unui graf cu noduri si muchii prestabilite Elevul are la dispozitie trei ferestre de meniuri cu care construieste nodurile, muchiile si verfica , respectiv reseteaza, rezolvarea cerintei, daca aceasta s-a facut gresit , sau daca elevul doreste sa reia problema.

5.3. IncidentaAcest modul este interactiv. In definirea notiunilor

elementare legate de graf , se pleaca de la un joc, pe care elevul il are descris in partea stanga-sus a ecranului.

Prin participarea efectiva a elevului la rezolvarea jocului acesta se familiarizeaza cu notiunile teoriei grafurilor: incidenta, grad, adiacenta.

In partea de jos-dreapta a ecranului se afla doua butoane:

-La accesarea acestui buton se dau explicatii legate de gradul unui graf. In acelasi context este enuntata o teorema a carei demonstratie este data prin accesarea butonului

.

- La accesarea acestui buton se dau explicatii legate de notiunile de adiaenta, incidenta.

5.4. Graf partialAcest obiect este interactiv si are ca scop familiarizarea

elevului cu notiunea de graf partial.Pentru antrenarea optima a elevului la insusirea cunostintelor,

modulul incepe cu un “joc – problema “ care cere determinarea unui graf partial obtinut prin eliminarea unui numar optim de muchii astfel incat un turist sa poata vizita oricare cabana.

Folosind aceasta metoda activ-participativa , elevul nu asimileaza “mecanic” notiunea, ci beneficiaza direct de intelegerea logica a ei.

In continuare se prezinta partea teoretica a notiunii de graf partial. Elevul poate interactiona cu aplicatia folosind butoanele

prezente in partea de sus a ecranului, stabilindu-se un ritm propriu de intelegre.

5.5 SubgrafEste un obiect interactiv de tip “joc”, care-l determina pe elev

sa caute, sa investigheze si sa descopere un subgraf.

Acesta este o prezentare animata care , obsevata cu atentie , in ritmul de intelegere al elevului, pune bazele teoretice si practice ale notiunii de subgraf.

5.6 Graf Bipartit Este un moment de tip exercitiu interactiv care pune elevul in situatia de a construi un graf

Dupa rezolvarea exercitiului, se trece la partea teoretica a acestuia, definindu-se riguros notiunea de graf bipartit.

5.7 Graf completPrin parcurgerea acestui modul, elevul se familiarizeaza cu

notiunea de graf complet.Obiectul acesta de continut este interactiv si contine un joc.

Elevul are posibilitatea sa verifice daca rezolvarea cerintei este

corecta sau nu prin intermediul a doua butoane : si

.

Dupa incheierea jocului se trece la o noua pagina de continut unde se explica elevului notiunea de graf complet si proprietatile acestuia.

5.8 Graf conexAcest obiect de continut are rolul de a defini notiunea de graf

conex. Este un modul interactiv care demareaza cu un joc interactiv si captivant. Jocul poate fi reluat folosind butonul

sau elevul poate sa-si verifice modul de rezolvare a

cerintei folosind butonul .

In final, dupa incheierea jocului, se deschide o fereastra care

aminteste elevului notiunea de graf conex.

5. Tema pentru acasatema11. Reprezentaţi grafic toate grafurile neorientate cu 3 noduri;2. Să se calculeze numărul grafurilor neorientate cu n vârfuri date;3. Să se demonstreze că orice graf neorientat are un număr par de vârfuri cu grad impar;4. Determinaţi un graf G=(X,U) cu 5 noduri astfel încăt oricare două vârfuri a,bX, a <>b să fie adiacente.

tema21. Determinaţi numărul nodurilor corespunzătoare unui graf neorientat complet cu 36 de muchii;

2. Să se demonstreze că un poligon convex cu n vârfuri are diagonale;

3. Fiind dat un graf G neorientat cu n vârfuri si m muchii cu m> , să se demonstreze că G nu are vârfuri izolate;4. Graful G=(X,U) se numeşte bipartit complet dacă între orice vârf Xi din A şi orice vârf Xk din B există muchia [Xi,Xk]. Pentru un graf bipartit complet, pentru care mulţimea A are p elemente si mulţimea B are q elemente, să se determine numărul total de muchii.

6. Teste de evaluare

Test1

1. Apreciaţi prin adevarat sau fals următoarea afirmaţie:

Într-un graf neorientat, o muchie u este o pereche ordonata de noduri din X AdevaratFalsraspuns corect : fals

2. Fiind dată următoarea reprezentare grafică pentru un graf neorientat, atunci pentru graful G=(X,U), mulţimile X şi U sunt:

a) X={1,2,3,4,5}

U={[1,2];[1,3];[2,3];[2,4];[2,5];[2,6];[3,4]}

b) X={1,2,3,4,5,6}

U={[1,2];[1,3];[2,4];[2,5];[2,6];[2,3];[3,4]}

c) X={1,2,3,4,5,6}

U={[1,2];[1,3];[2,4];[2,5];[5,6];[2,3]}

d) X={1,2,3,4,5,6}

U={[1,2];[1,3];[2,4];[2,5];[2,6];[2,3];[4,5]}raspuns corect b)

3. Precizaţi care din următoarele noţiuni se referă la grafuri neorientate:a) muchie

b) arcc) legătură d) punct final

4. Apreciaţi cu adevărat sau fals următoarea afirmaţie:

Două muchii sunt incidente dacă au o extremitate comună.AdevaratFalsraspuns corect : Adevarat

5. Apreciaţi cu adevărat sau fals următoarea afirmaţie:

Un nod izolat are gradul 1.AdevaratFalsraspuns: fals

6. Apreciaţi cu adevărat sau fals următoarea afirmaţie:

Un nod terminal are gradul 1.AdevaratFalsraspuns: Fals

7. Un nod este nod terminal dacă:a) nu există muchii incidente cu elb) este incident cu o singură muchiec) este izolat în graful neorientat raspuns : b

8. Un nod este nod izolat intr-un graf neorientat dacă:a) este nod terminal in grafb) nu există muchii incidente cu elc) există cel puţin o muchie incidentă cu elraspuns : b)

9. Determinaţi răspunsurile corecte pentru graful din figura alăturată:a) nodul 1 are gradul 2b) nodul 2 are gradul 4c) nodul 3 are gradul 3d) nodul 5 este nod terminale) nodul 6 este nod izolatraspuns :a,c,d10. Care este suma gradelor vârfurilor unui graf neorientat cu n vârfuri si m muchii?a) 2*m

b) 2*(m-1)c) 2*nd) m raspuns a)Test2

1. Într-un graf neorientat G=(X,U):

Într-un graf neorientat, o muchie u este o pereche ordonata de noduri din X a) Un graf parţial al său se obţine prin suprimarea unor vârfurib) Un subgraf se obţine prin suprimarea unor muchiic) Un graf parţial al său este se obţine prin suprimarea unor muchiid) Orice graf parţial este subgraf al grafului Graspuns corect c)

2. Se consideră graful definit prin mulţimile X={1,2,3,4,5} şi U={[1,2] ;[1,3] ;[2,3];[2,4];[3,4];[4,5]}. Eliminând muchiile [1,2] şi [3,4] se obţine:a) Un subgraf definit prin X={5}b Un graf parţial definit prin X şi U={[1,3];[2,3];[2,4];[3,4];[4,5]}c) Un graf parţial definit prin X şi U={[1,2];[3,4]}d) Un subgraf definit prin X şi restul muchiilore) Un graf parţial definit prin X şi restul muchiilor

raspuns corect e)

3. Un graf neorientat G complet cu n noduri are proprietatea:a) Conţine noduri izolate

b) Are n*m muchiic) Oricare două noduri distincte sunt adiacente d) Conţine noduri terminaleraspuns c)

4. Care este numărul total al muchiilor unui graf neorientat complet cu n vârfuri?:

a) nb) n*(n-1)/2c) n*(n-1)d) 2*nraspuns b)

5. Un graf complet are 15 muchii. Câte noduri are?:

a) 10b) 6 c) 5

d) 12raspuns b)

6. Fie graful neorientat G=(X,U) cu X={1,2,3,4,5} şi U={[1,2];[2,3];[1,5];[1,4];[2,5];[3,4];[4,5]}. Dacă se elimină muchiile [1,2], [3,4] şi [4,5] se obţine:

a) Un graf parţial al grafului iniţialb) Un  subgraf al grafului iniţialc) Un graf completd) Un graf bipartitraspuns : a,d

7. Fie graful neorientat G=(X,U) cu X={1,2,3,4,5,6} şi U={[1,2];[2,3];[3,4];[4,5];[5,6];[6,1];[1,3];[1,5];[2,5];[3,5]}. Care este numărul maxim de muchii ce se pot elimina astfel încât graful să rămână conex?a) 8b) 4c) 5d) 6raspuns : c

8. Fie graful neorientat G=(X,U), X={1,2,3,4,5,6}, U={[1,2];[1,3];[2,3];[4,5]}. Care este numărul minim de muchii care trebuiesc adăugate grafului pentru a deveni conex?a) Nici una, graful este conex;b) 3c) 2raspuns : c)

9. Fie G=(X,U) unde X este mulţimea nodurilor iar U este mulţimea muchiilor. Graful din dreapta este:a) Un graf completb) Un subgraf al grafului datc) Un graf parţial al grafului datd) Un graf bipartit complet raspuns :a,b10. Care Un graf neorientat G=(X,U) este conex dacă:a) Între oricare două vârfuri a,b din X, a<>b, există o muchie;b) Între oricare două vârfuri a,b din X, a<>b, există lanţ;c) Nu conţine vârfuri izolate.raspuns b)

7. BIBLIOGRAFIE

1. N. Nedita , St Niculescu, C. Zidaroiu Matematici aplicate la tehnici de calcul.Editura didactica si pedagogica , Bucuresti 1979

2. C. Achinca, A. Breaz , A. Demco , M. Gradinescu, D. Grigoriu , L. Toca, C. Balanescu, R. Motruna , Bacalaureat Informatica teste grila , Editura Nedion , Bucuresti, 2003

3. M. Gheorghe , C . Golli , Roxana Carmen Marin , I. Oprea , Informatica , Editura Corint , Bucuresti 2003

4. I . Tomescu , A. Leu , Matemtica aplicata in tehnica de calcul, Editura Didactica si Pedagogica Bucuresti 1982

5. G. D. Mateescu , P. F. Moraru , Informatica pentru clasa a XI-a , Editura Niculescu 2003

6. C. Ivasc , M. Pruna Bazele informaticii , Editura Petrion , Bucuresti

7. I. Tomescu , Grafuri si programare liniara , Editura Didactica si Pedagogica Bucuresti , 1975

8. T. Sorin , Tehnici de programare ., Editura Teora , Bucuresti 1994

9. L Toca , A. Demco , C. Opincaru , A. Sindile, Informatica – manual pentru clasa a X-a , Editura Niculescu , Bucuresti 2000