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 C₁ şi C₂ cu n₁, respectiv n₂ vîrfuri (n₁+n₂ = n+1) şi m₁, respectiv m₂ muchii (m₁+m₂ = m-1). Subgrafurile C₁ şi C₂ sînt conexe minimale, altfel graful G nu ar fi conex minimal. Din ipoteza inductivă rezultă că m₁ £ n₁-1, m₂ £ n₂-1; dar m₁+m₂ = m-1 £ n₁+n₂ = 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 v₁, v₂, …, v_k.

Să considerăm subgraful parţial G_k = (V_k, U_k) constînd  din ciclul C. Deci V_k = {v₁, v₂ ,…, v_k}, iar U_k = {[v₁,v₂)], [v₂,v₃],…,[v_k-1,v_k], (v_k,v₁]} (½V_k½=½U_k½= k). Dacă  ½V_k½<½V½, atunci  $v_iÎV_k şi v_k+1ÎV-V_k astfel încît [v_i, v_k+1]ÎU, graful G fiind conex.

Construim G_k+1 = (V_k+1, U_k+1) în modul următor: V_k+1 = V_k È{v_k+1};     U_k+1=U_kÈ{[v_i,v_k+1]} şi ½U_k+1½=½V_k+1½=k+1.

Cît timp k+1 < n, aplicăm acelaşi procedeu pînă cînd obţinem un graf  G_n = (V, U_n), cu ½U_n½= n, U_n Í 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 C₁, C₂,…, C_p cele p componentele conexe ale grafului G, avînd respectiv n₁, n₂,…, n_p vîrfuri şi m₁, m₂,…, m_p muchii fiecare. Evident că n₁+n₂+…+n_p = n  şi m₁+m₂+…+m_p = 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= n_i-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 sînt unite printr-un lanţ simplu. Astfel, adăugînd orice muchie obţinem un ciclu.

6 Þ 1

Presupunem că graful G este aciclic, dar dacă am mai adăuga o muchie s-ar obţine un ciclu. Să demonstrăm că G este conex.

Fie u şi v două vîrfuri neadiacente din graf, arbitrar alese. Deoarece adăugînd muchia [u, v] se obţine un ciclu, rezultă că u şi v sînt unite printr-un lanţ ale cărui muchii aparţin grafului G. Cum u,v au fost alese arbitrar, deducem că graful G este conex.

Q.E.D.

Teorema 2

Numerele întregi 0 < d₁ £ d₂ £ …£ d_n (n ³ 2) sînt gradele vîrfurilor unui arbore dacă şi numai dacă d₁+d₂+…+d_n = 2n-2.

Demonstraţie:

Necesitatea Condiţia este necesară, deoarece orice arbore cu n vîrfuri are n-1 muchii, iar suma gradelor vîrfurilor oricărui graf este de două ori numărul de muchii. Deci d₁+d₂+…+d_n = 2n-2.

Suficienţa Fie 0 < d₁ £ d₂ £…£ d_n astfel încît d₁+d₂+…+d_n = 2n-2.

Să demonstrăm că există un arbore cu gradele vîrfurilor d₁, d₂,…, d_n. Vom proceda prin inducţie.

P(2)                 Dacă d₁+d₂ = 2, atunci d₁ = d₂ = 1 , arborele fiind cel din figura de mai jos:

Fig. 3

P(n)                 Presupunem acum că proprietatea este adevărată pentru orice secvenţă de n numere naturale 0 < d₁ £ d₂ £ …£ d_n, astfel încît d₁+d₂+…+d_n = 2n-2.

P(n+1)             Să demonstrăm că pentru orice secvenţă 0 < d’₁ £ d’₂ £…£ d’_n £ d’_n+1 astfel încît d’₁+d’₂+…+d’_n+1 = 2n, există un arbore cu n+1 vîrfuri cu secvenţa gradelor d’₁, d’₂, …, d’_n+1.

Observăm că există măcar un nod terminal x₁ cu gradul d’₁=1, altfel dacă  d_i ³ 2,”iÎ{1, 2,…, n+1} Þ d’₁+d’₂+…+d’_n+1 ³ 2(n+1), ceea ce contrazice ipoteza. În mod analog, observăm că există măcar un nod neterminal  x_n+1, cu gradul d’_n+1 > 1, altfel dacă d’_i = 1,”iÎ{1, 2, …, n+1} Þ d’₁+d’₂+…+d’_n+1 = n+1 < 2n .

Să considerăm următoarea secvenţă de n numere întregi d’₂,…, d’_n, d’_n+1-1 cu proprietatea că d’₂+…+d’_n+d’_n+1 = 2n-2. Din ipoteza inductivă există un arbore A_n cu n vîrfuri şi secvenţa gradelor d’₂,…, d’_n, d’_n+1-1. Adăugăm la arborele A_n un vîrf pe care îl unim printr-o muchie cu vîrful avînd gradul d’_n+1-1. Obţinem un arbore A_n+1 cu gradele vîrfurilor d’₁, d’₂,…, d’_n+1.

Q.E.D.

Demonstraţia acestei teoreme oferă şi o soluţie constructivă pentru obţinerea unui arbore cu secvenţa gradelor dată.

Vom reţine gradele vîrfurilor într-un vector d de dimensiune n, ordonat crescător, cu suma componentelor egală cu 2n-2.

Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu două linii şi n-1 coloane, în care pentru fiecare muchie din arbore vom reţine extremităţile.

Spre deosebire de ideea din demonstraţie, pentru a conserva ordinea în vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 şi nu ultimul.

Capit1

Capit2_partea1

Capit2_partea2