1755945 Josh Tukker
Grafentheorie
Hoofdstuk 1 – Inleiding en basisbegrippen
1.2 Basisbegrippen
• 𝑛 is het aantal punten, 𝑚 is het aantal lijnen.
• Een graaf is een diagram die bestaat uit punten die wel of niet verbonden worden door één of
meer lijnen.
§ Is de lijn voorzien van een richting? Dit is een gerichte graaf.
§ Is de lijn voorzien van een gewicht? Dit is een gewogen graaf.
• Twee verbonden punten zijn buren, twee verbonden lijnen heten buurlijnen.
§ Er is sprake van meervoudige lijnen als tussen twee punten meer dan één lijn loopt.
§ Een lus is een lijn van een punt naar zichzelf.
§ Een graaf zonder meervoudige lijnen en lussen is een enkelvoudige graaf.
§ Als van graaf 𝐺 enkele lijnen en/of punten worden weggelaten, dan ontstaat de deelgraaf
van 𝐺.
• De valentie van een punt geeft aan hoeveel lijnen er aan een punt vastzitten, waarbij een lus voor
twee telt.
§ Bij enkelvoudige grafen wordt ook het begrip lijnvalentie gebruikt. Dit geeft het aantal andere
lijnen aan die vastzitten aan die lijn.
§ Een geïsoleerd punt is een punt met valentie 0.
§ De valentie-rij is de niet-dalende rij van valenties van de punten van de graaf.
§ Een graaf 𝐺 is regelmatig van de orde 𝒌 als ieder punt van 𝐺 valentie 𝑘 heeft.
• Handenschud-lemma:
§ In elke graaf is de valentiesom gelijk aan 2𝑚.
• Een ongelabelde graaf is een graaf waarbij de punten geen naam hebben.
§ Als er voor de tekening van twee ongelabelde grafen een naamgeving te verzinnen is zo dat ze
dezelfde (gelabelde) graaf voorstellen, dan zijn beide ongelabelde grafen isomorf.
- Twee ongelabelde grafen 𝐺 en 𝐻 zijn isomorf als het mogelijk is de punten van 𝐺 en 𝐻 zo te
labelen dat gelijk gelabelde punten van 𝐺 en 𝐻 gelijke buren hebben.
• Een pad in een graaf is een rij opeenvolgende verschillende lijnen.
§ Een pad wordt genoteerd als een rij opeenvolgende lijnen.
§ Paden worden aangegeven met Griekse letters (α, β, γ, etc.).
§ Het eerste punt heet het beginpunt en het laatste punt heet het eindpunt.
- Als het beginpunt en eindpunt van een pad α samenvallen, heet het pad α een circuit.
o Een circuit van drie lijnen noem je een driehoek, een circuit van vier lijnen noem je een
vierhoek, etc.
• Een graaf heet een samenhangende graaf als er tussen elk tweetal verschillende punten van de
graaf een pad bestaat.
§ Een niet-samenhangende graaf bestaat uit een aantal componenten, die ieder afzonderlijk wel
samenhangend zijn, maar onderling niet verbonden zijn.
1.3 Verbindingsmatrices
• Een graaf kan numeriek worden weergegeven door middel van een verbindingsmatrix.
§ In een verbindingsmatrix geeft het getal 1 aan dat punten buren zijn.
§ Het aantal tweestap-, driestap-, vierstap-, etc-routes zijn te berekenen met behulp van de
matrixvermenigvuldiging.
1/9
Grafentheorie
Hoofdstuk 1 – Inleiding en basisbegrippen
1.2 Basisbegrippen
• 𝑛 is het aantal punten, 𝑚 is het aantal lijnen.
• Een graaf is een diagram die bestaat uit punten die wel of niet verbonden worden door één of
meer lijnen.
§ Is de lijn voorzien van een richting? Dit is een gerichte graaf.
§ Is de lijn voorzien van een gewicht? Dit is een gewogen graaf.
• Twee verbonden punten zijn buren, twee verbonden lijnen heten buurlijnen.
§ Er is sprake van meervoudige lijnen als tussen twee punten meer dan één lijn loopt.
§ Een lus is een lijn van een punt naar zichzelf.
§ Een graaf zonder meervoudige lijnen en lussen is een enkelvoudige graaf.
§ Als van graaf 𝐺 enkele lijnen en/of punten worden weggelaten, dan ontstaat de deelgraaf
van 𝐺.
• De valentie van een punt geeft aan hoeveel lijnen er aan een punt vastzitten, waarbij een lus voor
twee telt.
§ Bij enkelvoudige grafen wordt ook het begrip lijnvalentie gebruikt. Dit geeft het aantal andere
lijnen aan die vastzitten aan die lijn.
§ Een geïsoleerd punt is een punt met valentie 0.
§ De valentie-rij is de niet-dalende rij van valenties van de punten van de graaf.
§ Een graaf 𝐺 is regelmatig van de orde 𝒌 als ieder punt van 𝐺 valentie 𝑘 heeft.
• Handenschud-lemma:
§ In elke graaf is de valentiesom gelijk aan 2𝑚.
• Een ongelabelde graaf is een graaf waarbij de punten geen naam hebben.
§ Als er voor de tekening van twee ongelabelde grafen een naamgeving te verzinnen is zo dat ze
dezelfde (gelabelde) graaf voorstellen, dan zijn beide ongelabelde grafen isomorf.
- Twee ongelabelde grafen 𝐺 en 𝐻 zijn isomorf als het mogelijk is de punten van 𝐺 en 𝐻 zo te
labelen dat gelijk gelabelde punten van 𝐺 en 𝐻 gelijke buren hebben.
• Een pad in een graaf is een rij opeenvolgende verschillende lijnen.
§ Een pad wordt genoteerd als een rij opeenvolgende lijnen.
§ Paden worden aangegeven met Griekse letters (α, β, γ, etc.).
§ Het eerste punt heet het beginpunt en het laatste punt heet het eindpunt.
- Als het beginpunt en eindpunt van een pad α samenvallen, heet het pad α een circuit.
o Een circuit van drie lijnen noem je een driehoek, een circuit van vier lijnen noem je een
vierhoek, etc.
• Een graaf heet een samenhangende graaf als er tussen elk tweetal verschillende punten van de
graaf een pad bestaat.
§ Een niet-samenhangende graaf bestaat uit een aantal componenten, die ieder afzonderlijk wel
samenhangend zijn, maar onderling niet verbonden zijn.
1.3 Verbindingsmatrices
• Een graaf kan numeriek worden weergegeven door middel van een verbindingsmatrix.
§ In een verbindingsmatrix geeft het getal 1 aan dat punten buren zijn.
§ Het aantal tweestap-, driestap-, vierstap-, etc-routes zijn te berekenen met behulp van de
matrixvermenigvuldiging.
1/9
