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ă.

Lanţ = este o secvenţă de noduri ale unui graf neorientat G=(V,E), cu proprietatea că oricare două noduri consecutive din secventa lant  sunt adiacente:

 L=[w₁, w₂, w₃,. . ,w_n]  cu proprietatea că (w_i, w_i+1)ÎE pentru  1£i<n.

Lungimea unui lanţ = numărul de muchii din care este format.

Lanţ simplu = lanţul care conţine numai muchii distincte

Lanţ compus= lanţul care nu este format numai din muchii distincte

Lanţ elementar = lanţul care conţine numai noduri distincte

Ciclu = Un lanţ în care primul nod coincide cu ultimul.

Ciclul este elementar dacă este format doar din noduri distincte, excepţie făcând primul şi ultimul. Lungimea unui ciclu nu poate fi 2.

Graf partial = Dacă dintr-un graf G=(V,E) se suprimă cel puţin o muchie atunci noul graf G’=(V,E’), E’Ì E se numeşte graf parţial al lui G (are aceleasi noduri si o parte din muchii).

 Subgraf = Dacă dintr-un graf G=(V,E) se suprimă cel puţin un nod împreună cu muchiile incidente lui, atunci noul graf G’=(V’,E’), E’Ì E si V’ÌV se numeşte subgraf al lui G.

Graf regulat = graf neorientat în care toate nodurile au acelaşi grad;

Graf complet = graf neorientat G=(V,E) în care există muchie între oricare două noduri.

Numărul de muchii ale unui graf complet este:  nr*(nr-1)/2.Unde nr este numarul de noduri

graf complet. Nr de muchii: 4x(4-1)/2 = 6

Graf conex = graf neorientat G=(V,E) în care pentru orice pereche de noduri (v,w) există un lanţ care le uneşte.

graf conexnu este graf conex

Componentă conexă = subgraf al grafului de referinţă, maximal în raport cu proprietatea de conexitate (între oricare două vârfuri există lanţ);

graful nu este conex. Are 2 componente conexe:

                                                1, 2 si 3, 4, 5, 6

Lanţ hamiltonian = un lanţ elementar care conţine toate nodurile unui graf

 L=[2 ,1, 6, 5, 4, 3] este lant hamiltonian

Ciclu hamiltonian = un ciclu elementar care conţine toate nodurile grafului

C=[1,2,3,4,5,6,1] este ciclu hamiltonian

Graf hamiltonian = un graf G care conţine un ciclu hamiltonian

Graful anterior este graf Hamiltonian.

Daca G este un graf cu n>=3 noduri astfel incat gradul fiecarui nod este mai mare sau egal decat n/2 atunci G este hamiltonian

Lanţ eulerian = un lanţ simplu care conţine toate muchiile unui graf

Lantul: L=[1.2.3.4.5.3.6.2.5.6] este lant eulerian

Ciclu eulerian = un ciclu simplu care conţine toate muchiile grafului

 Ciclul: C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian

Graf eulerian = un graf  care conţine un ciclu eulerian.

                                    Intrebari si exercitii :

1. desenati un graf G neorientat cu 6 noduri si 10 muchii
2. Exprimati graful ca o relatie binara detaliind multimea nodurilor si multimea muchiilor
3. precizati pentru fiecare nod gradul
4. precizati un lant simplu, un lant compus
5. precizati un lant elementar, neelementar
6. precizati un ciclu
7. desenati un graf Gp partial cu 7 muchii
8. desenati un subgraf Gs cu 4 noduri
9. modificati Gs astfel incat Gs sa fie graf complet
10. desenati un graf regulat Gr cu 9 noduri
11. cate componente conexe are Gr?
12. modificati Gr astfel incat sa obtineti Gr1 graf conex
13. precizati un lant hamiltonian in Gr1
14. modificati  Gr astfel incat acesta sa fie graf eulerian
15. precizati un ciclu eulerian in Gr
16. puteti desena urmatoarea figura fara a ridica creionul de pe hartie si fara a repete muchiile?

17. este graful anterior eulerian ? de ce ?

Pentru inceput un scurt istoric despre parintii teoriei grafurilor:
Leonard Euler

STIATI CA...

Leonard Euler este considerat a fi fost forta dominanta a matematicii secolului al XVIII-lea si unul dintre cei mai remarcabili matematicieni si savanti multilaterali ai omenirii. El a introdus notiunea de functie si a fost primul care a notat f(x) pentru aplicarea functiei f elementului x.
De asemenea, el a introdus notatia moderna pentru functiile trigonometrice, litera e pentru baza logaritmului natural (cunoscut in prezent drept numarul lui Euler), litera greceasca ? pentru suma si litera i pentru unitatea imaginara.
Folosirea literei grecesti ? pentru raportul dintre circumferinta unui cerc si diametrul sau a fost de asemenea popularizata de Euler, chiar daca ideea nu a pornit de la el. 
 
Primele notiuni in teoria grafurilor ca parte integranta a matematicii au fost definite in anul 1736 de catre Leonhard Euler .
Problema pe care a rezolv-o si care a dus la noi fundamente teoretice in teoria grafurilor este o problema practica legata de traversarea celor 7 poduri din Königsberg - Prusia, plecand de la un pod si trecand prin celelalte o singura data , intorcandu-se la podul de pornire.
Arthur Cayley

STIATI CA...

Arthur Cayley s-a nascut în Londra. Tatal sau, Henry Cayley, a fost var cu Sir George Cayley, inventator în domeniul aeronauticii.
În 1852, Francis Guthrie a incercat sa coloreze o harta reprezentand comitatele Angliei, astfel incat doua regiuni cu frontiera comuna sa aiba culori distincte.
De cate culori este nevoie pentru a colora o harta oarecare, astfel incat regiunile cu frontiera comuna sa aiba culori diferite?
De la profesor la student, de la coleg la coleg… problema a ajuns la Arthur Cayley, care i-a intrebat pe colegii sai din London Mathematical Society.
S-a demonstrate ca sunt suficiente 4 culori care sa resolve aceasta problema.

Conceptul de graf chimic a fost formulat de matematicianul britanic Arthur Cayley inaintea introducerii termenului graf.
O contributie importanta in studiul grafurilor chimice o are chimistul roman Alexandru T. Balaban 

Variantele 31-39

Varianta 31: Se considera graful neorientat cu 7 noduri, numerotate de la 1 la 7, si muchiile[1,3],[2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre urmatoarele succesiuni de noduri reprezinta un lant care trece o singura data prin toate nodurile grafului? (4p.)

   
a. (1, 2, 3, 4, 5, 6, 7)                

b. (4, 5, 3, 6, 7)

c. (7, 6, 3, 5, 4, 2, 1)               

d. (1, 3, 5, 4, 2, 3, 6)

  

Raspuns :  c ,deoarece este singura succesiune de noduri  care trece o singura data prin toate varfurile.

Varianta 32. Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este

reprezentat cu ajutorul matricei de adiacenta alaturate.  Pentru acest graf este adevarata afirmatia: (4p.)

a. Graful este hamiltonian               

b. Graful nu are noduri de grad 0

c. Gradul maxim al unui nod este 3

d. Graful are trei componente conexe

Raspuns:d ,deoarece  graful nu contine toate nodurile conditie necesara pentru un graf hamiltonian, are graduri de nodul 0 iar gradul maxim al unui nod este 4. Dupa cum se poate observa pe desenul corespunzator matricei de adiacenta graful are 3 componente conexe.

Varianta 34. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60], [60,20], [2,30] si [4,30]. Numarul componentelor conexe ale grafului este egal cu:

(4p.)

a. 3

b. 56

c. 54 

d. 0

 Raspuns b. deoarece din 60 de noduri scadem 6 noduri si adaugam 2(cele 2 componente conexe) rezultand 56.

Varianta 35. Un graf neorientat cu 10 noduri, numerotate de la 1 la 10,este reprezentat cu ajutorul listelor de adiacenta alaturate.Câte componente conexe are graful si care este numarul    minim de muchii ce trebuie adaugate pentru ca graful sa fie

conex? (6p.)

1:3,5

2:4

3:1,5

4:2,8

5:1,3

6:

7:10

8:4

9:

10:7

Raspuns :5 componente conexe  ,                                           trebuie adaugate 4  muchii astfel  incat graful sa fie conex.

Varianta 36. Se considera un graf neorientat cu 7 noduri       numerotate de la 1 la 7 si muchiile [1,2],[1,3],[2,3],[2,4],[2,5],[2,6],[4,6],[5,7],[6,7]. Care este numarul minim de muchii care trebuie adaugate pentru ca acest graf sa devina eulerian? (4p.)

Raspuns : minim 8 muchii(muchiile albastre) (fiecare nod trebuie sa aiba grad par si trebuie sa existe toate muchiile )

Varianta 38. Urmatorii doi itemi se refera la un graf neorientat cu 7 noduri,nume-rotate de la 1 la 7 si muchiile [1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].

1. Care este numarul minim de muchii care trebuie eliminate astfel încât graful sa aiba 3 componente conexe? (6p.)

Raspuns:eliminam [1,5] [5,6] (2 muchii ) si avem 1 si 6 doua componenta conexe   {2,3,4,5,7} formeaza a treia componenata conexa .

2. Câte cicluri elementare distincte exista în graf? Doua cicluri sunt distincte daca difera prin cel putin o muchie.

Raspuns: 5 cicluri elementare

Rezolvare :

(2,5,7,4,3,2)  

(2,3,4,2)

(3,4,5,2,3)

(3,2,5,7,4,3)

(3,2,4,7,5,3)

Varianta 39. Se considera un graf neorientat cu 8 noduri, numerotate de la 1 la 8, si muchiile [1,5], [1,6], [2,6], [3,4], [3,6], [3,7], [4,6], [6,8], [7,8]. Daca se elimina nodul 6 si toate muchiile incidente cu acesta câte componente conexe va avea subgraful rezultat?

                                                                                         
 Rezolvare:

Raspuns : 3 componenete conexe