Tipuri de Grafuri

        1.Graful complet

        Se numeşte graf complet cu n vârfuri un graf cu proprietatea că oricare două noduri distincte sunt adiacente. Un graf complet cu n vârfuri se notează Kn.

        Exemplu: Graful definit mai jos este complet şi se notează cu K5. 

        Într-un graf complet, gradul oricărui nod este n - 1, pentru că din/în fiecare nod pleacă/sosesc n - 1 muchii. Într-un graf complet, avem relaţia: m = n(n - 1)/2 = 2 Cn (numărul de submulţimi cu 2 elemente ale mulţimii celor n noduri), unde m este numărul de muchii, iar n numărul de noduri. Avem ( 1) / 2 2 n n− grafuri neorientate cu n noduri.

         2.Graful bipartit

       Un graf G = (X, U) se numeşte bipartit dacă există 2 mulţimi nevide A şi B a.î. X = A ∪ B, A ∩ B = ∅ şi orice muchie u a lui G are o extremitate în A iar cealaltă în B. Mulţimile A şi B formează o partiţie a lui X. Un graf este bipartit dacă şi numai dacă nu conţine cicluri de lungime impară.                    Exemplu: A = {1, 3, 4} şi B = { 2, 5, 6, 7}.

         

        3.Graful eulerian

Fie G=(V, M) un graf neorientat. Graful G, fără vârfuri izolate, este eulerian dacă si numai daca este conex si gradele tuturor vârfurilor sale sunt numere pare.
Fie G=(V, M) un graf neorientat. Se numeste lant eulerian, in graful G, un lant care contine toate muchiile grafului G, fiecare muchie apărând în lant o singură dată.
Fie G= (V,M) un graf neorientat. Se numeste ciclu eulerian, în graful G, un ciclu care contine toate muchiile grafului G, fiecare muchie apărând în ciclu o singură data.
Graful G=(V,M) este un graf eulerian, deoarece graful este conex si gradul fiecarui varf este un numar par .

  

Pentru acest graf exista: Ciclu Eulerian: 1,2,6,3,2,5,3,4,5,6,1.

        4.Graful hamiltonian

   Se numeste graf hamiltonian, un graf care contine un ciclu hamiltonian.

Exemplu: Graful din figura este hamiltonian, deoarece ciclul c=[1,2,3,5,4,1] este elementar (pleaca din vârful 1, iar muchiile [1,2], [2,3], [3,5], [5,4] si [4,1] sunt distincte doua câte doua ) si în plus contine toate vârfurile.
Se numeste lant hamiltonian într-un graf, un lant elementar care contine toate vârfurile grafului.
Se numeste ciclu hamiltonian într-un graf, un ciclu elementar care contine toate vârfurile grafului.