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

  1. 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.

  2. 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.

  3. De afstand tussen twee knopen u en v is de lengte van het kortste pad tussen knoop u en knoop v.

  4. Een samenhangende graaf is een graaf waar tussen elk tweetal knopen een pad bestaat.

  5. Een cycle is een pad waarvoor geldt e1 = en en n > 1

  6. Een boom is een samenhangende graaf zonder cycles.

  7. 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'.

  8. Zij v ∈ V, dan N(v) := {u ∈ V | uv ∈ E}, we noemen dit de verzameling buren van v.

  9. Zij v ∈ V, dan d(v) := #N(v).

  10. Δ(G):= max{d(v) | v ∈ V}.

  11. δ(G) := min{d(v) | v ∈ V}.

Definities specifiek voor artikelen

  1. De orde van een boom G(V,E) is het aantal elementen van V.

  2. De diameter van een graaf G is de lengte van het 'langste kortste pad' tussen twee knopen uit de graaf.

  3. De girth van een graaf is de lengte van de kortste cycle in een graaf.

  4. Een end/pendent vertex is een knoop met graad 1.

  5. Een leaf is een pendent vertex in een boom.

  6. Een end/pendent-edge is een kant uv ∈ E zodat u of v een end vertex is.

  7. 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.

  8. Een gewortelde boom is een boom met een uitverkoren knoop v, de wortel van de boom.

  9. Een spider is een gewortelde boom waarvoor geldt dat iedere knoop, ongelijk de wortel, graad 1 of graad 2 heeft.

  10. De diepte van een gewortelde graaf is de langste afstand van de wortel v naar een andere knoop.

  11. 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