fbpx

Teoria Grafurilor – Tipuri de grafuri neorientate

0

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

Acesta este un graf complet
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 bipartit complet

Graf regulat

Definitie

Se numeste graf regulat, un graf cu proprietatea ca toate nodurile au acelasi grad.

Exemplu

Acest graf este unul regulat.
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
Graf planar
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