Definiţia matematică a grafului:
Definiţie : Se numeşte graf G= (X ,U ), unde X={ x1, x2, x3,…, xi,…, xn}, X≠∅, este multimea de vârfuri sau noduri, iar U={ u1, u2, u3,…, uk,…, um}, este multimea de muchii (arce).
ordinul grafului = card(X) = n
Clasificarea grafurilor :
Grafuri neorientate. Un graf G=(X,U) este un graf neorientat dacă mulţimea U are proprietatea de simetrie. Mulţimea U este formată din perechi neordonate (xi,xj), numite muchii
Grafuri orientate.Un graf G=(X,U) este un graf orientat dacă mulţimea U nu are proprietatea de simetrie. Mulţimea U este formată din perechi ordonate (xi,xj) , numite arce.
Definiţie : Se numeşte graf G= (X ,U ), unde X={ x1, x2, x3,…, xi,…, xn}, X≠∅, este multimea de vârfuri sau noduri, iar U={ u1, u2, u3,…, uk,…, um}, este multimea de muchii (arce).
ordinul grafului = card(X) = n
Clasificarea grafurilor :
Grafuri neorientate. Un graf G=(X,U) este un graf neorientat dacă mulţimea U are proprietatea de simetrie. Mulţimea U este formată din perechi neordonate (xi,xj), numite muchii
Grafuri orientate.Un graf G=(X,U) este un graf orientat dacă mulţimea U nu are proprietatea de simetrie. Mulţimea U este formată din perechi ordonate (xi,xj) , numite arce.
Graful Neorientat
Reprezentarea în plan:
Teoremă : Dacă graful neorientat G are n noduri {x1,x2,…xn} atunci numărul total de grafuri neorientate care se pot forma cu aceste noduri este g:
Gradul unui nod într-un graf neorientat:
Definiţie: Gradul unui nod xk al grafului G este egal cu numărul muchiilor incidente cu nodul şi se notează cu d(xk).
Definiţie : Vârful x apartine X se numeşte izolat în graful G , dacă d(x) = 0 si terminal dacă d(x) = 1.
Teoremă: suma gradelor tuturor nodurilor grafului este egală cu dublul numărului de muchii :
Definiţie: Gradul unui nod xk al grafului G este egal cu numărul muchiilor incidente cu nodul şi se notează cu d(xk).
Definiţie : Vârful x apartine X se numeşte izolat în graful G , dacă d(x) = 0 si terminal dacă d(x) = 1.
Teoremă: suma gradelor tuturor nodurilor grafului este egală cu dublul numărului de muchii :
Definiţie : Graful în care oricare două vârfuri sunt adiacente, se numeşte graf complet si se notează prin Kn . Numărul de muchii ale lui Kn este:
Definiţie : Un graf în care fiecare nod are gradul k se numeşte k- regulat sau k-valent.
Un graf 3−valent se numește graf trivalent sau cubic.Un exemplu de graf trivalent este graful lui Petersen
Un graf 3−valent se numește graf trivalent sau cubic.Un exemplu de graf trivalent este graful lui Petersen
Exemple:
Corolar. Graful complet Kn este (n - 1)-regulat.
Definiţie : Graful G = (X,U) cu U = se numeşte graf vid si se notează prin On , iar graful pentru care |X| =1, U = se numeşte graf trivial.
Definiţie : Graful G = (X,U) cu U = se numeşte graf vid si se notează prin On , iar graful pentru care |X| =1, U = se numeşte graf trivial.
Graful Orientat
în graful orientat perechile de noduri sunt ordonate. Graful ordonat se mai numeşte şi digraf.
Teoremă : Dacă graful orientat G are n noduri {x1,x2,…xn} atunci numărul total de grafuri orientate care se pot forma cu aceste noduri este:
Gradele unui nod într-un graf orientat:
Definiţie : Gradul intern al unui nod xi al grafului G este egal cu numărul arcelor care intră în nodul xi şi se notază cu d-(xi).
Definiţie : Gradul extern al unui nod xi al grafului G este egal cu numărul arcelor care ies în nodul xi şi se notază cu d+(xi).
Definiţie : Se numeşte nod terminal un nod care are suma gradelor egală cu 1. Nodul terminal este incident cu un singur arc.
Definiţie : Se numeşte nod izolat un nod care are suma gradelor egală cu 0. Nodul izolat nu este incident cu nici un arc.
Teoremă : Suma gradelor interne ale tuturor nodurilor este egală cu suma gradelor externe ale tuturor nodurilor şi este egal cu numărul de arce :
Definiţie : Gradul intern al unui nod xi al grafului G este egal cu numărul arcelor care intră în nodul xi şi se notază cu d-(xi).
Definiţie : Gradul extern al unui nod xi al grafului G este egal cu numărul arcelor care ies în nodul xi şi se notază cu d+(xi).
Definiţie : Se numeşte nod terminal un nod care are suma gradelor egală cu 1. Nodul terminal este incident cu un singur arc.
Definiţie : Se numeşte nod izolat un nod care are suma gradelor egală cu 0. Nodul izolat nu este incident cu nici un arc.
Teoremă : Suma gradelor interne ale tuturor nodurilor este egală cu suma gradelor externe ale tuturor nodurilor şi este egal cu numărul de arce :