fbpx

Teoria Grafurilor – Lant. Ciclu. Arbore

0

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

Un exemplu de graf ce contine mai multe tipuri de lanturi

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

In aceasta imagine avem mai multe cicluri.

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:

  1. G este arbore
  2. G este un graf conex, minimal in raport cu aceasta proprietate (eliminand o muchie oarecare, se obtine un graf ne-conex)
  3. 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

Arbore

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More