Copac acoperitor

Un capac de copac sau un arbore de legătură sau un arbore de rulment al unui grafic , conectat și cu arcuri neorientate, este un arbore care conține toate vârfurile graficului și conține doar un subset de arce, adică numai cele necesare pentru a conecta între ele toate vârfuri cu o singură cale . De fapt, ceea ce diferențiază un grafic de un copac este că în acesta din urmă nu există mai multe căi între două noduri, în imagine arcurile care fac parte dintr-un copac întins sunt afișate cu caractere aldine, în timp ce arcurile grafului original erau toate arcuri, atât îndrăznețe, cât și subtile.

Arborele care se întinde este, de asemenea, cunoscut sub termenul englezesc spanning tree ( ST ).

Definiție formală

Un copac este un anumit tip de grafic nedirectat , conectat și aciclic în cadrul căruia nu pot exista căi închise (cicluri) și pentru fiecare pereche de noduri există o singură legătură care le conectează.

Proprietate

Iată câteva dintre principalele proprietăți ale unui copac întins. ^[1]

Deține $n-1$ ${\ displaystyle n-1}$ $n-1$ arcuri, unde $n$ ${\ displaystyle n}$ $n$ este numărul de vârfuri.
Are un număr minim de margini pentru proprietatea conexiunii: prin eliminarea oricărei margini, graficul nu mai este conectat .
Are un număr maxim de arce pentru proprietatea aciclică: adăugând un arc între oricare două vârfuri, graficul nu mai este aciclic .
În interiorul copacului există o singură cale simplă între două noduri.

Arborele minim de acoperire

Același subiect în detaliu: Arborele minim de întindere .

Dacă arcurile sunt ponderate, arborele minim de întindere ( MST ) poate fi de asemenea definit. Un MST nu este altceva decât un copac întins în care, prin adăugarea greutăților arcurilor, se obține valoarea minimă dintre toți copacii posibili.

Aplicații

Conceptul de arbore de întindere este utilizat în rețelele locale , a se vedea, de asemenea, Arborele de întindere (rețea) .

Notă

^ (EN) Kevin Wayne, Greedy Algorithms II (PDF) pe cs.princeton.edu, Universitatea Princeton , Departamentul de Informatică, 18 februarie 2013. Accesat la 13 septembrie 2016 ( depus la 13 septembrie 2016).

Elemente conexe

Teorema lui Kirchhoff

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe copac

Controlul autorității	LCCN ( EN ) sh2005003951

Portal IT

Portalul de matematică

[1] (EN) Kevin Wayne, Greedy Algorithms II (PDF) pe cs.princeton.edu, Universitatea Princeton , Departamentul de Informatică, 18 februarie 2013. Accesat la 13 septembrie 2016 ( depus la 13 septembrie 2016).

[1]