Werkblad Grafentheorie met antwoorden

Gratis printbaar werkblad Grafentheorie: 6 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Een enkelvoudige graaf heeft 5 hoekpunten met graden 4, 3, 3, 2, 2. Hoeveel kanten |E| heeft hij?

deg: 4, 3, 3, 2, 2
|E| =
2.Makkelijk
ABCDEF

Bepaal de som van de graden van alle hoekpunten van de getoonde graaf, Σ deg.

|V| = 6
Σ deg =
3.Gemiddeld
ABCDEEulercircuitEulerpad, geen circuitgeen van beide

Heeft de samenhangende graaf een Eulercircuit, een Eulerpad dat geen circuit is, of geen van beide? Klik op je antwoord.

|V| = 5|E| = 6
  1. 1Eulercircuit
  2. 2Eulerpad, geen circuit
  3. 3geen van beide
4.Gemiddeld

Een samenhangende graaf heeft 18 hoekpunten en 28 kanten. Hoeveel kanten k moeten worden verwijderd om een opspannende boom over te houden?

|V| = 18|E| = 28
k =
5.Moeilijk
2712101110271ABCDEFG

Het algoritme van Dijkstra start bij A. Klik op het hoekpunt dat in ronde 3 wordt vastgelegd (definitief gemaakt); A zelf is ronde 1.

start: Aronde 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Moeilijk
861410135319711ABCDEFG

Het algoritme van Prim bouwt een minimaal opspannende boom vanaf hoekpunt E. Klik op de kant die het toevoegt als kant nummer 3.

start: Ek = 3
  1. 1kant AC
  2. 2kant BC
  3. 3kant BD
  4. 4kant CE
  5. 5kant DE
  6. 6kant EF
  7. 7kant GB
  8. 8kant GC
  9. 9kant GD
  10. 10kant GE

Antwoordenblad

  1. 1. |E| = 7
  2. 2. Σ deg = 14
  3. 3. Eulercircuit
  4. 4. k = 11
  5. 5. C
  6. 6. kant BC

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.