fbpx

Adiacenta – Incidenta – Grad

0

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:

Un exemplu de graf neorientat cat mai simplu

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

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More