Extras din curs
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
Preview document
Conținut arhivă zip
- SCAUT.DOC
- NOTINT1.DOC
- MULTDISJ.DOC
- HUFF.DOC
- HEAPNOU.DOC
- EXPRES.DOC
- COMPLEX.DOC
- BIBLIO.DOC
- ARBPART1.DOC
Alții au mai descărcat și
INTRODUCERE Ca urmare a gradului înalt de abstracţie atins de matematică în secolul nostru, există o tendinţă în fiecare dintre noi de a căuta să...
Introducere Teoria grafurilor este o ramură a matematicii moderne cu caracter aplicativ şi derivă din teoria mulţimilor, având originile în...
Algoritmul lui Bellman-Kalaba 1. Determinarea drumului de lungime minima într-un graf Sa atasam grafului G=(X, U) o matrice , a carei elemente...
1. MATRICI 1.1. Despre matrici Definiţie. Se numeşte matrice cu m linii şi n coloane (sau de tip ) un tablou cu m linii şi n coloane ale cărui...
ALGEBRĂ LINIARĂ CAPITOLUL 1 SPAŢII VECTORIALE §1. Spaţii vectoriale Spaţiul vectorial este una din cele mai importante structuri matematice,...
CAPITOLUL III ELEMENTE DE TEORIA DIGRAFURILOR SI GRAFURILOR Teoria digrafurilor si grafurilor este o ramura relativ tânara a matematicii. Prima...
NOTIUNI PRELIMINARE §1. Multimi, relatii binare si functii Multimi Prin multime se întelege o colectie de obiecte care vor fi numite elemente....
Serii trigonometrice Vom studia clasa particulară de serii de funcţii ()1nfx∞Σ cu ()()()()000,cossin,1, cu nnnnnfxafxanxbnxnxa≥==+≥∈⊂RR, numite...
Te-ar putea interesa și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
Introducere Teoria grafurilor este o ramură a matematicii moderne cu caracter aplicativ şi derivă din teoria mulţimilor, având originile în...
’’ Ideile, si daca sunt abstracte si daca nu, ca sa le poti manui, trebuie sa le ai. Calculatorul, ca sa-si faca treaba, trebuie sa inteleaga...
Optimizarea activităţii de planificare a etapelor de execuţie a unui proiect folosind teoria grafurilor - metoda PERT 1. Introducere Pentru ca un...
Termenul de ”graf” are cu totul altă semnificație decˆ at cel de grafic. Prima lucrare de teoria grafurilor a fost scrisă de renumitul matematician...
CAPITOLUL III ELEMENTE DE TEORIA DIGRAFURILOR SI GRAFURILOR Teoria digrafurilor si grafurilor este o ramura relativ tânara a matematicii. Prima...
Metoda grafica de rezolvare a unei PPL 1.1 Firma X importa componente pentru asamblarea a 2 modele de coputere personale: PC1 si PC2. In urma...
ELEMENTE DE TEORIA GRAFURILOR SI ANALIZA DRUMULUI CRITIC •Concepte fundamentale.Modelarea prin grafuri a proceselor economice. •Drumuri de...