Arbore (teoria grafurilor)
graf aciclic, conex, neorientat
Î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 și cei mai frecvent utilizați în practică.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Tree_graph.svg/220px-Tree_graph.svg.png)
Termenul de „arbore” din teoria grafurilor a fost folosit pentru prima dată de Cayley în anul 1857. El a plecat de la o analogie cu noțiunea de „arbore” din botanică.
Istorie
Arborii au fost studiați intensiv de numeroși matematicieni și fizicieni, precum matematicianul britanic Arthur Cayley, pe care l-au interesat aplicațiile lor în chimia organică, de ex. grafurile chimice, sau fizicianul german G. R. Kirchhoff, care a studiat această categorie pornind de la studiul circuitelor electrice.
Propoziții și teoreme
- Fie un arbore G=(V,E), unde V e mulțimea nodurilor, iar E cea a muchiilor. Următoarele afirmații sunt echivalente:
- G este un graf conex minimal („minimal” se numește proprietatea unui arbore, că dacă i se elimină orice muchie, se obține un graf neconex).
- G este un graf fără cicluri maximal („maximal” se numește proprietatea unui arbore, că dacă i se adaugă orice muchie, se obține un graf care are măcar un ciclu, și deci nu e arbore).
- 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.
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 și nu este conex se numește „pădure”.
Bibliografie
- Cornelia Ivașc, Mona Prună, Luminița Condurache, Doina Logofătu-Hrinciuc, Informatică - C++, Ed. Petrion, 2002, ISBN 973-9470-33-5
Vezi și
🔥 Top keywords: Pagina principalăNicușor StanciuCampionatul European de Fotbal 2024Echipa națională de fotbal a RomânieiCampionatul European de FotbalRadu DrăgușinEduard IordănescuLista domnilor Țării RomâneștiSpecial:CăutareFlorin NițăDenis DrăgușAllianz ArenaCampionatul European de Fotbal 2020Campionatul European de Fotbal 2000Răzvan MarinDeșteaptă-te, române!Anghel IordănescuRomâniaAlegeri prezidențiale în România, 2024Damac FCIanis HagiBogdan RacovițanGheorghe HagiEchipa națională de fotbal a UcraineiCampionatul Mondial de FotbalAndrei BurcăCampionatul Mondial de Fotbal 2026Campionatul European de Fotbal 2028Kylian MbappéAndrei RațiuListă de antrenori ai echipei naționale de fotbal a RomânieiRomânia la Campionatul Mondial de FotbalCampionatul Mondial de Fotbal 1994Listă de domni și domnitori ai Țărilor RomâneCiprian MaricaMarius MarinLista finalelor Campionatului European de FotbalZodiacMîhailo Mudrîk