Conexitate

                                         Conexitate

Lant

Definitie: Fie G=(V, U) un graf orientat. Se numeşte lant, în graful G, o succesiune de arce, notată 
L=[ui1 ,ui2 ,...,uik] cu proprietatea ca oricare două arce consecutive au o extremitate comună (nu are importantă orientarea arcelor). 

Se întâlnesc notiunile: 

- extremitătile lantului 
• fiind dat lantul L=[ui1 ,ui2 ,...,uik] se numesc extremităti ale sale extremitatea arcului ui1 care nu este 
comună cu arcul ui2 şi extremitatea arcului uik care nu este comună cu arcul uik-1 
- lungimea lantului 
• fiind dat lantul L=[ui1 ,ui2 ,...,uik] prin lungimea sa se întelege numărul de arce care apar în L; 

• Exemplu de lant: 
cu reprezentarea grafică astfel: 
Fie graful G=(V, U), unde: V={1,2,3,4,5} 
                                                U={(1,3),(1,4), (2,3), (2,4), (5,2)}= { u1, u2, u3, u4, u5 } 

L1=[ u1 ,u3 ,u5] este, în graful G, lanŃ cu lungimea 3 şi extremităŃile 1 şi 5. 
L2=[ u1 ,u2, u4, u5] este, în graful G, lanŃ cu lungimea 4 şi extremităŃile 3 şi 5. 


Atentie! Dacă L=[ui1 ,ui2 ,...,uik] este lant în graful G, atunci şi L=[uik ,uk-1 ,...,ui1] 

 este lant în graful G. 

Drum

Definitie: Fie G=(V, U) un graf orientat. Se numeşte drum, în graful G, o succesiune de noduri, notată D=(xi1 ,xi2 ,...,xik), cu proprietatea (xi1 ,xi2),..., (xik-1 ,xik) ∈ U(altfel spus (xi1 ,xi2),..., (xik-1 ,xik) sunt arce).

Se întâlnesc notiunile: 

- extremitătile drumului 
• fiind dat drumul  D=(xi1 ,xi2 ,...,xik) se numesc extremităti ale sale nodurile xi1 şi xik (xi1 extremitate initială şi xik extremitate finală) - lungimea drumului 
• fiind dat drumul D=(xi1 ,xi2 ,...,xik) , prin lungimea sa se întelege numărul de arce care apar în cadrul său; • Exemplu de drum:
Fie graful G=(V, U) unde:
V={ 1,2,3,4,5 }
U={(1,3), (4,1), (3,2), (2,4), (5,2)}
cu reprezentarea grafică astfel: 

D1=(1, 3, 2) este, în graful G, drum cu lungimea 2 şi extremitătile 1 şi 2. 

D2=(4, 1, 3, 2) este, în graful G, drum cu lungimea 3 şi extremitătile 4 şi 2

Atentie! Dacă D=(xi1 ,xi2 ,...,xik) este drum, în graful G, atunci nu neapărat şi D1=(xik ,xik-1 ,xi) este drum, în graful G.

Definitie: Fie G=(V,U) un graf orientat. Se numeşte drum elementar, în graful G, drumul 

 D=(xi1 ,xi2 ,...,xik) cu proprietatea că oricare două noduri ale sale sunt distincte (altfel spus, printr-un nod nu se trece decât o singură dată). 

• Exemplu: în graful de mai jos, 

     

drumul D1=(4, 1, 3, 2) este drum elementar.

Definitie: Fie G=(V, U) un graf orientat: Se numeşte drum neelementar, în graful G, drumul 

D=(xi1 ,xi2 ,...,xik) cu proprietatea că nodurile sale nu sunt distincte două câte două (altfel spus, prin anumite noduri s-a trecut de mai multe ori). 

• Exemplu: în graful de mai jos,

drumul D2=(4, 1, 3, 2, 4, 5, 2) este drum neelementar (prin 4 (şi 2) 

s-a trecut de două ori).

Definitie Un drum hamiltonian într-un graf orientat este un drum care conţine toate vârfurile grafului.

Circuit

Definitie: Fie G=(V, I) un graf neorientat. Se numeşte circuit, în graful G, drumul D=(xi1 ,xi2 ,...,xik) 

cu proprietatea că xi1 = xik şi are arcele cel compun diferite două câte două (circuitul se notează în continuare cu C). 

• Exemplu: în graful de mai jos, 

drumul C=(1, 3, 2, 4, 1) este circuit. 

Definitie: Fie G=(V, U) un graf orientat. Se numeşte circuit elementar, în graful G, un circuit cu proprietatea că oricare două noduri ale sale, cu exceptia primului şi a ultimului, sunt distincte. 

• Exemplu: în graful de mai jos, 

circuitul C=(1, 3, 2, 4, 1) este circuit elementar. 

Definitie: Fie G=(V, U) un graf orientat. Se numeşte circuit neelementar, în graful G, un circuit cu 

proprietatea că nodurile sale, cu exceptia primului şi a ultimului, nu sunt distincte. 

• Exemplu: în graful de mai jos 

circuitul C=(1, 3, 4, 2, 5, 4, 1) este circuit neelementar (prin 4 s-a trecut de două ori). 

Definitie : Intr-un graf orientat G=(X,U) se numeşte circuit hamiltonian un circuit elementar care conţine toate vârfurile grafului. 

Definitie:  Intr-un graf orientat G=(X,U) se numeşte circuit eulerian un circuit care conţine toate 
arcele grafului. 

Definitie: Se numeşte graf eulerian un graf care conţine un circuit eulerian. 

Graf conex

Definitie: Fie G=(V, U) un graf orientat. Graful G se numeşte conex dacă pentru oricare două vârfuri x şi y,  x#y, există un lant de extremităti x şi y. 

• Exemplu de graf care este conex: 

Graful este conex, deoarece oricare ar fi vârfurile x şi y, x#y, există un lant in G care să le lege. 

• Exemplu de graf care nu este conex: 

  Graful nu este conex, deoarece există două vârfuri, cum ar fi 1 şi 4, pentru care nu există nici un lant în graf 

care să le lege. 

Definitie: Un graf este tare conex dacă pentru oricare două vârfuri x, y  X există un drum de la x la y şi un drum de la y la x.

Exemplu:
-Graf tare conex

Componentă conexă 

Definitie: Fie G=(V, U) un graf orientat. Se numeşte componentă conexă un graf orientat G1=(V1 ,U1) care verifică următoarele conditii: 

- este subgraf al grafului G; 

- este conex; 

- nu există nici un lant în G care să lege un nod din V, cu an nod din V-V1. 

• Exemplu: Fie graful G=(V, U) : V={1,2,3,4,5} şi U={(1,2), (3,1), (3,2), (4,5)} 

Pentru graful de mai sus, graful G1=(V1,U1) unde: V1={4,5} şi U1={(4,5)} este componentă conexă, 

deoarece: 

- este subgraf al grafului G; 

- este conex; 

- nu există nici un lant în G care să lege un nod din V, cu un nod din V-V1={1,2,3} 

La fel, se poate spune şi despre graful G2=(V2,U2) unde: V2={1,2,3) şi U2={(1,2)> (3,1), (3,2)} 

În concluzie, graful din figura de mai sus este format din două componente conexe. 

Observatie: Fie G=(V, U) un graf orientat. Graful G este conex dacă şi numai dacă este format dintr-o 

singură componentă conexă. 

• Exemplu de graf conex (este format dintr-o singură componentă conexă):

Definitie: O componentă tare conexă a unui graf orientat G=(X, U) este un subgraf G1=(X1,Y1) al lui G care este tare conex şi care este maximal în raport cu această proprietate (adică oricare ar fi x  X\X1,
subgraful lui G generat de X1{x} nu mai este tare conex).

Exemplu:
-Graf cu doua componente tare conexe