VII. Aplicaţii metodico-practice
1. Lecție mixtă - Componente conexe
Unitatea de învăţare: Conexitate
Subiectul lecţiei: Componente conexe.
Tipul lecţiei : mixtă (sistematizarea şi consolidarea achiziţiilor referitoare la definiția conexității și parcurgerea grafurilor în adâncime. Transferul de noi cunoştinţe prin însuşirea noțiunii de componentă conexă, elaborarea și implementarea algoritmului de aflare a componentelor conexe, verificarea și evaluarea performanţei şcolare).
Subiectul lecţiei: Componente conexe.
Tipul lecţiei : mixtă (sistematizarea şi consolidarea achiziţiilor referitoare la definiția conexității și parcurgerea grafurilor în adâncime. Transferul de noi cunoştinţe prin însuşirea noțiunii de componentă conexă, elaborarea și implementarea algoritmului de aflare a componentelor conexe, verificarea și evaluarea performanţei şcolare).
Fișa de lucru nr.1
1. Să se determine componentele conexe ale unui graf neorientat reprezentat prin matricea de adiacență. Datele se citesc din fișierul de intrare comp_conex.in și rezultatele se scriu în fișierul comp_conex.out.
Fișa de lucru nr. 2
1. Din grupul de n persoane între care s-au stabilit relații de prietenie și de vecinătate, determinați grupurile de prieteni, grupurile de vecini și grupurile de prieteni vecini.
Indicație: Relațiile de prietenie și relațiile de vecinătate se reprezintă prin două grafuri neorientate. Grupurile de prieteni și grupurile de vecini se stabilesc aflând componentele conexe ale celor două grafuri iar grupurile de prietenie și vecinătate prin aflarea componentelor conexe ale grafului intersecție (în graful intersecție există o muchie între i și j dacă în graful prieteniei și în graful vecinătăților există o muchie între i și j).
2. În rețeaua de străzi a orașului (presupunem că nu există străzi cu sens unic), un număr de p străzi se închid pentru a fi reparate. Etichetele intersecțiilor care sunt legate de aceste străzi se citesc de la tastură. Să se verifice dacă prin închiderea acestor străzi nu se izolează unele zone ale orașului de alte zone.
Indicație: Se generează graful parțial al grafului, prin eliminarea muchiilor dintre nodurile precizate și se verifică dacă graful obținut este conex.
1. Să se determine componentele conexe ale unui graf neorientat reprezentat prin matricea de adiacență. Datele se citesc din fișierul de intrare comp_conex.in și rezultatele se scriu în fișierul comp_conex.out.
Fișa de lucru nr. 2
1. Din grupul de n persoane între care s-au stabilit relații de prietenie și de vecinătate, determinați grupurile de prieteni, grupurile de vecini și grupurile de prieteni vecini.
Indicație: Relațiile de prietenie și relațiile de vecinătate se reprezintă prin două grafuri neorientate. Grupurile de prieteni și grupurile de vecini se stabilesc aflând componentele conexe ale celor două grafuri iar grupurile de prietenie și vecinătate prin aflarea componentelor conexe ale grafului intersecție (în graful intersecție există o muchie între i și j dacă în graful prieteniei și în graful vecinătăților există o muchie între i și j).
2. În rețeaua de străzi a orașului (presupunem că nu există străzi cu sens unic), un număr de p străzi se închid pentru a fi reparate. Etichetele intersecțiilor care sunt legate de aceste străzi se citesc de la tastură. Să se verifice dacă prin închiderea acestor străzi nu se izolează unele zone ale orașului de alte zone.
Indicație: Se generează graful parțial al grafului, prin eliminarea muchiilor dintre nodurile precizate și se verifică dacă graful obținut este conex.
2. Lecție de evaluare - Reprezentarea grafurilor neorientate
Subiectul lecţiei: Reprezentarea grafurilor neorientate prin matricea de adiacență.
Tipul lecţiei : lecție de evaluare (verificare și apreciere a cunoștințelor acumulate în unitatea de învățare ” Reprezentarea şi parcurgerea grafurilor”).
Fișa de lucru
1. Scrieți programul C++ care realizază următoarele:
a. Crearea matricei de adiacenţă a unui graf neorientat, prin citirea ei din fişierul matrice_n.in .
b. Determinarea numărului de vecini ai tuturor nodurilor.
c. Afişarea muchiilor grafului.
Tipul lecţiei : lecție de evaluare (verificare și apreciere a cunoștințelor acumulate în unitatea de învățare ” Reprezentarea şi parcurgerea grafurilor”).
Fișa de lucru
1. Scrieți programul C++ care realizază următoarele:
a. Crearea matricei de adiacenţă a unui graf neorientat, prin citirea ei din fişierul matrice_n.in .
b. Determinarea numărului de vecini ai tuturor nodurilor.
c. Afişarea muchiilor grafului.
Test de evaluare - Timp de lucru: 5 min.
1. Se consideră graful neorientat dat prin matricea de adiacență alăturată. Să se determine câte perechi de noduri neadiacente există în graf ?
a. 1 b. 2 c. 3 d. 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
2. Pentru graful complet K5 numărul de elemente egale cu 0, din matricea de adiacență este:
a. 0 b. 2 c. 5 d. 3
Următorii itemi se referă la graful neorientat cu 8 noduri, având muchiile: [1,2] [1,3], [1,4], [1,5], [2,3],[3,4],[3,7],[4,7],[4,5].
3. Numărul de noduri care au gradul maxim este:
a. 1 b. 2 c. 4 d. 3
4. Numărul de noduri izolate este:
a. 1 b. 2 c. 5 d. 0
5. Numărul de elemente egale cu 1 de pe linia 4 din matricea de adiacență este:
a. 0 b. 6 c. 4 d. 3
6. Numărul de elemente egale cu 0 de pe diagonala principală, din matricea de adiacență, este:
a. 8 b. 5 c. 4 d. 1
7. Gradul maxim al tuturor nodurilor din graf este :
a. 8 b. 0 c. 4 d. 3
8. Gradul minim al tuturor nodurilor din graf este :
a. 1 b. 0 c. 4 d. 3
9. Numărul de elemente, din matricea de adiacență, egale cu simetricul lor față de diagonala principală, este:
a. 15 b. 28 c. 56 d. 35
Notă
Se acordă un punct din oficiu și pentru fiecare răspuns corect se acordă 1 punct.
Pentru testul de evaluare, răspunsurile corecte sunt:
1. Se consideră graful neorientat dat prin matricea de adiacență alăturată. Să se determine câte perechi de noduri neadiacente există în graf ?
a. 1 b. 2 c. 3 d. 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
2. Pentru graful complet K5 numărul de elemente egale cu 0, din matricea de adiacență este:
a. 0 b. 2 c. 5 d. 3
Următorii itemi se referă la graful neorientat cu 8 noduri, având muchiile: [1,2] [1,3], [1,4], [1,5], [2,3],[3,4],[3,7],[4,7],[4,5].
3. Numărul de noduri care au gradul maxim este:
a. 1 b. 2 c. 4 d. 3
4. Numărul de noduri izolate este:
a. 1 b. 2 c. 5 d. 0
5. Numărul de elemente egale cu 1 de pe linia 4 din matricea de adiacență este:
a. 0 b. 6 c. 4 d. 3
6. Numărul de elemente egale cu 0 de pe diagonala principală, din matricea de adiacență, este:
a. 8 b. 5 c. 4 d. 1
7. Gradul maxim al tuturor nodurilor din graf este :
a. 8 b. 0 c. 4 d. 3
8. Gradul minim al tuturor nodurilor din graf este :
a. 1 b. 0 c. 4 d. 3
9. Numărul de elemente, din matricea de adiacență, egale cu simetricul lor față de diagonala principală, este:
a. 15 b. 28 c. 56 d. 35
Notă
Se acordă un punct din oficiu și pentru fiecare răspuns corect se acordă 1 punct.
Pentru testul de evaluare, răspunsurile corecte sunt:
3. Lecție de transmitere și însușire de noi cunoștințe - APM
Unitatea de învăţare: Arbori
Subiectul lecţiei: Arbori parțiali de cost minim.
Fisa lucru nr. 1
1. N localități trebuie unite într-o rețea informațională astfel încât informația transmisă dintr-o localitate A să poată fi recepționată în orice altă localitate printr-un canal de legatură directă sau prin intermediul altor centre (localități), cu condiția ca lungimea totală a acestei rețele să fie minimă. Se știe că între oricare două localități din punct de vedere fizic este posibilă, trasarea unui canal de legatură informațională.
Indicație: În această situație localitățile pot fi considerate drept vârfuri ale unui graf complet Kn în care fiecare muchie are o pondere egală cu lungimea canalului de legatură directă dintre centrele respective. Atunci rețeaua informațională cautată va fi un arbore parțial de cost minim al grafului Kn.
Subiectul lecţiei: Arbori parțiali de cost minim.
Fisa lucru nr. 1
1. N localități trebuie unite într-o rețea informațională astfel încât informația transmisă dintr-o localitate A să poată fi recepționată în orice altă localitate printr-un canal de legatură directă sau prin intermediul altor centre (localități), cu condiția ca lungimea totală a acestei rețele să fie minimă. Se știe că între oricare două localități din punct de vedere fizic este posibilă, trasarea unui canal de legatură informațională.
Indicație: În această situație localitățile pot fi considerate drept vârfuri ale unui graf complet Kn în care fiecare muchie are o pondere egală cu lungimea canalului de legatură directă dintre centrele respective. Atunci rețeaua informațională cautată va fi un arbore parțial de cost minim al grafului Kn.
Tema pentru acasă
Rezolvați următoarea problemă: La o firmă se fac renovări. O dată cu aceste renovări se doreşte să optimizeze şi reţeaua intranet a firmei. La dispoziţia specialiştilor este pus un plan pe care sunt marcate calculatoarele firmei. De asemenea sunt marcate calculatoarele între care se poate pune cablu precum şi costul necesar operaţiei. Trebuie să determinăm o modalitate de a conecta calculatoarele astfel încât costul total să fie minim.
Rezolvați următoarea problemă: La o firmă se fac renovări. O dată cu aceste renovări se doreşte să optimizeze şi reţeaua intranet a firmei. La dispoziţia specialiştilor este pus un plan pe care sunt marcate calculatoarele firmei. De asemenea sunt marcate calculatoarele între care se poate pune cablu precum şi costul necesar operaţiei. Trebuie să determinăm o modalitate de a conecta calculatoarele astfel încât costul total să fie minim.
4. Lecție de recapitulare - Conexitatea grafurilor
Unitatea de învățare : Conexitatea grafurilor
Subiectul lecţiei: Conexitatea grafurilor.
Subiectul lecţiei: Conexitatea grafurilor.
Material anexat:
Fișa de evaluare
Proiect, Conexitatea grafurilor
Informatică – Clasa a XI-a
Evaluare pentru grupa numărul.……făcută de către grupa numărul.……
Tema proiectului…………………………………………
Fișa de evaluare
Proiect, Conexitatea grafurilor
Informatică – Clasa a XI-a
Evaluare pentru grupa numărul.……făcută de către grupa numărul.……
Tema proiectului…………………………………………