INLEIDING GRAFENTHEORIE HOOFDSTUK 1 EN 2
Gemaakt door: L. Mulder
Gebruik de lege ruimtes om een voorbeeld te schetsen
Definities
1. Verzameling V van punten
Graaf: G={V , E } 2. Verzameling E van paren {u , v } uit V
waartussen een lijn loopt
Punten Elementen uit V
Lijnen Elementen uit E
Als twee punten verbonden zijn d.m.v. een lijn uit
Buur
E
Aantal buren van
Graad een punt in een
graaf
Alle punten
Regulier hebben dezelfde
graad
k -regulier Alle punten hebben graad k (kijk hierboven)
Elk paar punten in
Volledig ( K n ) V is verbonden
Als V in twee niet-lege klassen kan worden
Volledig bipartiet gesplitst zodanig dat
E={{ V 1 , V 2 }|v 1 ∈ V 1 , v 2 ∈V 2 }
Als ¿ V 1∨¿ m en
¿ V 2∨¿ n
Volledig bipartiete graaf Km,n
De graaf
G=(V , F )
waarbij F uit alle
Complement
paren punten
bestaat die niet
tot E behoren
Lijngraaf: L(G) De graaf waarvan
de
puntenverzamelin
g gelijk is aan E ,
waarbij 2
elementen van E
, verbonden zijn als
en alleen als ze
een punt van G
gemeen hebben.
Een rij punten
(v 0 , v1 , ... , v k )
Wandeling z.d.d. vi −1 en vi
verbonden, voor
elke i=1 , ..., k
Lengte Het getal k , in de wandeling ( v 0 , v1 , ... , v k )
Als v 0 , v1 , ..., v k in
een wandeling
Pad
verschillende
punten is
Als in een graaf tussen elk tweetal punten een pad
Samenhangend
loopt
Een graaf
G ’={V ’ , E ’ } is
een deelgraaf van
Deelgraaf: G ’={V ’ , E ’ }
G={V , E } als
V ’ ⊆V en
E’⊆ E
Een maximale niet-lege samenhangende deelgraaf
G ’={V ’ , E ’ }. Oftewel G ’ is niet een deelgraaf
Component van een andere samenhangende deelgraaf van G
G is samenhangend als en alleen als G ten
hoogste één component heeft
Als er voor een
wandeling
Gesloten wandeling
(v 0 , v1 , ... , v k )
geldt: v 0=v k
Een gesloten
wandeling
(v 0 , v1 , ... , v k )
Circuit waarbij k ≥ 3 en
v1 , ... , v k
verschillende
punten zijn
Een circuit van
Driehoek
lengte 3
Als er in de graaf
Bos G geen circuits
zitten
Gemaakt door: L. Mulder
Gebruik de lege ruimtes om een voorbeeld te schetsen
Definities
1. Verzameling V van punten
Graaf: G={V , E } 2. Verzameling E van paren {u , v } uit V
waartussen een lijn loopt
Punten Elementen uit V
Lijnen Elementen uit E
Als twee punten verbonden zijn d.m.v. een lijn uit
Buur
E
Aantal buren van
Graad een punt in een
graaf
Alle punten
Regulier hebben dezelfde
graad
k -regulier Alle punten hebben graad k (kijk hierboven)
Elk paar punten in
Volledig ( K n ) V is verbonden
Als V in twee niet-lege klassen kan worden
Volledig bipartiet gesplitst zodanig dat
E={{ V 1 , V 2 }|v 1 ∈ V 1 , v 2 ∈V 2 }
Als ¿ V 1∨¿ m en
¿ V 2∨¿ n
Volledig bipartiete graaf Km,n
De graaf
G=(V , F )
waarbij F uit alle
Complement
paren punten
bestaat die niet
tot E behoren
Lijngraaf: L(G) De graaf waarvan
de
puntenverzamelin
g gelijk is aan E ,
waarbij 2
elementen van E
, verbonden zijn als
en alleen als ze
een punt van G
gemeen hebben.
Een rij punten
(v 0 , v1 , ... , v k )
Wandeling z.d.d. vi −1 en vi
verbonden, voor
elke i=1 , ..., k
Lengte Het getal k , in de wandeling ( v 0 , v1 , ... , v k )
Als v 0 , v1 , ..., v k in
een wandeling
Pad
verschillende
punten is
Als in een graaf tussen elk tweetal punten een pad
Samenhangend
loopt
Een graaf
G ’={V ’ , E ’ } is
een deelgraaf van
Deelgraaf: G ’={V ’ , E ’ }
G={V , E } als
V ’ ⊆V en
E’⊆ E
Een maximale niet-lege samenhangende deelgraaf
G ’={V ’ , E ’ }. Oftewel G ’ is niet een deelgraaf
Component van een andere samenhangende deelgraaf van G
G is samenhangend als en alleen als G ten
hoogste één component heeft
Als er voor een
wandeling
Gesloten wandeling
(v 0 , v1 , ... , v k )
geldt: v 0=v k
Een gesloten
wandeling
(v 0 , v1 , ... , v k )
Circuit waarbij k ≥ 3 en
v1 , ... , v k
verschillende
punten zijn
Een circuit van
Driehoek
lengte 3
Als er in de graaf
Bos G geen circuits
zitten
