Teoria grafurilor

Multiseturi

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

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.

Fișier:Teoria grafurilor 27.png Fișier:Teoria grafurilor 28.png Fișier:Teoria grafurilor 29.png Fișier:Teoria grafurilor 30.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

• Lecţii complementare de teoria grafurilor (copie la Wikia)
• Introduction à la théorie des graphes (copie la Wikia), Solutions des exercices (copie la Wikia)
• Biblioteca Electronică a Studentului
• Telecomenzi si Electronica in Transporturi
• Grundlagen der Graphentheorie
• x-Referat.ro
• Graph Theory
• Applet pentru reprezentarea grafurilor cu Java