Un arbore este un caz special al unui grafic cel mai folosit în programare.
Există destul de mulți copaci echivalenți, aici sunt doar câteva.
Un arbore este un grafic conectat fără cicluri.
Un arbore este un grafic conectat, în care pentru n-ul N există întotdeauna exact o muchie N-1.
Un arbore este un grafic, între oricare dintre cele două noduri care au o singură cale.
Este definit arbore orientat în mod similar și - ca un grafic direcționat, în care între oricare două noduri, nu există mai mult de un fel.
Un arbore este un grafic finit conectat cu un vertex distinct (rădăcină) care nu are cicluri.
Pentru fiecare pereche de noduri de copaci - noduri - există un singur traseu, deci este convenabil să clasificați nodurile în funcție de gradul de distanță de la vârful rădăcinii.
Distanța de la vârful rădăcină V0 se numește nivelul vârfului.
Deoarece traseul dintre cele două noduri este unic, atunci. aplicând această proprietate la nodurile adiacente, putem concluziona că orice ramură este o punte.
Când marginea este îndepărtată, singura rută este întreruptă și graficul se împarte în două subgrafe.
Arborele rădăcină este un arbore orientat în care este posibil să se distingă vârfuri de trei tipuri: rădăcină, frunze (alt nume: vârfuri terminale) și alte vârfuri (nonterminale); și două condiții obligatorii trebuie îndeplinite:
nu arce lasă frunzele; de la alte noduri pot exista cât mai multe arce pe care le doriți;
nici un arc nu intră în rădăcină; toate celelalte vârfuri vin într-un singur arc.
În mod tradițional, în matematică și în științele conexe (inclusiv programele teoretice), copacii "cresc" cu susul în jos: acest lucru se face simplu pentru confortul frunzelor în creștere dacă este necesar. Astfel, în figuri, rădăcina copacului este vârful de sus, iar frunzele sunt cele mai mici.
Vârful vârfului v este vârful din care provine arcul care provine de la vârful v. Descendentul vârfului v este vârful în care apare arcul care provine de la vârful v. În aceste condiții, puteți da și alte definiții la noțiunile de rădăcină și frunză: rădăcina nu are strămoși, frunza nu are descendenți.
Un arbore binar este un copac rădăcină, fiecare vârf al căruia nu are mai mult de doi descendenți. În acest caz, uneori vorbesc despre copilul din stânga și despre copilul potrivit pentru vârful actual.
Înălțimea copacului rădăcinii este numărul maxim de arce care separă frunzele de rădăcină. Dacă arborele nu este ponderat, atunci înălțimea acestuia este doar distanța de la rădăcină la cea mai exterioară coală.
Un grafic G (V, X) este un arbore dacă și numai dacă există cel puțin una dintre următoarele condiții:
1. Pentru ca un grafic simplu conectat să fie un arbore, este necesar și suficient ca numărul de vârfuri să fie mai mare decât numărul de muchii cu unul.
2. Pentru a contoriza a fost un copac, este necesar și suficient ca oricare două noduri sunt conectate prin singurul său traseu.
3. Un grafic este un arbore dacă și numai dacă adăugarea oricărei margini noi are drept rezultat apariția unui singur ciclu.
4. Graficul G (V, X) este conectat și nu conține cicluri.
5. Graficul G (V, X) este conectat. dar pierde această proprietate după ce a eliminat orice margine.
Astfel, un arbore cu n noduri are n-1 margine, deci este un grafic minimal conectat.
Plăcile suspendate, cu excepția rădăcinii, sunt numite frunze.
Scheletul unui grafic conectat este orice subgraf al acestuia. Acesta conține toate vârfurile graficului și este un arbore.
Subgraful G 1 = (V 1, E 1) din graficul G = (V. E) se numește arborele de spanning în
Articole similare
-
Cum să crească un copac de lamaie dintr-o sămânță - un pas spre sănătate
-
Cum un copac afectează sunetul unei chitări electrice - întrebările chitaristului
-
O masă luminoasă din lemn cu propriile mâini, exemple de realizare a meselor rectangulare și rotunde
Trimiteți-le prietenilor: