Wiskunde:
hoofdstuk 14: grafen
● Een graaf G bestaat uit een eindige verzameling van knopen en een eindige
verzameling van bogen.
● De orde van de graaf is het aantal knopen in de graaf = n
● De grootte van de graaf is het aantal bogen van de graaf = m
● een knoop is een buur van een andere knoop als ze verbonden zijn door een boog =
deg(x)
● De hoogste graad die in G voorkomt, noteren we als Δ(G).
● De laagste graad die in G voorkomt, noteren we als δ(G).
Soorten grafen:
● Een planaire graaf is een graaf die in het platte vlak kan getekend worden zonder
dat de bogen elkaar kruisen.
● Een gewogen graaf is een graaf waarbij aan elke boog een
‘gewicht’ werd toegekend.
● Een multigraaf is een graaf waarbij twee knopen door meer
dan één boog met elkaar verbonden zijn.
,Wiskunde:
● Een graaf waarin alle knopen dezelfde graad hebben, is een
reguliere graaf.
● Een graaf heet volledig als elke knoop in de graaf verbonden
is met alle andere knopen in de graaf.
● Een wandeling tussen twee knopen x en y van een graaf is een
opeenvolging van bogen die beginnen in x en eindigen in Y.
● Gesloten wandeling ⇾ begint en eindigt in dezelfde knoop. (W2)
● Open wandeling ⇾ begint en eindigt niet in dezelfde knoop. (W1)
, Wiskunde:
Een graaf is samenhangend als er tussen elke twee knopen van een
graaf een wandeling bestaat. De gegeven graag G is samenhangend.
Hiernaast vind je een voorbeeld van een graaf die NIET samenhangend
of onsamenhangend is.
● Een pad tussen twee knopen X en Y is een wandeling waarbij
elke knoop hoogstens één keer voorkomt (behalve eventueel
begin- en eindpunt) ⇾ W1, W3, W4
●
●
Een gesloten pad wordt een cykel genoemd. ⇾ W4 ↗
Een spoor tussen twee knopen X en Y is een wandeling waarbij
elke boog hoogstens één keer voorkomt.⇾ W1, W2, W3, W4
zijn vier sporen.
● Een gesloten spoor wordt een circuit genoemd. ⇾ W2 en W4
zijn circuits.
Een eulerwandeling in een graaf G is een spoor dat elke boog van G
bevat.
Een eulertoer in een graaf G is een circuit dat elke boog van G bevat.
Een graaf die een eulertoer bevat noemen we een eulergraaf.
Een eulertoer in een graaf G is een circuit dat elke boog van G bevat.
hoofdstuk 14: grafen
● Een graaf G bestaat uit een eindige verzameling van knopen en een eindige
verzameling van bogen.
● De orde van de graaf is het aantal knopen in de graaf = n
● De grootte van de graaf is het aantal bogen van de graaf = m
● een knoop is een buur van een andere knoop als ze verbonden zijn door een boog =
deg(x)
● De hoogste graad die in G voorkomt, noteren we als Δ(G).
● De laagste graad die in G voorkomt, noteren we als δ(G).
Soorten grafen:
● Een planaire graaf is een graaf die in het platte vlak kan getekend worden zonder
dat de bogen elkaar kruisen.
● Een gewogen graaf is een graaf waarbij aan elke boog een
‘gewicht’ werd toegekend.
● Een multigraaf is een graaf waarbij twee knopen door meer
dan één boog met elkaar verbonden zijn.
,Wiskunde:
● Een graaf waarin alle knopen dezelfde graad hebben, is een
reguliere graaf.
● Een graaf heet volledig als elke knoop in de graaf verbonden
is met alle andere knopen in de graaf.
● Een wandeling tussen twee knopen x en y van een graaf is een
opeenvolging van bogen die beginnen in x en eindigen in Y.
● Gesloten wandeling ⇾ begint en eindigt in dezelfde knoop. (W2)
● Open wandeling ⇾ begint en eindigt niet in dezelfde knoop. (W1)
, Wiskunde:
Een graaf is samenhangend als er tussen elke twee knopen van een
graaf een wandeling bestaat. De gegeven graag G is samenhangend.
Hiernaast vind je een voorbeeld van een graaf die NIET samenhangend
of onsamenhangend is.
● Een pad tussen twee knopen X en Y is een wandeling waarbij
elke knoop hoogstens één keer voorkomt (behalve eventueel
begin- en eindpunt) ⇾ W1, W3, W4
●
●
Een gesloten pad wordt een cykel genoemd. ⇾ W4 ↗
Een spoor tussen twee knopen X en Y is een wandeling waarbij
elke boog hoogstens één keer voorkomt.⇾ W1, W2, W3, W4
zijn vier sporen.
● Een gesloten spoor wordt een circuit genoemd. ⇾ W2 en W4
zijn circuits.
Een eulerwandeling in een graaf G is een spoor dat elke boog van G
bevat.
Een eulertoer in een graaf G is een circuit dat elke boog van G bevat.
Een graaf die een eulertoer bevat noemen we een eulergraaf.
Een eulertoer in een graaf G is een circuit dat elke boog van G bevat.
