Graf complet
Definitie
Se numeste graf complet cu n varfuri, notat Kn, un graf G = (X, U) cu proprietatea ca oricare doua varfuri sunt adiacente. Altfel spus: oricum am alege aleator doua noduri, intre ele trebuie sa existe o muchie.
Observatie
Un graf complet cu n varfuri, are (x * (x – 1)) / 2 muchii.
*Formula scrisa matematic:
[math]\frac{x * (x-1)}{2}[/math]
Exemplu
Graf complet
Graf bipartit
Definitie
Se numeste graf bipartit, un graf G = (X, U) cu proprietatea ca exista doua multimi A si B incluse in X astfel incat:
- A ∩ B = Ø si A ∪ B = X
- toate muchiile grafului au o extremitate in A si cealalta in B
Graf bipartit complet: Se numeste graf bipartit complet, un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B, exista muchia (x, y). Unde A si B sunt cele doua submultimi care partitioneaza multimea varfurilor X.
Observatie
Un graf bipartit complet cu p varfuri in prima multime si q varfuri in a doua multime are p * q muchii.
Exemplu
Graf bipartit complet
Graf regulat
Definitie
Se numeste graf regulat, un graf cu proprietatea ca toate nodurile au acelasi grad.
Exemplu
Graful Petersen
Graf planar
Definitie
Se numeste graf planar, un graf cu proprietatea ca exista o reprezentare a sa in plan asftel incat oricare doua muchii sa nu se intersecteze.
Exemplu
Graf planar
