Fandom

Math Wiki

Teoria grafurilor

1.029pages on
this wiki
Add New Page
Comments0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Multiseturi Edit

Conceptul de multiset reprezintăă o generalizare a nţiunii matematice elementare de mulțime. Un multiset reprezintă o mulţime în care fiecare dintre elementele ei se poate repeta de un număr prestabilit de ori.

Definiţie. Fie S o mulţime finită nevidă. Un multiset (mulţime cu repetiţie) peste S este o pereche R = (S, r) \! formată din mulţimea S şi o funcție r: S \rightarrow \mathbb N, \! numită funcţie multiplicitate (sau repetiţie) a elementelor din S. Această funcţie are rolul de a "ţine minte" de câte ori se repetă fiecare element din mulţimea S.

Vom spune că R= (S, r) \! este un m-multiset dacă numărul total al elementelor acestuia (ţinând cont de multiplicităţi) este m.


Notaţii:

S^m = \{ (x_1, x_2, \cdots , x_n) x_i \in S \}; \!
S^{ \langle m \rangle }= \{ X \; | \mbox{X este m - multiset peste S} \}; \!
S^{( m ) }= \{ X \; | X \subset S , \; |X| =m \}; \!
S^* = U_{m \ge 0} S^m \!
S^{\langle * \rangle } =U_{m \ge 0} S^{\langle m \rangle }  \!
S^{( *) } =U_{m \ge 0} S^{( m ) }.  \!

Definirea grafului prin multiset Edit

Cu ajutorul conceptului de multiset putem defini noţiuni ca: graf neorientat, graf orientat şi izomorfism de grafuri. Această perspectivă permite grafurilor să aibă bucle, precum şi un număr oricât de mare de muchii între oricare două noduri ale sale.

Vom prezenta şi alte noţiuni ca: hipergraf, hipergraf k -uniform, şi graf suport.


Definiţie. Un graf neorientat peste V este o pereche G = (V, E), \! unde E=(V^{\angle 2 \rangle }, r) \! este un multiset peste V^{\angle 2 \rangle }. Un element e = uv \! se numeşte muchie din E, iar dacă u=v, \! acesta se numeşte buclă. Dacă r(e) \le p, \; \forall e \in E, \! atunci G se numeşte p-graf.


Teoria grafurilor 3.png Teoria grafurilor 4.png Teoria grafurilor 5.png Teoria grafurilor 6.png Teoria grafurilor 7.png Teoria grafurilor 8.png Teoria grafurilor 9.png Teoria grafurilor 10.png Teoria grafurilor 21.png Teoria grafurilor 22.png Teoria grafurilor 23.png Teoria grafurilor 24.png Teoria grafurilor 25.png Teoria grafurilor 26.png Fișier:Teoria grafurilor 27.png Fișier:Teoria grafurilor 28.png Fișier:Teoria grafurilor 29.png Fișier:Teoria grafurilor 30.png Teoria grafurilor 21.png Teoria grafurilor 22.png Teoria grafurilor 23.png Teoria grafurilor 24.png Teoria grafurilor 25.png Teoria grafurilor 26.png Teoria grafurilor fig.1.png Teoria grafurilor fig.2.png


Graf orientat

Un graf orientat reprezinta o pereche ordonata de multimi G=(X,U), unde X este o multime finita si nevida, numita multimea nodurilor, si U este o multime formata din perechi ordonate de elemente ale lui X, numita multimea arcelor.

Exemplu

In graful din fig. 1 multimea nodurilor este X={1, 2, 3, 4, 5, 6, 7} si multimea arcelor este U={u1, u2, u3, u4, u5, u6, u7, u8, u9, u10}={(1,2), (2,3), (3,4), (4,1), (3,5), (5,3), (5,6), (6,7), (7,6), (7,5)}.

2.Conexitate in grafuri orientate

Un graf G este conex, daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga.

Un lant intr-un graf orientat este un sir de arce {u1, u 2, u3 , …, un} cu proprietatea ca oricare doua arce consecutive au o extremitate comuna. Altfel spus, un lant este un traseu care uneste prin arce doua noduri numite extremitatile lantului, fara a tine cont de orientarea arcelor componente.

Exemplu

Graful este conex pentru ca oricum am lua doua noduri putem ajunge de la unul la celalalt pe un traseu de tip lant. De exemplu, de la nodul 4 la nodul 2 putem ajunge pe traseul de noduri (4,3,2) stabilind astfel lantul {u5, u3}, dar si pe traseul de noduri (4,1,2) stabilind lantul {u6, u2}


Resurse Edit

Also on Fandom

Random Wiki