1. Noţiuni introductive
Există mai multe moduri echivalente de definire a arborilor. Din punctul de vedere al teoriei grafurilor numim arbore un graf neorientat conex şi fără cicluri. Dacă graful este aciclic, dar nu este conex îl vom numi pădure.
De exemplu,
Fig. 1.
a. este arbore, b. este pădure, nefiind conex, iar c. nu este nici arbore, nici pădure, deoarece conţine cicluri.
1.1. Proprietăţi ale arborilor
Teorema 1
Fie G (V, U) un graf neorientat. Următoarele afirmaţii sunt echivalente:
1) G este arbore.
2) Oricare două vârfuri din G sunt unite printr-un lanţ simplu unic.
3) G este conex minimal (dacă suprimăm o muchie, graful obţinut este neconex).
4) G este conex şi are V -1 muchii.
5) G este aciclic şi are V -1 muchii.
6) G este aciclic maximal (dacă adăugăm o muchie, graful obţinut conţine cicluri).
Demonstraţie:
1 2
Dacă G este arbore, atunci G este conex, deci oricare ar fi două vârfuri din graf, acestea sunt unite prin cel puţin un lanţ simplu. Presupunem prin reducere la absurd că există x şi y două vârfuri unite prin două lanţuri simple distincte l1 şi l2 .
Fig. 2.
Fie z primul vârf de la care cele două lanţuri se despart, iar t primul vârf în care cele două lanţuri se întâlnesc din nou. Dacă notăm l'1 porţiunea de pe lanţul l1 între z şi t, iar cu l'2 porţiunea de pe lanţul l2 între z şi t, atunci l'1 şi l'2 nu au vârfuri comune, cu excepţia vârfurilor z şi t. Concatenând l'1 şi l'2, obţinem un ciclu- contradicţie cu ipoteza că G este arbore. Deci, oricare două vârfuri din graf sunt unite printr-un lanţ simplu unic.
2 3
Dacă oricare două vârfuri x, y V sunt unite printr-un lanţ simplu unic, atunci orice muchie x, y U reprezintă unicul lanţ dintre x şi y. Suprimând muchia x, y , între x şi y nu va mai exista lanţ, deci graful obţinut nu va mai fi conex.
3 4
Notăm cu n numărul de vârfuri şi cu m numărul de muchii din graf.
Pentru a demonstra că orice graf conex minimal are n-1 muchii vom demonstra prin inducţie completă după n că m n-1. Cum în orice graf conex m n-1, deducem m n-1.
P(1) Dacă n 1, atunci m 0 m n-1.
P(2) Dacă n 2, atunci m 1 m n-1.
P(n) Presupunem că într-un graf conex minimal cu cel mult n vârfuri numărul de muchii este strict mai mic decât numărul de vârfuri.
P(n 1) Demonstrăm că într-un graf conex minimal cu n 1 vârfuri, numărul de muchii este cel mult egal cu n.
Fie G conex minimal cu n 1 vârfuri şi m muchii. Eliminând o muchie oarecare din graf obţinem un graf G' cu m-1 muchii şi două componente conexe C1 şi C2 cu n1, respectiv n2 vârfuri (n1 n2 n 1) şi m1, respectiv m2 muchii (m1 m2 m-1). Subgrafurile C1 şi C2 sunt conexe minimale, altfel graful G nu ar fi conex minimal. Din ipoteza inductivă rezultă că m1 n1-1, m2 n2-1; dar m1 m2 m-1 n1 n2 n-2 m n-1. Deci G conex minimal implică G conex cu n-1 muchii.
4 5
Fie G un graf conex cu n-1 muchii. Să demonstrăm că G este aciclic.
Presupunem prin reducere la absurd, că graful G conţine un ciclu C format din vârfurile v1, v2, ..., vk.
Să considerăm subgraful parţial Gk (Vk, Uk) constând din ciclul C. Deci Vk v1, v2 ,..., vk , iar Uk v1,v2) , v2,v3 ,..., vk-1,vk , (vk,v1 ( Vk Uk k). Dacă Vk < V , atunci vi Vk şi vk 1 V-Vk astfel încât vi, vk 1 U, graful G fiind conex.
Construim Gk 1 (Vk 1, Uk 1) astfel :Vk 1 Vk vk 1 ; Uk 1 Uk vi,vk 1 şi Uk 1 Vk 1 k 1.
Cât timp k 1 < n, aplicăm acelaşi procedeu până când obţinem un graf Gn (V, Un), cu Un n, Un U; deci U n, contradicţie cu ipoteza U n-1.
5 6
Presupunem că graful G este aciclic cu n-1 muchii, să demonstrăm că G este aciclic maximal.
Fie C1, C2,..., Cp cele p componentele conexe ale grafului G, având respectiv n1, n2,..., np vârfuri şi m1, m2,..., mp muchii fiecare. Evident că n1 n2 ... np n şi m1 m2 ... mp n-1.
Cum graful G este aciclic, deducem că fiecare componentă conexă este un arbore. Deoarece am demonstrat că 1 5, rezultă că m i ni-1, i 1, 2, ..., p . Înlocuind în relaţia de mai sus, obţinem n-p n-1 p 1, deci G conex. Dacă G este conex şi aciclic, conform definiţiei G este arbore. Dar am demonstrat că 1 2, deci oricare două vârfuri din G sunt unite printr-un lanţ simplu. Astfel, adăugând orice muchie obţinem un ciclu.
6 1
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
