Arbore (teoria grafurilor)
De la Wikipedia, enciclopedia liberă
(Redirecţionat de la Arbore (informatică))
În teoria grafurilor, un arbore este un graf neorientat, conex şi fără cicluri. Arborii reprezintă grafurile cele mai simple ca structură din clasa grafurilor conexe, ei fiind cel mai frecvent utilizaţi în practică.
Cuprins |
[modifică] Istorie
Arborii au fost studiaţi intensiv de numeroşi matematicieni şi fizicieni, precum Cayley (pe care l-au interesat aplicaţiile lor în chimia organică) sau Kirchhoff (care a studiat această categorie pornind de la studiul reţelelor electrice).
[modifică] Etimologie
Termenul de arbore a fost folosit pentru prima dată de Cayley, în anul 1857. Acesta a plecat de la o analogie cu botanica.
[modifică] Propoziţii şi teoreme
- Fie un graf neorientat G=(V,E), unde V e mulţimea vârfurilor, iar E cea a muchiilor sale. Următoarele afirmaţii sunt echivalente:
-
- G este arbore.
- G este un graf conex, minimal cu această proprietate (dacă se elimină o muchie oarecare, se obţine un graf neconex).
- G este un graf fără cicluri, maximal cu această proprietate (dacă se adaugă o muchie, se obţine un graf care are măcar un ciclu).
- Un arbore cu n ≥ 2 vârfuri conţine cel puţin două vârfuri terminale.
- Orice arbore cu n vârfuri are n-1 muchii.
[modifică] Noţiuni corelate
- Fie G un graf neorientat. Un graf parţial H al lui G, cu proprietatea că H este arbore, se numeşte arbore parţial al lui G.
- Un graf neorientat G conţine un arbore parţial dacă şi numai dacă G este conex.
- Un graf neorientat care nu conţine cicluri se numeşte pădure.
[modifică] Vezi şi
[modifică] Bibliografie
- Cornelia Ivaşc, Mona Prună, Luminiţa Condurache, Doina Logofătu-Hrinciuc, Informatică - C++, Ed. Petrion, 2002, ISBN 973-9470-33-5
