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 boom heeft 22 hoekpunten. Hoeveel kanten |E| heeft hij?

|V| = 22
|E| =
2.Makkelijk
AABBCCDDEE0010000111110010100101110

De adjacentiematrix van een enkelvoudige ongerichte graaf is getoond. Hoeveel kanten |E| heeft de graaf?

|E| =
3.Gemiddeld

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

|V| = 8|E| = 16
k =
4.Gemiddeld

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

|V| = 19|E| = 30
k =
5.Moeilijk
41618215149ABCDE

Het algoritme van Kruskal bouwt een minimaal opspannende boom. Klik op de kant die het toevoegt als kant nummer 4; overgeslagen kanten tellen niet mee.

k = 4
  1. 1kant AB
  2. 2kant AC
  3. 3kant BC
  4. 4kant BD
  5. 5kant CE
  6. 6kant DE
  7. 7kant BE
6.Moeilijk
1358131513414610ABCDEFG

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

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

Antwoordenblad

  1. 1. |E| = 21
  2. 2. |E| = 6
  3. 3. k = 9
  4. 4. k = 12
  5. 5. kant CE
  6. 6. D

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