Clasa a XI-a

GRAFURI NOTIUNI INTRODUCTIVE Manualul profesorului

CONCEPTIE SI IMPLEMENTARE:

CORINA ACHINCA CECILIA BALANESCU RODICA CHERCIU SORIN STEFLEA CIPRIAN CONSTANTIN

Cuprins

1. Terminologie 2. Informatii generale despre tema prezentata 3. Obiective 4. Structura generala

4.1 Continut 4.2 Recomandari de structurare si predare

5. Structura detaliata a continuturilor 5.1 Introducere – Drumul lui Napoleon 5.2 Constructie – Istoricul grafurilor 5.3 Incidenta 5.4 Graf partial 5.5 Subgraf 5.6 Graf bipartit 5.7 Graf complet 5.8 Graf conex

6. Teste de evaluare 7. Teme pentru acasa 8. Bibliografie

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

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

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

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

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 meniuri Sunt 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 mesaj Se 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 detalii Aceasta fereastra ofera informatii suplimentare sau detalii despre un anumit element, termen, concept, imagine, personalitati, etc.)

2. Informatii generale pentru tema prezentata Produsul 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 Detaliere

Competente 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 Operationale OP1 Sa defineasca notiunea de graf , precum si

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

proprietatile acestuia si aplicabilitatea practica a grafurilor

OP3 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 captivante

OP5 Sa poata rezolva probleme in care grafurile neorientate au anumite proprietati

4. Structura generala 4.1 Continut Se prezinta lista obiectelor de continut (notate cu M ) si carateristicile lor generale .

M1 –Introducere – Drumul lui Napoleon - joc Obiective didactice OP1, OP2

Timp 5 minute Tip de interactiune cu

elevul Exercitiu, 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, OP4 Timp 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

M3 – Incidenta Obiective diactice OP2, OP3, OP4

Timp 15 minute Tip de interactiune cu

elevul Observare, 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

M4- Graf partial Obiective diactice OP2, OP3, OP4, OP5

Timp 6 minute Tip de interactiune cu

elevul Problematizare, descoperire, exercitiu ,

modelare si simulare Descriere - 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 – Subgraf Obiective diactice OP2, OP3, OP4, OP5

Timp 10 minute Tip 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, OP5 Timp 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 complet Obiective diactice OP2, OP3, OP4, OP5

Timp 8 minute Tip de interactiune cu

elevul problematizare, 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

M3 – Graf conex Obiective diactice OP2, OP3, OP4, OP5

Timp 5 minute Tip de interactiune cu

elevul problematizare, descoperire, exercitiu,

modelare si simulare Descriere - notiunea de graf conex este

introdusa prin intermediul unui joc care mentine o interactiune

permanenta a elevului cu calculatorul

4.2. Recomandari de structurare si predare Imbinarea 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 minute M2 15 minute M3 15 minute

Test 1 10 minute Tema 1 5 minute

2. Lectia 2 (Tipuri de grafui)

Obiect de continut Timp (minute)

M4 6 minute M5 10 minute M6 6 minute M7 8 minute M8 5 minute

Test 2 10 minute Tema 2 5 minute

5. Stuctura detaliata a contnutului 5.1. Introducere – Drumul lui Napoleon Este 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 grafurilor Acest 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. Incidenta Acest 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:

Grad

-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

.

Incidenta - La accesarea acestui buton se dau explicatii legate

de notiunile de adiaenta, incidenta. 5.4. Graf partial Acest 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 Subgraf Este 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 bipartit.

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

5.7 Graf complet Prin 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 : Verificare

si Resetare .

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 conex Acest 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

Resetare sau elevul poate sa-si verifice modul de rezolvare a cerintei folosind butonul Verificare

.

In final, dupa incheierea jocului, se deschide o fereastra care aminteste elevului notiunea de graf conex.

5. Tema pentru acasa tema1 1. 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,b X, a <>b să fie adiacente tema2 1. 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 2

)3( ?nn

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 Adevarat Fals raspuns 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) arc c) 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ă. Adevarat Fals raspuns corect : Adevarat

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

Un nod izolat are gradul 1. Adevarat Fals raspuns: fals

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

Un nod terminal are gradul 1. Adevarat Fals raspuns: Fals 7. Un nod este nod terminal dacă: a) nu există muchii incidente cu el b) este incident cu o singură muchie c) este izolat în graful neorientat raspuns : b 8. Un nod este nod izolat intr-un graf neorientat dacă: a) este nod terminal in graf b) nu există muchii incidente cu el c) există cel puţin o muchie incidentă cu el raspuns : b)

9. Determinaţi răspunsurile corecte pentru graful din figura alăturată: a) nodul 1 are gradul 2 b) nodul 2 are gradul 4 c) nodul 3 are gradul 3 d) nodul 5 este nod terminal e) nodul 6 este nod izolat raspuns :a,c,d 10. 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*n d) 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ârfuri b) Un subgraf se obţine prin suprimarea unor muchii c) Un graf parţial al său este se obţine prin suprimarea unor muchii d) Orice graf parţial este subgraf al grafului G raspuns 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 muchiilor e) 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 muchii c) Oricare două noduri distincte sunt adiacente d) Conţine noduri terminale raspuns c)

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

a) n

b) n*(n-1)/2 c) n*(n-1) d) 2*n raspuns b)

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

a) 10

b) 6 c) 5 d) 12 raspuns 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ţial b) Un subgraf al grafului iniţial c) Un graf complet d) Un graf bipartit raspuns : 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) 8 b) 4 c) 5 d) 6 raspuns : 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) 3 c) 2 raspuns : 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 complet b) Un subgraf al grafului dat c) Un graf parţial al grafului dat d) Un graf bipartit complet raspuns :a,b 10. 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