Created by Pastravanu Marius Page 1 4/19/2023

Pentru alte sensuri, vedeți Graf (dezambiguizare).

Fig. 1 - Graf neorientat Fig. 2 – Graf

orientatNumim graf o pereche ordonată de

mulțimi, notată G=(X,U), unde X

este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numește neorientat, altfel acesta este orientat.

Așadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) și din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).

Created on 11/9/2014 2:56:00 PM 1

Created by Pastravanu Marius Page 2 4/19/2023

Ordine și gradeNumim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulțimii X(G), și notăm această valoare cu |G|. Numărul de muchii se notează cu ∥G∥.

Graful vid este graful G(∅,∅) și se notează cu ∅. Spunem că un graf G este trivial dacă acesta are ordinul 0 sau 1.

Spunem că un nod v este incident cu o muchie r dacă v∈r. Două vârfuri x și y se numesc adiacente dacă există o muchie e care le unește (cu care amândouă vârfurile sunt incidente). Două muchii sunt adiacente dacă există un nod x care să fie incident cu ambele muchii.

Numim gradul unui nod particular v (v∈X(G)), numărul de arce care sunt conectate la acel nod și se notează de obicei cu ρ(v) sau cu d(v).

Dacă adunăm gradele tuturor nodurilor din graful G, obținem de două ori numărul de muchii:

∑v∈X(G)ρ(v)=2⋅|U(G)|Faptul că membrul drept al ecuației va fi mereu par, implică aceeași proprietate în membrul stâng, pentru ca egalitatea să fie satisfăcută.

Fig. 3 - GrafVârfurile verzi sunt adiacenteMuchiile roşii formează un drum care leagă nodurile 3 şi 6

Created on 11/9/2014 2:56:00 PM2

Created by Pastravanu Marius Page 3 4/19/2023

Drumuri într-un grafNumim 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 = x0, ..., xk-1 este un drum în graful G și xk-1x0 este o muchie în acest graf, atunci P + xk-1x0 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ște eulerian 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ă.

ConexiuneSpunem că un graf este conex dacă între oricare două vârfuri ale acestuia există cel puțin un drum. De exemplu grafurile din figurile 1 și 2 nu sunt conexe, în timp ce graful din figura 3 este un graf conex. Graful

trivial este considerat conex.

Complementul unui graf G este graful G¯(X,X2∖U), care conține o muchie între vârfurile x și y dacă și numai dacă G nu conține o astfel de muchie.

Complementul unui graf care nu este conex, este un graf conex. Reciproca nu este adevărată, de exemplu pentru un lanț de lungime 3 (între 4 vârfuri).

Noțiuni asociateDacă în definiția unui graf se considera E(G) o multimulțime pe P2(V(G)), adică este dată o funcție m: Ρ2(V(G))→ Ν, se obține noțiunea de multigraf.Dacă în definiția unui graf se considera E(G) o multimulțime pe mulțimea părtilor nevide cu cel mult două elemente ale lui V(G), atunci G se numește graf general sau pseudograf.

Created on 11/9/2014 2:56:00 PM 3

Created by Pastravanu Marius Page 4 4/19/2023

Un graf etichetat, cu 6 noduri și 7 muchii

În matematică și informatică, teoria grafurilor studiază proprietățile grafurilor. Un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi atribuite direcții (în acest caz, se spune că graful este orientat). Un graf poate fi reprezentat geometric ca o mulțime de puncte legate între ele prin linii (de obicei curbe).

AplicațiiGrafurile au o importanță imensă în informatică, de exemplu:

în unele problemele de sortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf;schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție;

Created on 11/9/2014 2:56:00 PM4

Teoria grafurilor

Created by Pastravanu Marius Page 5 4/19/2023

în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări, agregări)

Arbore(teoria grafurilor)

De la Wikipedia, enciclopedia liberă

Exemplu de arbore În teoria grafurilor, un arbore este un graf neorientat, conex și fără cicluri. Arborii reprezintă grafurile cele mai simple ca structură din clasa grafurilor conexe, ei fiind și cei mai frecvent utilizați în practică.

Termenul de „arbore” din teoria grafurilor a fost folosit pentru prima dată de Cayley în anul 1857. El a plecat de la o analogie cu noțiunea de „arbore” din botanică.

IstorieArborii au fost studiați intensiv de numeroși matematicieni și fizicieni, precum matematicianul britanic Arthur Cayley, pe care l-au interesat aplicațiile lor în chimia organică, de ex. grafurile chimice, sau fizicianul german G. R. Kirchhoff, care a studiat această categorie pornind de la studiul rețelelor electrice.

Propoziții și teoremeFie un graf neorientat G=(V,E), unde V e mulțimea vârfurilor, iar E cea a muchiilor sale. Următoarele afirmații sunt echivalente:G este arbore.G este un graf conex minimal („minimal” se numește proprietatea unui graf, că dacă i se elimină orice muchie, se obține un graf neconex).G este un graf fără cicluri maximal („maximal” se numește proprietatea unui graf, că dacă i se adaugă orice muchie, se obține un graf care are măcar un ciclu, și deci nu e arbore).Un arbore cu n ≥ 2 vârfuri conține cel puțin două vârfuri terminale.Orice arbore cu n vârfuri are n-1 muchii.

Created on 11/9/2014 2:56:00 PM 5

Created by Pastravanu Marius Page 6 4/19/2023

Ordine și grade 2

Drumuri într-un graf 2

Conexiune 3

Noțiuni asociate 3

Aplicații 4

ARBORE(TEORIA GRAFURILOR) 4

Istorie 4

Propoziții și teoreme 5

Created on 11/9/2014 2:56:00 PM6