Teorie grafuri neorientate C++

Un graf neorientat este o pereche ordonată de mulţimi G = ( V , E ).

Multimea V este o multime nevida si finita de elemente denumite varfurile grafului.

Multimea E este o multime de perechi formate cu ajutorul varfurilor din graf.

In cazul grafurilor neorientate, perechile de varfuri din multimea E sunt neordonate si se numesc muchii. Ele nu au directie. Muchia formata de varfurile x si y se noteaza cu [x,y], varfurile x si y fiind denumite extremitatile muchiei.

Daca exista o muchie determinata de varfurile x si y atunci, varfurile x si y se numesc adiacente. De asemenea, varfurile x si y sunt considerate incidente cu muchia pe care o formeaza. Fiecare extremitate a unei muchii este considerata incidenta cu muchia respectiva.

Intre varfurile oricarui graf neorientat poate exista cel mult o muchie.

1. Reprezentarea vizuala a grafurilor neorientate:

  1. Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
  2. Vom reprezenta fiecare muchie ca fiind o linie dreapta care pleaca de la un varf si ajunge la celalalt.

Exemplu:

2.Gradul unui varf

Se numeste grad al unui varf x numarul de muchii incidente cu varful respectiv. Graful unui varf x se noteaza cu d(x).

Astfel apar 2 notiuni noi:

Varful izolat = un varf care are gradul 0.

Varful terminal un varf care are gradul 1.

x 1 2 3 4 5 6
d(x) 3 2 1 1 3 0

Observam din tabelul de mai sus faptul ca varful 6 este un varf izolat si ca varfurile 3 si 4 sunt varfuri terminale.

Teorema: Suma gradelor unui varf neorientat este egala cu dublul numarului de muchii din graf.

Σd(x) = 2n

3. Notiunile de lant si ciclu

Intr-un graf neorientat, se numeste lant o secventa de varfuri cu proprietatea ca oricare doua varfuri consecutive din secventa sunt adiacente. De exemplu, pentru graful dat, [3,1,2,5,1,3,1] este un lant cu lungimea 6.

Lungimea unui lant = numarul de muchii pe care acesta le are in componenta.

Un lant este elementar atunci cand nu contine acelasi varf de mai multe ori. De exemplu, pentru graful dat, [1,2,5] este un lant elementar cu lungimea 2.

Un lant este simplu daca nu contine de mai multe ori aceeasi muchie. De exemplu, pentru graful dat, [3,1,2,5,4] este un lant simplu cu lungimea 4.

Se numeste ciclu, un lant simplu in care varful initial coincide cu varful final. In alte cuvinte lantul pleaca din varful x si ajunge tot in varful x. De exemplu, pentru graful dat, [1,2,5,1,2,5,1] este un ciclu.

Un ciclu este elementar daca nu contine de mai multe ori acelasi varf (cu exceptia extremitatilor). De exemplu, pentru graful dat [5,1,2,5], este un ciclu elementar.

Teoreme:

Un lant/ciclu elementar se numeste hamiltonian daca el trece prin toate varfurile grafului.

Un lant/ciclu elementar se numeste eulerian daca el trece prin fiecare muchie al grafului o singura data.

4. Grafuri asociate unui graf dat

Fie G = (V,E) un graf orientat.

Graful G’=(V,E’) se numeste un graf partial al lui G daca E’ ⊂ E.

Un graf partial al lui G se obtine eliminand muchii din graful G.

Graful partial de mai sus a fost obtinut prin eliminarea muchiilor [1,3], [1,5] din graful initial.

Un subgraf al lui G se obtine eliminand un varf si toate muchiile incidente cu acesta.

Subgraful de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a tuturor muchiilor incidente cu acesta: [1,5], [2,5], [4,5].

Un subgraf partial al lui G se obtine eliminand varfuri din graful G, muchiile incidente cu varfurile eliminate, precum si alte muchii din graful G.

Subgraful partial de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a muchiilor [1,3], [1,5], [2,5], [4,5].

Teoreme:

Fie G un graf neorientat cu n varfuri si m muchii:

a) Numarul de grafuri partiale ale lui G este 2m-1.

b) Numarul de subgrafuri ale lui G este 2n-1.

5. Tipuri speciale de grafuri

Un graf neorientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.

Graful neorientat complet cu n varfuri se numeste Kn si contine [n(n-1)]/2 muchii.

Exemplu:

Un graf neorientat G = (V,E) se numeste bipartit daca multimea varfurilor sale poate fi partitionata in doua submultimi A si B nevid ( A ∪ B = V ; A ∩ B = Ø) astfel incat orice muchie sa aia o extremitate in A si una in B.

In graful de mai sus, multimea A = {1,2,3} si multimea B = {4,5,6,7}.

Un graf neorientat se numeste regulat daca toate varfurile sale au acelasi grad.

 Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

15 Replies to “Teorie grafuri neorientate C++”

  1. Georgescu Razvan March 20, 2019 at 11:52 pm

    Va rog revizuiti-va pagina de grafuri, exista greseli.

    Reply

    1. nem tudom romanul

      Reply

    2. Uite graseala! Graful unui varf x se noteaza cu d(x).
      limbaj de kkmk!

      Reply

    3. Poti sa ne spui te rog ce greseli ai observat?

      Reply

  2. fuarte gresita situatia, ma dezamaghit

    Reply

    1. Dezamăgitoare sunt dezabilitățile tale in ale gramaticii.

      Reply

  3. dece ziceti ca e gresit, nu vad nici una greseala aicia la voi la cap poate este

    Reply

  4. daca zici ca e gresit spune ce e frate ca nu toti suntem perfecti ca tine auzi la el

    Reply

  5. nu imi place, trebuie sa dau test din asta joia urmatoare si o sa iau 2 pentru ca nu este explicat bine pe site

    Reply

    1. Poti sa ne spui te rog ce crezi ca nu e bine explicat? Ai vreun sfat pentru cum am putea sa explicam mai bine?

      Reply

  6. Nem tudom romanul!!!

    Reply

  7. mortmintu mati

    Reply

  8. buna! eu apreciez foarte mult munca voastra de pe site. cred ca e foarte bine explicat… gasesc multe lucruri utile si chiar daca poate exista greseli stiu ca faceti ce puteti ca sa le rezolvati (eu n-am remarcat dar daca sunt…)
    m-am folosit de foarte multe ori de site-ul acestea si m-a ajutat mult ! stiu ca necesita mult timp si energie dar va incurajez sa continuati 🙂

    Reply

    1. Buna! Iti multumim mult pentru apreciere si sutinere 🙂 Ne bucuram super mult ca siteul te ajuta. Zi faina!

      Reply

  9. 4. Grafuri asociate unui graf dat

    Fie G = (V,E) un graf orientat. // un graf neorientat nu ?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *