=INFORMATICA==INFORMATICA=GRAFURI GRAFURI

NEORIENTATENEORIENTATE

Prof. BRIA MONICA Prof. BRIA MONICA

CConţinuturionţinuturi Graf neorientat, adiacenţă, Graf neorientat, adiacenţă, incidenţă, gradincidenţă, grad((manual pentru clasa a manual pentru clasa a XI-a, G.D. Mateescu, Ed. Niculescu, XI-a, G.D. Mateescu, Ed. Niculescu, 2001).2001).

Reprezentarea grafurilor Reprezentarea grafurilor neorientate (Informaticneorientate (Informatică, M. ă, M. Gheorghe, Ed. Corint, Bucureşti Gheorghe, Ed. Corint, Bucureşti 2003)2003)..Noţiunile de graf parţial şi subgrafNoţiunile de graf parţial şi subgraf (Informatic(Informatică, M. Gheorghe, Ed. ă, M. Gheorghe, Ed. Corint, Bucureşti 2003):Corint, Bucureşti 2003):

PrefaţăPrefaţăDisciplina informatică cuprinde în ansamblul Disciplina informatică cuprinde în ansamblul ei unitatea de învăţare „Grafuri ei unitatea de învăţare „Grafuri neorientate”. În cadrul acestei unităţi de neorientate”. În cadrul acestei unităţi de învăţare elevii vor înţelege utilitatea învăţare elevii vor înţelege utilitatea grafurilor în rezolvarea problemelor practice grafurilor în rezolvarea problemelor practice (din lumea înconjurătoare). Multitudinea de (din lumea înconjurătoare). Multitudinea de probleme ce apar zilnic în activitatea probleme ce apar zilnic în activitatea noastră cotidiană îşi găsesc răspuns în noastră cotidiană îşi găsesc răspuns în teoria grafurilor. Pornind de la orientarea teoria grafurilor. Pornind de la orientarea noastră în spaţiu până la realizarea de noastră în spaţiu până la realizarea de enciclopedii, dicţionare, articole, etc. Au la enciclopedii, dicţionare, articole, etc. Au la bază însuşirea temeinică a noţiunii de graf.bază însuşirea temeinică a noţiunii de graf.

Standarde de performanţă - Standarde de performanţă - obiective de referinţăobiective de referinţă şi şi competenţe competenţe

specificespecifice

1. Identificarea conexiunilor dintre unitatea de 1. Identificarea conexiunilor dintre unitatea de învăţare studiată şi societate.învăţare studiată şi societate.2. Identificarea datelor care intervin într-o problemă 2. Identificarea datelor care intervin într-o problemă şi a relaţiilor dintre acestea.şi a relaţiilor dintre acestea.3. Elaborarea algoritmilor simpli de verificare a 3. Elaborarea algoritmilor simpli de verificare a însuşirii terminologiei sau de verificare a unor însuşirii terminologiei sau de verificare a unor proprietăţi specifice grafurilor (de exemplu, proprietăţi specifice grafurilor (de exemplu, calcularea gradelor vârfurilor unui graf, verificarea calcularea gradelor vârfurilor unui graf, verificarea faptului că o succesiune de vârfuri reprezintă lanţ, faptului că o succesiune de vârfuri reprezintă lanţ, drum, ciclu sau circuit în graf etc.).drum, ciclu sau circuit în graf etc.).4. Rezolvarea unor probleme practice, care solicită 4. Rezolvarea unor probleme practice, care solicită aplicarea algoritmilor de parcurgere a grafurilor.aplicarea algoritmilor de parcurgere a grafurilor.

Obiective operaţionaleObiective operaţionaleO1. Să analizeze noţiunea de graf;O1. Să analizeze noţiunea de graf;O2. Să stabilească modul de rezolvare a unei activităţi desfăşurate O2. Să stabilească modul de rezolvare a unei activităţi desfăşurate în viaţa de zi cu zi prin intermediul graf-urilor;în viaţa de zi cu zi prin intermediul graf-urilor;O3. Să analizeze problema prin aplicarea cunoştinţelor însuşite în O3. Să analizeze problema prin aplicarea cunoştinţelor însuşite în cadrul temei studiate; cadrul temei studiate; O4. Să descopere relaţiile existente între datele problemelor O4. Să descopere relaţiile existente între datele problemelor propuse;propuse;O5. Să identifice caracteristicile de bază ale unui graf;O5. Să identifice caracteristicile de bază ale unui graf;O6. Să identifice aplicarea, pe exemple relevante, a algoritmilor O6. Să identifice aplicarea, pe exemple relevante, a algoritmilor fundamentali din teoria graf-urilor;fundamentali din teoria graf-urilor;O7. Să adapteze algoritmii fundamentali de prelucrare a datelor O7. Să adapteze algoritmii fundamentali de prelucrare a datelor pentru rezolvarea problemelor propuse;pentru rezolvarea problemelor propuse;O8. Să identifice situaţii în care alegerea unui algoritm prezintă O8. Să identifice situaţii în care alegerea unui algoritm prezintă avantaje în raport cu altul;avantaje în raport cu altul;O9. Să elaboreze programe pentru rezolvarea unor probleme O9. Să elaboreze programe pentru rezolvarea unor probleme întâlnite de elevi în studiul altor discipline şcolare; întâlnite de elevi în studiul altor discipline şcolare; O10. Să evidenţieze greşelile tipice în elaborarea algoritmilor.O10. Să evidenţieze greşelile tipice în elaborarea algoritmilor.

Cum ne afectează Cum ne afectează viaţa modul de alocare viaţa modul de alocare al tipurilor de date?al tipurilor de date?

Care este metoda de utilizare Care este metoda de utilizare a grafurilor în activitatea zilnică?a grafurilor în activitatea zilnică?

Utilizarea grafului • Pentru a înţelege utilizarea grafurilor, să ne imaginăm cum arată oraşul

nostru. El poate fi privit ca un ansamblu de străzi care se intersectează între ele. Pentru a ajunge dintr-un loc în altul, trebuie să parcurgeţi nişte străzi şi să treceţi prin intersecţii. Cum poate să ajungă un turist, din locul X în locul Y. Va trebui să-i faceţi un mic desen pe o foaie de hârtie. Cum? Mai intâi veţi reprezenta intersecţiile prin puncte. Apoi străzile care “leagă” aceste intersecţii le veţi reprezenta prin linii drepte sau curbe, care în desenul vostru vor uni punctele deja fixate. Fără să vă daţi seama, aţi construit astfel un graf.

• Să zicem că dorim să realizăm o mică enciclopedie. Dispunem de un dicţionar de articole, despre care avem mai multe informaţii. Aceste articole sunt legate între ele, în sensul că, odată ajunşi să studiem un anumit articol, ni se pune la dispoziţie o listă de trimiteri la articole înrudite, pe care le putem numi articole vecine. Cum vom memora articolele şi legăturile dintre ele? Cea mai indicată structură de date, într-o asemenea situaţie, este graful. Un graf va fi o reţea de noduri, legate prin linii drepte (muchii).

GRAF NEORIENTAT ADIACENÎȚĂ, INCIDENȚĂ,

GRAD

Conceptul 1

Graf neorientatSe numeşte graf neorientat, o pereche ordonată de mulţimi (X, U), unde:X este o mulţime finită şi nevidă de elemente numite vârfuri sau noduri;U este o mulţime de perechi neordonate de câte două elemente din X, numite muchii sau arce.

Pentru o muchie uk=(a, b), vom spune că:Vârfurile a şi b sunt adiacente şi se numesc extremităţile muchiei uk;Muchia uk şi vârful a sunt incidente în graf. La fel, muchia uk şi vârful b;Muchia (a, b)este totuna cu (b, a) (nu există o orientare a muchiei)

Suport curs

REPREZENTAREA GRAFURILOR NEORIENTATE

Conceptul 2

Reprezentarea grafurilor neorientateConsideră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.

Suport curs

Matricea de adiacenţă

Este o matrice a cu n linii şi n coloane, în care elementele a[i, j] se definesc astfel:

a[i, j]= 1, dacă muchia [i, j] cu i j 0, în caz contrara[i, j]= a[j, i] oricare ar fi i, j{1, 2, …,n} cu ij.

Pentru orice graf neorientat, matricea de adiacenta a este simetrica faţă de diagonala principală .

Suport curs

Proprietatile matricei de adiacenta:

• Este o matrice simetrica;• Pe diagonala principala are

toate elemntele egale cu 0;• Suma elementelor pe linia

sau coloana i este egala cu gradul nodului i;

• Daca elementele pe linia/coloana i sunt toate egale cu 0 atunci nodul este izolat;

• Daca toate elementele din matrice,mai putin cele de pe diagonala principala, sunt 1 inseamna ca graful este complet.

Listele vecinilor• 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 ce trec prin nodul i.

• 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ţă.

Suport curs

Vectorul muchiilor

Fiecare muchie a grafului poate fi privită ca o înregistrare cu două componente: cele două vârfuri care constituie extremităţile muchiei. Definim graful ca un “Vector de muchii“, adică un vector cu elemente de tipul TMUCHIE: Type TMUCHIE=record

nod1, nod2 :integer; end;

Suport curs

NOŢIUNILE DE GRAF PARŢIAL ŞI SUBGRAF

Conceptul 3

Noţiunea de graf parţial

Fie graful G=(X, U). Un graf parţial al lui G, este un graf G1=(X, V), cu VU. Altfel spus, un graf parţial G1 al lui G, este chiar G, sau se obţine din G păstrând toate vârfurile şi suprimând nişte muchii.

Suport curs

Noţiunea de subgraf

Fie graful G=(X, U). Un subgraf al lui G, este un graf G1=(Y, V), unde YX şi VU, iar V va conţine numai muchiile care au ambele extremităţi în Y. Altfel spus, un subgraf G1 al lui G, se obţine din G eliminând nişte vârfuri şi păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase.

Suport curs

Test recapitulativ 1

Test recapitulativ 2

Evaluare Autoevaluare

Clik aici

Clik aici

Clik aici

Clik aici

Evaluare Autoevaluare

Clik aici

Clik aici

BIBLIOGRAFIE• Vlad Tudor (Huţanu), Tudor Sorin Manual de

INFORMATICĂ, clasa a XI-a, profilul real (neintensiv), Editura L&S SOFT, 2006

• George Daniel Mateescu - Informatica - manual pentru clasa a XI-a, Ed. Niculescu, București, 2001

• M. Gheorghe, Informatică, Ed. Corint, București, 2003• M. Bold, A. Matei – Aplicații de informatică pentru liceu,

Pitești, Ed. Paralela 45, 2007 • Mirela Popa, Informatică-fișe de lucru pentru elevi,

Editura Donaris, Sibiu, 2005

Ce este un graf?Ce este un graf?De câte tipuri pot fi grafurile?De câte tipuri pot fi grafurile?Ce înţelegem prin noţiunile de Ce înţelegem prin noţiunile de adiacenţă, incidenţă şi grad?adiacenţă, incidenţă şi grad?Care este reprezentarea Care este reprezentarea grafurilor neorientate?grafurilor neorientate?Cum definim noţiunile de graf Cum definim noţiunile de graf partialpartial şi subgraf? şi subgraf?