Definities
Op deze pagina vind je enkele definities van begrippen die in veel van de artikelen voorkomen, maar ook enkele algemene definities uit de grafentheorie.
Algemene definities
- Een graaf G = (V,E) bestaat uit een verzameling knopen V/ Een deel van deze knopen is met elkaar verbonden door kanten. Deze kanten zitten in de verzameling E.
- Een pad van knoop u naar een knoop v is een rij knopen u = e1, e2, ..., en = v zodanig dat eiei+1 ∈ E. De lengte van een pad is het aantal kanten dat dit pad bevat.
- De afstand tussen twee knopen u en v is de lengte van het kortste pad tussen knoop u en knoop v.
- Een samenhangende graaf is een graaf waar tussen elk tweetal knopen een pad bestaat.
- Een cycle is een pad waarvoor geldt e1 = en en n > 1
- Een boom is een samenhangende graaf zonder cycles.
- Een inbedding van G' = (V',E') in G = (V,E) is een injectieve afbeelding i:V'-> V zodanig dat i(u')i(v') ∈ E ⇔ u'v' ∈ E'.
- Zij v ∈ V, dan N(v) := {u ∈ V | uv ∈ E}, we noemen dit de verzameling buren van v.
- Zij v ∈ V, dan d(v) := #N(v).
- Δ(G):= max{d(v) | v ∈ V}.
- δ(G) := min{d(v) | v ∈ V}.
Definities specifiek voor artikelen
- De orde van een boom G(V,E) is het aantal elementen van V.
- De diameter van een graaf G is de lengte van het 'langste kortste pad' tussen twee knopen uit de graaf.
- De girth van een graaf is de lengte van de kortste cycle in een graaf.
- Een end/pendent vertex is een knoop met graad 1.
- Een leaf is een pendent vertex in een boom.
- Een end/pendent-edge is een kant uv ∈ E zodat u of v een end vertex is.
- Een penultimate vertex is een knoop in een graaf G die minstens 1 end-neighbor heeft en exact 1 neighbor die geen end-vertex is.
- Een gewortelde boom is een boom met een uitverkoren knoop v, de wortel van de boom.
- Een spider is een gewortelde boom waarvoor geldt dat iedere knoop, ongelijk de wortel, graad 1 of graad 2 heeft.
- De diepte van een gewortelde graaf is de langste afstand van de wortel v naar een andere knoop.
- De ξ(G):= min{d(u) + d(v) - 2 : uv ∈ E(G)}.
© 2014 Mark Coumans
Template design by Andreas Viklund / Best hosted at www.svenskadomaner.se