Grafuri

Grafuri neorientateUn graf neorientat reprezinta o pereche de multimi G=(X,U), unde X este o multime finita si nevida, numita multimea nodurilor, si U este o multime formata din perechi de elemente ale lui X, numita multimea muchiilor.

In figura alaturata:X={1,2,3,4,5,6} sunt noduriU={[1,2], [1,4], [2,3],[3,4],[3,5]} sunt muchiiG=(X, U)=({1,2,3,4,5,6}, {[1,2], [1,4], [2,3],[3,4],[3,5]})ProprietatiAdiacenta: ntr-un graf neorientat existena muchiei (v,w) presupune c w este adiacent cu v i v adiacent cu w. n exemplul din figura de mai sus vrful 1 este adiacent cu 4 dar 1 i 3 nu reprezint o pereche de vrfuri adiacente.Incidenta presupune ca o muchie este incident cu un nod dac l are pe acesta ca extremitate. Muchia (v,w) este incident n nodul v respectiv w.

GradulGradul unui nod x, dintr-un graf neorientat, este un numr natural ce reprezint numrul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv);Nod izolat = Un nod cu gradul 0;Nod terminal = Un nod cu gradul 1;

Nodul 5 este terminal (gradul 1).Nodul 6 este izolat (gradul 0)Nodurile 1, 2, 4 au gradele egale cu 2. LantulLant = este o secven de noduri ale unui graf neorientat G=(X,U), cu proprietatea c oricare dou noduri consecutive din lant sunt adiacente:Lungimea unui lan = numrul de muchii din care este format. Lan elementar = lanul care conine numai noduri distincteLan simplu = lanul care conine numai muchii distincteLan compus = lanul care nu este format numai din muchii distincte

CiclulCiclu = Un lan n care primul nod coincide cu ultimul.Ciclul este elementar dac este format doar din noduri distincte, excepie fcnd primul i ultimul. Lungimea unui ciclu nu poate fi 2. Graf partial = Dac dintr-un graf se suprim cel puin o muchie atunci noul graf se numete graf parial al lui G.Subgraf = Dac dintr-un graf se suprim cel puin un nod mpreun cu muchiile incidente lui, atunci noul graf se numete subgraf al lui G.Graf complet = graf neorientat n care exist muchie ntre oricare dou noduri.

Exemple

Succesiunea de vrfuri 2, 3, 5, 6 reprezint un lan simplu i elementar de lungime 3.Lanul 5 3 4 5 6 este simplu dar nu este elementar.Lanul 5 3 4 5 3 2 este compus i nu este elementar.Lanul 3 4 5 3 reprezint un ciclu elementar

Graful GGraful G1Graful G1 este graf partial a lui G

Graful G2Graful G2 este subgraf a lui GConexitateGraf conex = graf neorientat G=(X,U) n care pentru orice pereche de noduri (v,w) exista un lant care le uneste.Component conex = subgraf al grafului de referin, maximal n raport cu proprietatea de conexitate (ntre oricare dou vrfuri exist lan);

Graf conexGraf neconex cu 2 componente conexe

Lant/Ciclu HamiltonianGraf hamiltonian = un graf G care conine un ciclu hamiltonian Lan hamiltonian = un lan elementar care conine toate nodurile unui graf Ciclu hamiltonian = un ciclu elementar care conine toate nodurile grafului

Lant Hamiltonian

Ciclu HamiltonianLant/Ciclu EulerianGraf eulerian = un graf care conine un ciclu eulerian. Lan eulerian = un lan simplu care conine toate muchiile unui graf Ciclu eulerian = un ciclu simplu care conine toate muchiile grafului

Lantul: L=[1.2.3.4.5.3.6.2.5.6] este lant eulerianCiclul: C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian

Grafuri orientateUn 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.

In graful din fig. 1 X={1, 2, 3, 4, 5, 6, 7} siU={u1, u2, u3, u4, u5, u6, u7, u8, u9, u10}Conexitate in grafuri orientateUn 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.

Graful este conex pentru ca oricum am lua doua noduri putem ajunge de la unul la celalalt pe un traseu de tip lantComponenta conexaComponenta conexa a unui graf G=(X, U), reprezinta un subgraf G1=(X1, U1) conex, a lui G, cu proprietatea ca nu exista nici un lant care sa lege un nod din X1 cu un nod din X-X1

Distingem doua componente conexe: G1 =(X1, U1), unde X1={1,2,3} si U1={u1, u2, u3}; si G2=(X2, U2), unde X2={4,5,6} si U2={u4, u5}. Graf tare conexGraful tare conex este un graf orientat G=(X, U), daca pentru oricare doua noduri x si y apartin lui X, exista un drum de la x la y precum si un drum de la y la x.

SfarsitProiect realizat si prezentat deBucur Radu ValerianIova Valentin