Fie G - un grafic conectat. Lemnul set nod este setul de noduri ale lui G. și marginile sunt muchii ale grafului G. numit un arbore de acoperire a graficului G. Cu alte cuvinte, un arbore de acoperire a graficului G - este un subgraf care conține toate nodurile și un copac.
Exemplu. Fig. 2 prezintă un grafic cu cinci noduri și opt muchii. Patru margini selectate (împreună cu cinci noduri) constituie un arbore de acoperire a acestui grafic. Spanning copac nu este definit în mod unic.
Fig. 3 a subliniat marginile care constituie un alt arbore de acoperire a graficului (rețineți că în această figură coaste neselectate formează, de asemenea, un arbore de acoperire).
În ceea ce privește aplicate de problema găsirii unui arbore de acoperire poate fi înțeleasă ca sistemul de căutare de conexiuni între puncte fără duplicarea inutilă.
Construcția se întinde copac. Un arbore de acoperire T al lui G pot fi formate după cum urmează. Mai întâi să luăm T ca un nod arbitrar al graficului G. In plus, succesiv, construirea T copac în conformitate cu următoarea regulă: dacă graficul G are o margine care leagă nodurile u și v astfel încât u este conținută în T. și v -
Nu adăugați T la această margine cu vârful v. Noi arată că arborele rămâne în acest grafic T. În primul rând, fiecare nod adăugat este asociat cu unul dintre cele deja incluse în T., astfel încât adăugarea de noi noduri și muchii părăsește grafic T conectat. Mai mult, în graficul de timp inițial T conține un nod și nu are nici unul dintre coaste. Apoi, la fiecare pas de a construi numărul de noduri și numărul de muchii este incrementat. Astfel, numărul T de noduri pe unitate depășește numărul de marginile sale. Prin urmare, graficul T este un copac. La un anumit stadiu de extindere ulterioară a T va fi imposibil. Arătăm că, în acest caz, T este un arbore de acoperire a graficului G. adică toate nodurile grafului G pus în grafic T. Fie T“, care contine toate nodurile grafului G. neinclus în T. și toate marginile care le conectează. Pe graficul G nu are margini, care ar avea un capăt în partea de sus a T. și celălalt în T“. Deoarece graful G este conectat, T „nu poate fi un non-gol.
Fie n - numărul de noduri, și m - numărul de muchii ale grafului G. Orice arborele său se întinde T are vârfuri n și n - 1 coaste. Astfel, arborele se întinde este obținut prin aruncarea m - n + 1 numărul de muchii ale grafului G. # 61677; (G) = m - n + 1 se numește numărul cyclomatic al graficului G.
Un arbore de acoperire al unui grafic G poate fi obținut prin îndepărtarea ulterioară # 61677; (G) «inutile» coaste: fiecare
pas, aveți posibilitatea să renunțați la orice margine, în cazul în care nu conduce la o încălcare a graficului.
Să presupunem că un număr pozitiv atribuit fiecare margine a graficului, numita valoare sau greutatea sa (acest lucru poate fi, de exemplu, în cazul rețelelor de date, costul stabilirii conexiunii între punctele finale). În acest caz, graficul este încărcat. Valoarea ponderată grafice, presupunem costul total al tuturor marginilor sale. Multe dintre problemele asociate cu construcția unor sisteme eficiente de sisteme informatice sau de comunicații, ceea ce duce la problema de a găsi costul minim se întinde copac.
Fie G - graficul încărcat conectat. Vom nota cu c (T) arbitrar valoarea T graficului subgrafic G. Dacă un grafic conectat T conține toate nodurile grafului G, și are o valoare minimă între toate subgrafurilor G. având aceste două proprietăți, atunci T este un arbore de acoperire. De fapt, în cazul în care graficul conține un ciclu T, ar fi posibil să se renunțe la cel puțin o nervură și, astfel, reduce costurile T.
Noi descriem un algoritm pentru construirea unui arbore de acoperire de cost minim. Acesta se obține prin modificarea ușoară a algoritmului pentru construirea unui arbore de acoperire al unui grafic conectat. În primul rând vom lua ca T în partea de sus a graficului G. Marginea din care un cost minim. Mai mult, în timp ce
posibil T. construirea în mod constant un copac din toate marginile graficului G. de conectare noduri u ∈T și v ∉T. Am ales costul minim de o margine și se adaugă la T această margine cu vârful v. Rezultând din executarea algoritmului arbore de acoperire va avea un cost minim.
Exemplu. Fig. 4 alocat acoperă copac de cost minim. Valoarea sa este egală cu 6. Un arbore de acoperire prezentat în Fig. 2, în aceleași estimări ale nervurilor are un cost de 8, se întinde copac în Fig. 3 - costul de 8, margini neselectate în Fig. 3 constituie un arbore de acoperire