deelgrafen van een graaf
Een deelgraaf H van een graaf G is een graaf waarvoor geldt:
- de puntenverzameling van H is een deelverzameling van de puntenverzameling van G.
- de lijnenverzameling van H is een deelverzameling van de lijnenverzameling van G (let op dat daarbij wel de eindpunten van de lijnen uit H ook punten van H moeten zijn; anders is H geen graaf.)
In figuur 25 zie je links een graaf G en rechts een deelgraaf H van G.
G
H
figuur 25: Een graaf G en een deelgraaf H van G.
figuur 26: drie opspannende deelgrafen van de graaf G uit figuur 25
opdracht 17
Bekijk de graaf G uit figuur 27.
figuur 27: De graaf G uit opdracht 1
a. Geef van de grafen uit figuur 28 aan of ze wel of niet een deelgraaf van G zijn.
A
B
C
b. Welke van de drie grafen is een opspannende deelgraaf van G?