In grafiekteorie is 'n boom 'n ongerigte grafiek waarin enige twee hoekpunte met presies een pad verbind word, of ekwivalent 'n gekoppelde asikliese ongerigte grafiek. … 'n Poliwoud (of gerigte woud of georiënteerde woud) is 'n gerigte asikliese grafiek waarvan die onderliggende ongerigte grafiek 'n woud is.
Wat is gerigte en ongerigte bome?
'n Ongerigte grafiek sonder siklusse is 'n woud en as dit verbind is, word dit 'n boom genoem. 'n Gerigte grafiek is 'n woud (of boom) as wanneer alle rande na ongerigte rande omgeskakel word, dit ongerigte woud (of boom) is. 'n Gewortelde boom is 'n boom met een hoekpunt wat as die wortel aangedui word.
Waarom is bome ongerig?
Stelling: 'n Ongerigte grafiek is 'n boom as daar presies een eenvoudige pad tussen elke paar hoekpunte isBewys: As ons 'n grafiek T het wat 'n boom is, dan moet dit met geen siklusse verbind word nie. Aangesien T verbind is, moet daar ten minste een eenvoudige pad tussen elke paar hoekpunte wees.
Wat word bedoel met gerigte boom?
'n Gerigte boom is 'n asiklies-gerigte grafiek Dit het een knoop met graad 1, terwyl alle ander nodusse graad 1 het soos in fig. getoon: Die knoop wat buitegraad 0 het is 'n eksterne nodus of 'n terminale nodus of 'n blaar genoem. Die nodusse wat uitgraad groter as of gelyk aan een het, word interne nodus genoem.
Hoe weet jy of 'n ongerigte grafiek 'n boom is?
In die geval van ongerigte grafieke, voer ons drie stappe uit:
- Voer 'n DFS-kontrole vanaf enige nodus uit om seker te maak dat elke nodus presies een ouer het. Indien nie, gee terug.
- Kyk dat alle nodusse besoek is. As die DFS-tjek nie alle nodusse kon besoek nie, gee dan terug.
- Anders is die grafiek 'n boom.
