Articles

Boom (grafiektheorie)

by admin

TreeEdit

een boom is een niet-gerichte grafiek G die aan een van de volgende gelijkwaardige voorwaarden voldoet:

  • G is verbonden en acyclisch (bevat geen cycli).
  • G is acyclisch, en een eenvoudige cyclus wordt gevormd als een rand wordt toegevoegd aan G.
  • G is verbonden, maar zou worden losgekoppeld als een enkele rand wordt verwijderd uit G.
  • G is verbonden en de 3-vertex volledige grafiek K3 is geen minor van G.
  • elke twee hoekpunten in G kunnen worden verbonden door een uniek eenvoudig pad.

als G een eindig aantal hoekpunten heeft, bijvoorbeeld n, dan zijn de bovenstaande statements ook gelijk aan een van de volgende voorwaarden:

  • G is verbonden en heeft n − 1 randen.
  • G is verbonden, en elke subgraph van G bevat ten minste één vertex met nul of één invallende randen. (Dat wil zeggen, G is verbonden en 1-gedegenereerd.)
  • G heeft geen eenvoudige cycli en heeft n-1 randen.

zoals elders in de grafiektheorie wordt de orde-nulgrafiek (grafiek zonder hoekpunten) over het algemeen niet beschouwd als een boom: hoewel het vacuüm is verbonden als een grafiek (elke twee hoekpunten kunnen worden verbonden door een pad), is het niet 0-verbonden (of zelfs (-1)-verbonden) in de algebraïsche topologie, in tegenstelling tot niet-lege bomen, en schendt het de relatie “één meer vertex dan randen”. Het kan echter worden beschouwd als een bos dat uit nulbomen bestaat.

een intern vertex (of inner vertex of branch vertex) is een vertex van graad ten minste 2. Een externe vertex (of buitenste vertex, eindvertex of blad) is een vertex van graad 1.

een onherleidbare boom (of reeksreduceerde boom) is een boom waarin zich geen top van graad 2 bevindt (opgesomd in rij A000014 in de OEIS).

ForestEdit

een forest is een niet-gerichte grafiek waarin twee hoekpunten zijn verbonden door ten hoogste één pad. Op equivalente wijze is een bos een niet-gerichte acyclische grafiek, waarvan alle aangesloten componenten bomen zijn; met andere woorden, de grafiek bestaat uit een disjuncte Vereniging van bomen. Als speciale gevallen zijn de orde-nul grafiek (een bos bestaande uit nul bomen), een enkele boom, en een randloze grafiek, voorbeelden van bossen.Aangezien voor elke boom V-E = 1, kunnen we gemakkelijk het aantal bomen tellen dat zich in een bos bevindt door het verschil tussen de totale hoekpunten en de totale randen af te trekken. TV-TE = Aantal bomen in een bos.

PolytreeEdit

Main article: Polytree

een polytree (of directed tree of oriented tree of single connected network) is een gerichte acyclische grafiek (DAG) waarvan de onderliggende niet-gerichte grafiek een boom is. Met andere woorden, als we de gerichte randen vervangen door niet-gerichte randen, krijgen we een niet-gerichte grafiek die zowel verbonden als acyclisch is.

sommige auteurs beperken de zin “directed tree” tot het geval dat de randen allemaal naar een bepaald punt zijn gericht, of allemaal weg van een bepaald punt (zie arborescence).

PolyforestEdit

een polyforest (of gericht bos of georiënteerd bos) is een gerichte acyclische grafiek waarvan de onderliggende niet-gerichte grafiek een forest is. Met andere woorden, als we de gerichte randen vervangen door niet-gerichte randen, krijgen we een niet-gerichte grafiek die acyclisch is.

sommige auteurs beperken de zin “directed forest” tot het geval dat de randen van elk verbonden onderdeel allemaal naar een bepaald punt zijn gericht, of allemaal weg van een bepaald punt (zie vertakkingen).

Rooted treeEdit

een rooted tree is een tree waarin een vertex de root is aangewezen. De randen van een gewortelde boom kunnen een natuurlijke oriëntatie krijgen, weg van of naar de wortel, in welk geval de structuur een gerichte gewortelde boom wordt. Wanneer een gerichte wortelboom een oriëntatie heeft weg van de wortel, wordt het een arborescentie of out-tree genoemd; wanneer het een oriëntatie heeft naar de wortel, wordt het een anti-arborescentie of in-tree genoemd. De boomvolgorde is de gedeeltelijke ordening op de hoekpunten van een boom met u < V dan en alleen als het unieke pad van de wortel naar v door u gaat. een gewortelde boom T die een subgrafie is van een grafiek G is een normale boom als de uiteinden van elk T-pad in G vergelijkbaar zijn in deze boomvolgorde (Diestel 2005, p. 15). Gewortelde bomen, vaak met extra structuur zoals het ordenen van de buren op elk hoekpunt, zijn een belangrijke datastructuur in de informatica; zie boomgegevensstructuur.

in een context waarin bomen verondersteld worden een root te hebben, wordt een boom zonder enige aangewezen root een vrije boom genoemd.

een gelabelde boom is een boom waarin elk hoekpunt een uniek label krijgt. De hoekpunten van een geëtiketteerde boom op n hoekpunten worden meestal gegeven de labels 1, 2,…, n. een recursieve boom is een gelabelde wortelboom waarbij de vertex-labels de boomvolgorde respecteren (d.w.z., als u < V voor twee hoekpunten u en v, dan is het label van u kleiner dan het label van v).

in een gewortelde boom is de ouder van een vertex v het vertex verbonden met v op het pad naar de root; elk vertex heeft een unieke ouder behalve de root die geen ouder heeft. Een kind van een Top v is een top waarvan v de ouder is. Een ascendant van een Top v is een top die ofwel de ouder van v is, ofwel (recursief) de ascendant van de ouder van V is. Een afstammeling van een vertex v is elk vertex dat ofwel het kind van v is ofwel (recursief) de afstammeling is van een van de kinderen van v. een broer of zus van een vertex v is elk ander vertex op de boom die dezelfde ouder heeft als v. een blad is een vertex zonder kinderen. Een intern vertex is een vertex dat geen blad is.

de hoogte van een vertex in een gewortelde boom is de lengte van het langste pad naar een blad vanaf dat vertex. De hoogte van de boom is de hoogte van de wortel. De diepte van een vertex is de lengte van het pad naar zijn wortel (wortelpad). Dit is vaak nodig bij de manipulatie van de verschillende zelfbalancerende bomen, AVL bomen in het bijzonder. De wortel heeft diepte nul, bladeren hebben hoogte nul, en een boom met slechts een enkele top (dus zowel een wortel en blad) heeft diepte en hoogte nul. Conventioneel, een lege boom (een boom zonder hoekpunten, als dat toegestaan is) heeft diepte en hoogte -1.

een k-ary boom is een gewortelde boom waarin elk vertex maximaal k-kinderen heeft. 2-Arige bomen worden vaak binaire bomen genoemd, terwijl 3-Arige bomen soms ternaire bomen worden genoemd.

Ordered treeEdit

een geordende boom (of plataan) is een gewortelde boom waarin een volgorde is opgegeven voor de kinderen van elk hoekpunt. Dit wordt een “plataan” genoemd omdat een volgorde van de kinderen gelijk is aan een inbedding van de boom in het vlak, met de wortel aan de bovenkant en de kinderen van elk hoekpunt lager dan dat hoekpunt. Gegeven een inbedding van een gewortelde boom in het vlak, als men fixeert een richting van kinderen, laten we zeggen van links naar rechts, dan een inbedding geeft een volgorde van de kinderen. Omgekeerd, gegeven een geordende boom, en conventioneel tekenen van de wortel aan de bovenkant, dan kan het kind hoekpunten in een geordende boom worden getrokken van links naar rechts, wat resulteert in een in wezen unieke vlakke inbedding.