curs 4: arbori

Curs 4: ArboriTeoria grafurilor

Radu Dumbraveanu

Universitatea de Stat “A. Russo” din Balt, iFacultatea de S, tiint,e Reale

Aceasta prezentare este pusa la dispozitie sub Licenta Atribuire -Distribuire-ın-conditii-identice 3.0 Ne-adaptata (CC BY-SA 3.0)

Balt, i, 2013

R. Dumbraveanu (USARB) Curs 4: Arbori Balt,i, 2013 1 / 23

Arbori

Un arbore este un graf conex fara cicluri.

Vırfurile de gradul 1, ıntr-un arbore, se numesc frunze.

Arborele care consta doar dintr-un vırf se numes, te arbore trivial; adica K1.

Orice arbore netrivial are cel put, in o frunza.

Arbori

Arbori; Punt, i

Conexitatea arborelui este una slaba; este de ajuns sa suprimam o muchiesau un vırf care nu-i frunza din arbore s, i graful obt, inut nu mai este conex.

Din acest punct de vedere arborii sınt grafuri minimal conexe.

TeoremaUn graf conex G este arbore daca s, i numai daca orice muchie a sa estepunte.

Arbori; Punt, i

Conexitatea arborelui este una slaba; este de ajuns sa suprimam o muchiesau un vırf care nu-i frunza din arbore s, i graful obt, inut nu mai este conex.

Din acest punct de vedere arborii sınt grafuri minimal conexe.

TeoremaUn graf conex G este arbore daca s, i numai daca orice muchie a sa estepunte.

Arbori; Punt, i

Demonstratie.Suficient, a. Fie G conex s, i orice muchie e punte. Atunci nici o muchie nupoate sa se cont, ina ıntr-un ciclu.Deci este aciclic.Suficient, a. Fie G arbore, deoarece nu cont, ine cicluri reiese ca fiecaremuchie este punte.

Arbori; Punt, i

Lant, unic

TeoremaIntr-un arbore pentru oricare doua vırfuri distincte, exista un unic lant,elementar care le unes, te.

Demonstratie.Fie G = (V ,E) un arbore.Presupunem, prin absurd, ca exista doua vırfuri diferite u s, i v pentru careG cont, ine cel put, in doua u − v-lant, uri elementare distincte.Notam aceste lant, uri prin P1 s, i P2.Intrucıt P1 6= P2 exista cel put, in un vırf x care apart, ine P1 s, i nu apart, ineP2.Dar atunci exista o muchie e = xy ın P1 care nu apart, ine P2.

Lant, unic

Demonstrat, ie; Continuare.Din cele de mai sus reiese ca subgraful (P1 ∪ P2)− e este conex; adicacont, ine un x − y-lant, .Dar ın as, a caz subgraful (P1 ∪ P2) + e va cont, ine un ciclu, ceea ce esteimposibil deoarece G este arbore.

Lant, unic

Demonstrat, ie; Continuare.Din cele de mai sus reiese ca subgraful (P1 ∪ P2)− e este conex; adicacont, ine un x − y-lant, .Dar ın as, a caz subgraful (P1 ∪ P2) + e va cont, ine un ciclu, ceea ce esteimposibil deoarece G este arbore.

Lant, unic

CorolarUn graf este arbore daca s, i numai daca pentru oricare doua vırfuridistincte, exista un unic lant, elementar care le unes, te.

Demonstratie.Evident, daca orice doua vırfuri sınt unite printr-un unic lant, reiese ca Geste ın I rınd conex s, i ın al II-lea rınd aciclic.

Lant, unic

CorolarUn graf este arbore daca s, i numai daca pentru oricare doua vırfuridistincte, exista un unic lant, elementar care le unes, te.

Demonstratie.Evident, daca orice doua vırfuri sınt unite printr-un unic lant, reiese ca Geste ın I rınd conex s, i ın al II-lea rınd aciclic.

Numarul de vırfuri vs. numarul de muchii

Teorema

Daca G este un arbore atunci ‖G‖ = |G| − 1.

Demonstratie.Demonstram prin induct, ie tare pe n = |G| (numarul de vırfuri).Pasul I: Pentru n = 1 avem graful trivial la care numarul de muchii este 0.Deci teorema este verificata.Pasul I: Presupunem ca teorema este adevarata pentru orice arbore cunumarul de vırfuri mai mic decıt n.Fie G un arbore cu n vırfuri, n ≥ 2.Alegem o muchie e = uv ∈ E(G); atunci unicul u − v-lant, este ınsas, imuchia e.

Teorema

Numarul de vırfuri vs. numarul de muchiiDemonstrat, ie; Continuare.Atunci G − e este neconex s, i G − e consta exact din doua componente;fiecare dintre acest doua componente fiind arbore.

Notam prin G1 s, i G2 acess, i doi arbori.

Demonstrat, ie; Continuare.Evident, |G1|, |G2| < n; dar atunci

‖G1‖ = |G1| − 1 (1)

s, i‖G2‖ = |G2| − 1. (2)

Aplicınd (1) s, i (2) obt, inem

‖G‖ = ‖G1‖+ ‖G2‖+ 1= (|G1| − 1) + (|G2| − 1) + 1= |G1|+ |G2| − 1 = |G| − 1.

Demonstrat, ie; Continuare.Evident, |G1|, |G2| < n; dar atunci

‖G1‖ = |G1| − 1 (1)

s, i‖G2‖ = |G2| − 1. (2)

Aplicınd (1) s, i (2) obt, inem

‖G‖ = ‖G1‖+ ‖G2‖+ 1= (|G1| − 1) + (|G2| − 1) + 1= |G1|+ |G2| − 1 = |G| − 1.

CorolarOrice arbore netrivial are cel put, in doua vırfuri cu gradul 1.

Demonstratie.Fie G = (V ,E) un (n,m)-arbore netrivial atunci∑

v∈V d(v) = 2m= 2(n − 1)= 2n − 2.

Pe de alta parte G este netrivial s, i deci d(v) ≥ 1, ∀v ∈ V .Reiese ca G trebuie sa aiba cel put, in doua vırfuri cu gradul 1.

v∈V d(v) = 2m= 2(n − 1)= 2n − 2.

Arbori “scufundate” ın alte grafuri

TeoremaFie G un arbore cu m muchii s, i H un graf cu δ(H ) ≥ m. Atunci H are unsubgraf izomorf cu G.

Arbore de acoperire

Definit, ieUn subgraf de acoperire conex s, i fara cicluri se numes, te arbore deacoperire.

Doar un graf conex poate avea arbore de acoperire.

Arbori de acoperire

De la stınga spre dreapta: un graf ımpreuna cu doi arbori de acoperire ai sai

Aplicat, ii ale arborilor de acoperire

Arbori de acoperire

CorolarOrice graf conex G cont, ine un arbore de acoperire.

Demonstratie.Fie H un subgraf minimal de acoperire al lui G care este conex.Atunci pentru orice muchie e din H , H − e nu mai este conex.Reiese ca orice muchie a lui H este punte, concludem ca H este unarbore.

Arbori de acoperire

CorolarDaca G este conex atunci ‖G‖ ≥ |G| − 1.

Demonstratie.Fie H un arbore de acoperie al lui G atunci pe de o parte ‖H‖ = |H | − 1,iar pe de alta parte ‖G‖ ≥ ‖H‖ s, i |G| = |H |.

Arbori de acoperire

CorolarUn graf conex G este arbore daca s, i numai daca ‖G‖ = |G| − 1

Demonstratie.Necesitatea a fost deja demonstrata.Suficient, a. Presupunem, prin absurd, ca G nu este arbore.Atunci pentru doua vırfuri u s, i v putem gasi doua uv-lant, uri elementare.Reiese ca G cont, ine un ciclu C .Fie e o muchie din C atunci G − e ramıne conex.Dar atunci ‖G − e‖ = ‖G‖ − 1 s, i ‖G − e‖ = n − 2 adica G − e nu maieste conex; Contradict, ie.

Numarul de arbori de acoperire

In general, dupa cum s-a observat, un graf conex poate avea mai mult deun arbore de acoperire.

Vom nota prin τ(G) numarul de arbori de acoperire ale grafului G.

Evident, daca G este arbore atunci τ(G) = 1.

Numarul de arbori de acoperire

TeoremaDaca G este un graf conex atunci

τ(G) = τ(G − e) + τ(G/e) ∀e ∈ E(G).

Acesta teorema poate fi utilizata pentru a calcula, ıntr-un mod recursiv,numarul de arbori de acoperire a unui graf conex.

Aplicat, ii

G1 = G − v0v1

G2 = G/v0v1

G3 = G1 − v1v2

G4 = G1/v1v2

G5 = G − v2v4

G6 = G/v2v4

τ(G) = τ(G1) + τ(G2)= (τ(G3) + τ(G4)) + (τ(G5) + τ(G6))= (2 + 3) + (3 + 4)= 12.

curs 4: arbori

Education