Teoria Grafurilor.

Noțiuni introductive.

 Def. Se considera mulțimile finite X = { x₁, x₂, …, x_n} si mulțimea U, care este produsul cartezian al mulțimii X cu ea insăși.

Se numește graf o pereche ordonata de multimi (X, U), X fiind o multime finita si nevida de elemente numite varfuri sau noduri, iar U o multime de perechi (submultimi cu cate doua elemete) din X,  numite muchii sau arce.

Multimea X se numeste multimea nodurilor sau varfurilorr, iar multimea U se numeste multimea muchiilor sau arcelor.

Un graf va fi notat G = (X, U), iar in figurarea sa nodurile se vor desena prin numere sau litere, iar muchiile prin linii neorientate si arcele prin linii orientate.

Def. Se spune ca multimea U are propietatea de simetrie daca si numai daca avand [x_k, x_i] in U rezulta si [x_i, x_k] tot in U.

Def. Daca multimea U are propietatea de simetrie se spune ca graful este un graf neorientat.

Def. Daca multimea U nu are propietatea de simetrie se spune ca graful este un graf orientat sau directionat sau digraf.

Pentru un arc (x_i, x_j), x_i este numit baza arcului sau originea sau extremitatea initiala iar x_j este numit varful grafului sau extremitatea finala sau terminala. Se mai spune ca xi si x_j sunt adiacente. Astfel arcul (x_i, x_j) este incident spre exterior cu x_i si incident spre interior cu x_j.

Daca un varf nu este nici extremitate initiala si nici extremitate finala pentru nici un arc atunci el este varf izolat.

Metode de reprezentare

 Reprezentarea geometrică.

Graf neorientat

Graf orientat

Fie graful G = (X, U) unde X = {1, 2, 3, 4, 5, 6}

                             U = {(1, 2); (2, 3); (1, 4), (4, 5); (2, 6)}

Reprezentarea vârfurilor se va face printr-un cerculeț in interiorul căruia se va trece numărul corespunzător vârfului sau o literă. Reprezentarea arcului se va face printr-o linie care unește cele două vârfuri figurându-se și sensul.

Def. Se considera graful G= (X, U). Daca multimea U este vida atunci graful se numeste nul si reprezentarea lui se reduce la figurarea unor puncte izolate.

Def. Se numeste gradul unui varf x al unui graf numarul de muchii incidente cu x si se noteaza cu d(x).

Daca un varf are gradul 0 atunci el este varf izolat iar daca are gradul 1 atunci el este varf terminal.

Conventie:  Fie un graf G = (X, U). Atunci  unde n este numarul de varfuri iar m este numarul de muchii al grafului.

Corolar. Fiecare graf are un numar par de varfuri cu grad impar.

Def. Fie graful G=(X, U) si V  inclusă în U. Graful Gp= (X, V)  se numeste graf partial al grafului G.

Numărul de grafuri parţiale ale lui G este  2^m.

Soluţie: Numerotăm muchiile grafului de la 1 la m. Fiecărui graf parţial îi putem asocia în mod biunivoc o funcţie f:{1, 2, 3, …, m} à {0, 1}  astfel: dacă muchia numerotată i aparţine grafului parţial va avea valoarea 1 și 0 dacă nu aparține.

Numărul de grafuri parţiale este egal cu numărul de funcţii definite, adică 2^m (considerăm că un graf este parţial al său).

Def. Fie graful G=(X, U). se numeste graf complementar al grafului G, graful Gc=(X, U’) cu prop. ca doua varfuri sunt adiacente in Gc daca ele nu sunt adiacente in G.

Def. Fie graful G=(X, U) si Y  inclusa in X. Fie V inclusă in U, unde V contine toate muchiile din U care au extremitatile in multimea Y. Graful Gs=(Y, V)  se numeste graf subgraf al grafului G.

Def. Se considera U = X x X – D. Atunci graful G=(X, U) se numeste graf complet si se noteaza K_n (n fiind numarul de varfuri al grafului). Si D = { (x, x) | x  apartine lui X }

Prop. K_n este graf neorintat cu n varfuri are  n(n-1)/2 muchii.

Def. Graful G se numeste bipartit daca exista doua multimi nevide A si B astfel incat X = A U B si A Ç B =  Æ si orice muchie u a lui U are o extremitate in A si cealalta in B.

Def. Graful G bipartit se numeste bipartit complet  daca intre orice varf x_i din  A si orice varf x_k din B exista muchia [x_i, x_k].