Definitie
Un graf neorientat este o pereche ordonata de multimi (X, U), unde:
– X este o multime finita si nevida de elemente numite noduri sau varfuri
– U este o multime de perechi neordonata din X, numite muchii
Daca exista muchia U = (x, y) atunci vom spune ca nodurile x si y sunt adiacente.
Daca exista muchia U = (x, y) atunci vom spune ca nodul x si muchia u sunt incidente. La fel nodul y si muchia u.
Gradul unui nod x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).
- Un nod care are gradul 0 se numeste nod izolat.
- Un nod care are gradul 1 se numeste nod terminal.
Elemente de teorie
Teorema
Intr-un graf G=(X, U) cu n varfuri si m muchii, suma gradelor tuturor varfurilor este egala cu 2*numarul muchiilor, altfel spus:
Exemplu
Multimea nodurilor: X = {1, 2, 3, 4, 5, 6, 7}
Multimea muchiilor: U = {(2, 3), (5, 4), (5, 6), (4,7)}
Gradul nodului 5: d(5) = 2
Nod izolat: 1
Noduri terminale: 2, 3, 6, 7
Nodurile 2 si 3 sunt adiacente, pentru ca avem muchia (2, 3) in multimea U. Puteti sa raspundeti in comentarii care sunt toate nodurile adiacente?
Nodul 7 si muchia (4, 7) sunt incidente, pentru ca nodul „7” se regaseste in muchia (4, 7).
Portal.edu.ro
Adiacenta – Incidenta – Grad – Teorie – portal.edu.ro
Adiacenta – Incidenta – Grad – Evaluare – portal.edu.ro
Adiacenta – Incidenta – Grad – Desenarea unui graf – portal.edu.ro
