Grafen les 2 Wandelingen/ paden/ cykel/spoor/circuit en oefeningen

• Wiskunde
• Secundair onderwijs

Grafen

Wandelingen en paden

even herhalen....

Hoeveel knopen
heeft deze graaf?

Hoeveel bogen
heeft deze graaf?

orde (n) van de graaf

grootte (m) van de graaf

Het aantal knopen =

Het aantal bogen =

Geef de grootte m
van deze graaf?

Duid de juiste stelling aan
In een graaf geldt:

De som van alle bogen is gelijk aan het dubbel van het aantal knopen

De som van alle knopen is gelijk aan het dubbel het aantal bogen.

De som van alle graden van alle knopen is gelijk aan het dubbel van het aantal bogen.

Noteer of de graaf samenhangend
is of niet. (Ja/Nee)
Verklaar.

Noteer of de graaf samenhangend
is of niet. (Ja/Nee)
Verklaar.

Noteer of de graaf samenhangend
is of niet. (Ja/Nee)
Verklaar.

Verbeter:

Speciale types van grafen

• Twee grafen zijn gelijk als ze dezelfde knopen hebben en tussen dezelfde knopen dezelfde bogen hebben.
• De som van alle graden van alle knopen is gelijk aan het dubbel van het aantal bogen.
• een reguliere graaf: graaf waarin alle knopen dezelfde graad hebben.
• een volledige graaf: elke knoop is verbonden met alle andere knopen van de graaf.
• multigraaf: een graaf waarbij bepaalde knopen door meer dan één boog met elkaar verbonden zijn <-> enkelvoudige graaf

• wandeling tussen twee knopen X en Y: opeenvolging van bogen die begint in X en eindigt in Y.
  
• - gesloten wandeling: wandeling die begint en eindigt in dezelfde knoop. <-> open wandeling
• pad: een wandeling waarbij elke knoop maximaal één keer doorlopen wordt. (behalve eventueel begin en eindpunt)
• - een cykel: een gesloten pad
• spoor: een wandeling waarbij elke boog maximaal één keer doorlopen wordt
• - circuit: een gesloten spoor
• samenhangende graaf: elke knoop van de graaf is via een pad bereikbaar vanuit elke andere knoop van de graaf

2.7 Oefeningen p 53 e.v.

• Eerst oefenen we de begrippen in:  Oef 1(a,b,c)

oefening 1 oplossing

oefening 4

oefening 4 oplossing

oefening 20

oefening 20 oplossing

Enkele concrete toepassingen

Oefening 6 

oefening 6 oplossing

Oefening 14

extra chat: Ella chatte met 3 personen.

Oefening 14 oplossing

extra vragen:

1-Wat zijn de buren van A

2- Wat is de graad van C

3-Is deze graaf samenhangend?

Oefening 14 oplossing

extra vragen:

1-Wat zijn de buren van A

B,F

2- Wat is de graad van C

4

3-Is deze graaf samenhangend?

ja

oefening 15

oefening 15 oplossing

Theoretische oefeningen

oefening 7

Oefening 7 oplossing

Theoretische oefeningen

oefening 8

Oefening 8 oplossing

Twee extra toepassingen

• De bakker
• Levensloop 

De bakker oplossing

De bakker oplossing

levensloop oplossing