Google Classroom
GeoGebraGeoGebra Classroom

begrip graaf

voorstelling

In de applet kan je de grijze lijnstukken en hun randpunten verslepen en zo een aantal punten verbinden. Klik op de lijnstukken om ze blauw te kleuren en de verbinding te activeren. Zo krijg je de voorstelling van een graaf.

begrippen

Formeler wordt een graaf bepaald door
  • een verzameling V van punten
  • een verzameling E van paren {u, v} uit V die verbonden zijn door een lijnstuk.
Je kunt dus een graaf G definiëren als een paar (V, E) waarbij V een eindige verzameling is van punten en E een verzameling van paren uit V.
  • De elementen uit V noemen we punten of knopen (V komt van het Engelse Vertices)
  • De elementen uit E noemen we lijnen of kanten of bogen (E komt van het Engelse Edges).
  • De paren bestaan steeds uit twee verschillende elementen, maar in een ruimere definitie zijn ook lussen als {u, u} mogelijk.  
  • Wanneer je op een voorstelling ziet dan twee knopen u en v verbonden zijn door een boog, noemen we {u, v} een paar en v een buur van u.
Opmerking: In de praktijk vind je uiteenlopende notaties voor bogen en wordt de schrijfwijze met accolades zelden gebruikt. Eerder lees je uv (of UV wanneer je de knopen noteert met hoofdletters).

Voorbeeld

Voorbeeld
  • De graaf bij bovenstaande afbeelding kan je beschrijven als ({A, B, C, D}, {(A, B), (A, C), (A, D), (B, D), (C, D)}).
  • Hij heeft 4 knopen en 5 bogen.
  • De buren van B zijn A en D.

knopen activeren door ze te kleuren

  • Definieer een booleaanse variabele toonAB= false.
  • Bepaal twee punten A en B en creëer een lijnstuk dat beide punten verbindt.
  • Rechtsklik op het lijnstuk, selecteer Eigenschappen en open de tab Scripting
  • Typ in de tab Bij klikken het commando SetValue(toonAB,!toonAB).
Opmerking: In scripting staat een uitroepteken voor ‘niet’ of ‘tegengestelde waarde’. Bij klikken op het lijnstuk zal de waarde dus telkens wisselen tussen true en false.
Image
Selecteer nu de tab Geavanceerd en definieer de dynamische kleuren: toonAB=true: Rood en Groen krijgen als waarde 0 en Blauw 1. Het lijnstuk kleurt dus blauw. toon AB=false: de drie kleuren krijgen als waarde 0.7. Het lijnstuk kleurt lichtgrijs. Opmerking: De combinatie 0-0-0 geeft zwart, 1-1-1 geeft wit. 0.8 kleurt dus iets lichter, 0.6 donkerder. Bij klikken zal de kleur van het lijnstuk wisselen tussen lichtgrijs en blauw.
Image