Grafuri neorientate

Trimis la data: 2007-05-06
Materia: Informatica
Nivel: Liceu
Pagini: 12
Nota: 8.39 / 10
Downloads: 3335
Autor: Valentin Tamas
Dimensiune: 38kb
Voturi: 95
Tipul fisierelor: doc
Acorda si tu o nota acestui referat:
Grafuri neorientate
Graf = orice mulţime finită V prevăzută cu o relaţie binară internă E. Notăm graful cu G=(V, E).

Graf neorientat = un graf G=(V, E) în care relaţia binară este simetrică: (v,w)ÎE atunci (w,v) ÎE.

Nod = element al mulţimii V, unde G=(V, E) este un graf neorientat.

Muchie = element al mulţimii E ce descrie o relaţie existentă între două vârfuri din V, unde G=(V, E) este un graf neorientat;

In figura alaturata:
V={1,2,3,4,5,6} sunt noduri
E={[1,2], [1,4], [2,3],[3,4],[3,5]} sunt muchii
G=(V, E)=({1,2,3,4,5,6}, {[1,2], [1,4], [2,3],[3,4],[3,5]})


Adiacenta: Într-un graf neorientat existenţa muchiei (v,w) presupune că w este adiacent cu v şi v adiacent cu w.
În exemplul din figura de mai sus vârful 1 este adiacent cu 4 dar 1 şi 3 nu reprezintă o pereche de vârfuri adiacente.

Incidenţă = o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate. Muchia (v,w) este incidentă în nodul v respectiv w.

Grad = Gradul unui nod v, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

Nod izolat = Un nod cu gradul 0.

Nod terminal= un nod cu gradul 1

Nodul 5 este terminal (gradul 1).

Nodul 6 este izolat (gradul 0)

Nodurile 1, 2, 4 au gradele egale cu 2.


Lanţ = este o secvenţă de noduri ale unui graf neorientat G=(V,E), cu proprietatea că oricare două noduri consecutive din lant sunt adiacente:
L=[w1, w2, w3,. . ,wn] cu proprietatea că (wi, wi+1)ÎE pentru 1£i
Home | Termeni si conditii | Politica de confidentialitate | Cookies | Help (F.A.Q.) | Contact | Publicitate
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.