wiskunde - H3 Grafen (theorie/definities) Flashcards
definitie graaf
Een graaf is een grafische voorstelling die bestaat uit punten en verbindingslijnen tussen die punten.
Wat is een knoop in een graaf?
Een punt is een knoop van een graaf.
Wat is een boog in een graaf?
Een verbindingslijn is een boog van een graaf.
Wanneer zijn 2 verschillende knopen buren?
Als ze met elkaar verbonden zijn door een boog.
Wat zijn buren?
2 verschillende knopen die met elkaar verbonden zijn door een boog.
definitie lus
Een lus is een boog van een knoop naar zichzelf.
definitie wandeling
Een wandeling in een graaf is een rij van aaneensluitende bogen.
definitie pad
Een pad in een graaf is een wandeling waarbij je nooit meer dan 1 keer dezelfde knoop passeert.
Enkel de beginknoop mag dezelfde zijn als de eindknoop.
definitie samenhangende graaf
Een samenhangende graaf is een graaf waarbij tussen elke 2 knopen een wandeling bestaat.
Wanneer is een graaf niet samenhangend?
Als ze uit meer dan 1 deel bestaat.
definitie graad van een knoop
De graad van een knoop van een graaf is het aantal bogen dat aan de knoop vastzit.
Daarbij telt de lus telkens voor 2.
Aan wat is de som van alle graden gelijk in een graaf?
Aan het dubbel van het aantal bogen.
s = 2v
(v=verbindingen)
definitie enkelvoudige graaf
Een enkelvoudige graaf is een graaf zonder lussen en met hoogstens 1 boog tussen elke 2 knopen.
In een enkelvoudige graaf is de graad van een knoop gelijk aan het aantal buren van die knoop.
definitie cykel
Een cykel is een gesloten pad: de begin- en eindknoop zijn dezelfde.
definitie volledige graaf
Enkelvoudige grafen waarin alle knopen met elkaar verbonden worden door een boog.
Wat is een bewijs uit het ongerijmde?
Dan bekijk je of dat het tegenovergestelde vals is.
Wat is een component
Een deel van een niet-samenhangende graaf.
Als de niet-samenhangende graaf uit 2 delen bestaat, heeft die 2 componenten.
Wat betekent een graaf kleuren?
Betekent dat je aan elke knoop een kleur toekent worst twee buren niet dezelfde kleur hebben.
Wanneer is een graaf alleen k-kleurbaar?
Als en slechts als je met k kleuren de graaf kunt kleuren.
Wat is het chromatisch getal van een graaf?
Het kleinste aantal kleuren dat nodig is om de graaf te kleuren.
Wat is de bovengrens van het chromatisch getal?
Als d de hoogste graad is van een knoop van een graaf, dan is het chromatisch getal van die graag niet groter dan d + 1
-> nog geen algoritme om te berekenen.
Wat is de ondergrens van een chromatisch getal?
Zijn in een graag een aantal knopen allemaal onderling verbonden, dan moeten die knopen een verschillende kleur krijgen.
Dat aantal knopen is dan een ondergrens voor het chromatisch getal van de graaf.
Wat is een vlakke graaf?
Een graaf die zodanig getekend kan worden dat de bogen elkaar niet snijden.
Wat is een spoor?
Een wandeling waarbij je meer dan 1 keer dezelfde boog passeert.
Wat is een circuit?
Een gesloten spoor: de begin en eind knoop wijn hetzelfde.
Wat is een eulerspoor?
Een spoor dat alle bogen van de graaf passeert.
Wat is een eulercircuit?
Een gesloten eulerspoor.
Een gesloten spoor dat alle bogen van de graaf passeert.
Wat is een eulergraaf?
Een graaf met een eulercircuit.
= een graaf met de naam n gesloten spoor dat alle bogen van de graaf passeert.
Wanneer is een samenhangende graaf alleen een eulergraaf?
Als en slechts als de graad van elke knoop even is.
