wiskunde - H3 Grafen (theorie/definities)

Question 1

definitie graaf

Answer 1

Een graaf is een grafische voorstelling die bestaat uit punten en verbindingslijnen tussen die punten.

Question 2

Wat is een knoop in een graaf?

Answer 2

Een punt is een knoop van een graaf.

Question 3

Wat is een boog in een graaf?

Answer 3

Een verbindingslijn is een boog van een graaf.

Question 4

Wanneer zijn 2 verschillende knopen buren?

Answer 4

Als ze met elkaar verbonden zijn door een boog.

Question 5

Wat zijn buren?

Answer 5

2 verschillende knopen die met elkaar verbonden zijn door een boog.

Question 6

definitie lus

Answer 6

Een lus is een boog van een knoop naar zichzelf.

Question 7

definitie wandeling

Answer 7

Een wandeling in een graaf is een rij van aaneensluitende bogen.

Question 8

definitie pad

Answer 8

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.

Question 9

definitie samenhangende graaf

Answer 9

Een samenhangende graaf is een graaf waarbij tussen elke 2 knopen een wandeling bestaat.

Question 10

Wanneer is een graaf niet samenhangend?

Answer 10

Als ze uit meer dan 1 deel bestaat.

Question 11

definitie graad van een knoop

Answer 11

De graad van een knoop van een graaf is het aantal bogen dat aan de knoop vastzit.
Daarbij telt de lus telkens voor 2.

Question 12

Aan wat is de som van alle graden gelijk in een graaf?

Answer 12

Aan het dubbel van het aantal bogen.

s = 2v
(v=verbindingen)

Question 13

definitie enkelvoudige graaf

Answer 13

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.

Question 14

definitie cykel

Answer 14

Een cykel is een gesloten pad: de begin- en eindknoop zijn dezelfde.

Question 15

definitie volledige graaf

Answer 15

Enkelvoudige grafen waarin alle knopen met elkaar verbonden worden door een boog.

Question 16

Wat is een bewijs uit het ongerijmde?

Answer 16

Dan bekijk je of dat het tegenovergestelde vals is.

Question 17

Wat is een component

Answer 17

Een deel van een niet-samenhangende graaf.

Als de niet-samenhangende graaf uit 2 delen bestaat, heeft die 2 componenten.

Question 18

Wat betekent een graaf kleuren?

Answer 18

Betekent dat je aan elke knoop een kleur toekent worst twee buren niet dezelfde kleur hebben.

Question 19

Wanneer is een graaf alleen k-kleurbaar?

Answer 19

Als en slechts als je met k kleuren de graaf kunt kleuren.

Question 20

Wat is het chromatisch getal van een graaf?

Answer 20

Het kleinste aantal kleuren dat nodig is om de graaf te kleuren.

Question 21

Wat is de bovengrens van het chromatisch getal?

Answer 21

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.

Question 22

Wat is de ondergrens van een chromatisch getal?

Answer 22

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.

Question 23

Wat is een vlakke graaf?

Answer 23

Een graaf die zodanig getekend kan worden dat de bogen elkaar niet snijden.

Question 24

Wat is een spoor?

Answer 24

Een wandeling waarbij je meer dan 1 keer dezelfde boog passeert.

Question 25

Wat is een circuit?

Answer 25

Een gesloten spoor: de begin en eind knoop wijn hetzelfde.

Question 26

Wat is een eulerspoor?

Answer 26

Een spoor dat alle bogen van de graaf passeert.

Question 27

Wat is een eulercircuit?

Answer 27

Een gesloten eulerspoor.
Een gesloten spoor dat alle bogen van de graaf passeert.

Question 28

Wat is een eulergraaf?

Answer 28

Een graaf met een eulercircuit.

= een graaf met de naam n gesloten spoor dat alle bogen van de graaf passeert.

Question 29

Wanneer is een samenhangende graaf alleen een eulergraaf?

Answer 29

Als en slechts als de graad van elke knoop even is.