Lant
Definitii
Se numeste lant in graful G, o succesiune de varfuri L = {z1,z2,…,zk} unde z1,z2,…,zk ∈ X, cu proprietatea ca oricare doua varfuri consecutive sunt adiacente, adica muchiile [z1, z2], [z2, z3], …,[zk-1, zk] ∈ U
Pentru un lant L = {z1,z2,…,zk}, daca varfurile sunt distincte doua cate doua, atunci lantul se numeste elementar. In caz contrar, lantul este neelementar.
Daca un lant nu contine de mai multe ori aceeasi muchie, atunci el se numeste simplu.
Numarul de muchii care intra in componenta unui lant reprezinta lungimea lantului.
Exemplu
Vom analiza 4 lanturi
L1 = {1, 2, 3, 7, 4} este elementar, simplu, de lungime 4.
L2 = {6, 5, 3, 5} este neelementar si de lungime 3.
L3 = {3, 4, 7, 3, 2} este neelementar, simplu si de lungime 4.
L4 = {8, 7, 3, 5, 6} este elementar, simplu, de lungime 4.
Ciclu
Definitii
Se numeste ciclu intr-un graf, un lant L = {z1,z2,…,zk} cu proprietatea ca z1 = z2 si muchiile [z1, z2], [z2, z3], …,[zk-1, zk] sunt distincte doua cate doua.
Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar. In caz contrar, el este nelementar.
Un graf G se numeste conex daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga.
Exemplu
Analizam 3 cicluri:
C1 = {1, 2, 3, 5, 6, 1} este un ciclu elementar.
C2 = {3, 4, 7, 8, 5, 3, 2, 1, 6, 5, 3} este un ciclu neelementar.
C3 = {3, 4, 7, 8, 5, 3} este un ciclu elementar.
Arbore
Definitii
Un graf conex si fara cicluri se numeste arbore.
Fie un graf G = (X, U). Urmatoarele afirmatii sunt echivalente:
- G este arbore
- G este un graf conex, minimal in raport cu aceasta proprietate (eliminand o muchie oarecare, se obtine un graf ne-conex)
- G este un graf fara cicluri, maximal in raport cu aceasta proprietate (adaugand o muchie oarecare, se obtine un graf care are cel putin un ciclu)
Un arbore cu n varfuri are n-1 muchii.
Exemplu
