Grafuri neorientate : Tipuri de graf

Definitie:Un graf  se zice regulat daca toate vf sale au acelasi grad.

Exemple graful din fig 5 este graf regulat 

Graf complementar

Fie graful G=(X,U) .se numeste graf complementar al garfului G grafuil G’=(U’,X’),cu proprietatea ca doua varfuri adiacente in G’ daca nu sunt adiacente in G

Exemplu: Graful G’  complementar grafului  G .

 

Graf conex

Un graf este conex daca pentru oricare 2 varfuri x si y exista un lant care le leaga .

                          Exp:fig 8

         Se numeste componenta conexa a grafului  G=(X,U) un subgraf G’=(U’,X’) conex cu proprietatea ca nu exista nici un lant in G care sa lege un  varf din X’ cu un varf din X.

Exemplu: graful alaturat are 2 componenete  conexe fig 12.

           

     Fie G=(V,E)  un graf neorientat conex.Un varf i se numeste punct de articulatie daca prin indepartarea sa si a muchiilor adiacente graful nu mai ramane conex.

Un graf  G=(V,E)  se numeste biconvex daca un are puncte de articulatie .Daca G nu este biconvex se pune problema determinarii componentelor sale biconvexe ,unde prin componenta biconvexa se intelege un subgraf biconvex maximal.

Graf hamiltonian

Se numeste graf hamiltonian un graf care contine un ciclu hamiltonian(care contine toate varfurile grafului).

Exp:fig 14 graf hamiltonian  

 Conditie suficienta ca un graf sa fie hamiltonian :Daca G=(X,U) este un graf cu n≥3 varfuri astfel incat gradul fiecarui varf satisface conditia d(x)≥n/2 atunci este hamiltonian.

Graf eulerian

Se numeste graf eulerian un graf care contine un ciclu eulerian (ciclu care contine toate muchiile grafului)

Exp:graful din  figura alaturata   este eulerian. 

        Un graf G=(X,U) fara varfuri izolate este eulerian  daca si numai daca este conex si gradele tuturor varfurilor sunt numere pare .

OBS: O metoda pentru a arata ca un graf este eulerian :se arata ca graful este conex ,si toate varfurile au grade pare.

Lanţ

Definiţie 1.2.3.1 Fie un graf neorientat G=(X, U). Se numeşte lanţ al grafului G o succesiune de noduri L=[x1, x2, ..., xk], unde x1, x2, ..., xkÎX, cu proprietatea că [x1, x2], [x2, x3], ..., [xk-1, xk]ÎU (adică există muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] în graful G).

Definiţe 1.2.3.2 Fie un graf neorientat G=(X, U) ş L=[x1, x2, ..., xk] un lanţal grafului G. x1 şi xk se numesc extremităţle lanţlui, iar număul muchiilor care intră în componenţa lanţului reprezintă lungimealanţului.

Exemplu: Pentru graful din figura 1.19 se pot distinge mai multe lanţuri printre care

L1=[1, 2, 3, 5, 4, 8], L2=[1, 2, 3, 2], L3=[9, 3, 5, 4, 3, 2], L4=[6, 7, 3, 5, 4, 8]

 

Figura 1.19

Definiţie 1.2.3.3 Fie un graf neorientat G=(X, U) şi L=[x1, x2, ..., xk] un lanţ al grafului G. Dacă nodurile x1, x2, ..., xk sunt distincte două câte două, atunci lanţul se numeşte elementar. În caz contrar lanţul se numeşte ne-elementar.

Exemplu: Lanţurile L1 şi L4 din exemplul anterior sunt elementare. Lanţurile L2 şi L3 din exemplul anterior sunt ne-elementare.

Definiţie 1.2.3.4 Fie un graf neorientat G=(X, U) şi L=[x1, x2, ..., xk] un lanţ al grafului G. Dacă muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] sunt distincte două câte două, atunci lanţul se numeşte simplu. În caz contrar lanţul se numeşte compus.

Exemplu: Lanţurile L1, L3, L4 din exemplul anterior sunt simple. Lanţul L2 din exemplul anterior este compus.

Observaţie: Orice lanţ elementar este simplu. Reciproca nu este valabilă (se poate întâmpla ca lanţul să fie simplu, dar să fie ne-elementar – vezi lanţul L3 din exemplul lanţurilor).

Drumuri într-un graf

Numim drum într-un graf o succesiune de muchii adiacente și distincte care conectează două vârfuri din graf (numite capetele drumului). Un drum se numește simplu dacă muchiile care îl compun sunt distincte. Numim ciclu un drum care are drept capete un același vârf.

Dacă P = x₀, ..., x_k-1 este un drum în graful G și x_k-1x₀ este o muchie în acest graf, atunci P + x_k-1x₀ este un ciclu din graful G.

Un ciclu se numește hamiltonian dacă este simplu și trece prin toate nodurile grafului G, exact o dată, și se numeșteeulerian dacă trece prin toate muchiile grafului G, exact o dată. Nu orice graf conține un ciclu hamiltonian (Fig. 2).

Spunem că S este un subgraf al lui G, dacă acesta conține o parte din vârfurile lui G și numai acele muchii care le conectează.