Samenvatting/aantekeningen cursus Grafenthreorie

SAMENVATTING
GRAFENTHEORIE




Baltuttis,luke L.

Modelleren, kenmerken Grafen, Algoritmes en heuristieken, bewijzen en
redeneren

, Week 1
De student kent de basisbegrippen

Definities en afspraken
Een graaf 𝐺 is een paar (𝑉, 𝐸), waarbij de verzameling 𝑉 de verzameling punten (of knopen) weergeeft
en de verzameling 𝐸 de verzameling lijnen (of kanten) tussen de punten in 𝑉. Meestal wordt de graaf als
diagram weergegeven. De naam (label) van een punt geven we aan met een hoofdletter, de naam van
een lijn met een kleine letter (of met de twee hoofdletters van de eindpunten van de lijn)

- 𝑛 ≔ 𝑉 , dus het aantal punten.
- 𝑚 ≔ 𝐸 , dus het aantal lijnen.
- ValenBe (of graad) van een punt: het aantal lijnen dat aan een punt vast zit.
- ValenBerij: niet-dalende rij van valenBes van de punten van de graaf.
- Een graaf heet regelmaBg van orde 𝑘 als ieder punt valenBe 𝑘 heeE.
- Een wandeling (ook wel weg) in een graaf is een rij opeenvolgende lijnen.
- Een pad in een graaf is een rij opeenvolgende verschillende lijnen.
- Het eerste punt van een wandeling of pad heet beginpunt en het laatste heet eindpunt.
- Als begin- en eindpunt van een wandeling samenvallen, spreken we van een rondwandeling.
- Als begin- en eindpunt van een pad samenvallen, spreken we van een circuit.
- Een circuit van drie lijnen heet een driehoek, van vier lijnen een vierhoek, etc.
- Een graaf heet samenhangend als er tussen elk tweetal punten een pad bestaat.
- Alternatieve definitie van samenhangend: er zijn geen geïsoleerde punten.
- Een niet-samenhangende graaf valt uiteen in een aantal componenten, die ieder afzonderlijk
samenhangend zijn, maar onderling dus niet verbonden.
- Een lijn die bij weglating het aantal componenten vergroot heet een brug.

Voorbeeld
- 𝑉 = {A, B, C, D, E}
- 𝐸 = {AB, AC, BD}
- Hier noemen we punt 𝐸 eengeïsoleerd punt

Termen
- Twee verbonden punten heten buren
- Een lus is een lijn van een punt naar zichzelf
- Tussen een tweetal punten mogen meerdere lijnen lopen,
deze lijnen noemen we dan meervoudige lijnen
- Een graaf zonder meervoudige lijnen en lussen heet een simpele graaf (soms ook enkelvoudige
graaf)
- Als lijnen voorzien zijn van een richBng, spreken we van een gerichte graaf
- Als de lijnen voorzien zijn van een getal, spreken we van een gewogen graaf
- Als we van een graaf enkele lijnen en/of punten weglaten, spreken we van een deelgraaf