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 14 kanten. Hoeveel hoekpunten |V| heeft hij?

|E| = 14
|V| =
2.Makkelijk

Een bos (een graaf zonder cykels) heeft 16 hoekpunten en 5 samenhangende componenten. Hoeveel kanten |E| heeft het?

|V| = 16c = 5
|E| =
3.Gemiddeld

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

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

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

|V| = 14|E| = 18
k =
5.Moeilijk
112111112148121ABCDEF

Gebruik het algoritme van Dijkstra om de lengte d(F) van het kortste pad van A naar F in de gewogen graaf te vinden.

start: Aeinde: F
d(F) =
6.Moeilijk
91719121511310136ABCDEFG

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

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

Antwoordenblad

  1. 1. |V| = 15
  2. 2. |E| = 11
  3. 3. k = 5
  4. 4. k = 5
  5. 5. d(F) = 24
  6. 6. kant DF

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