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
AABBCCDDEEFF011000100110100000010011010101000110

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

|E| =
2.Makkelijk
ABCDE

Precies één hoekpunt van de graaf heeft graad 4. Klik erop.

deg = 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
3.Gemiddeld

Hoeveel verschillende Hamiltoncircuits H heeft de volledige graaf K7? Circuits die alleen verschillen in het beginpunt of de richting tellen als hetzelfde.

K7
H =
4.Gemiddeld

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

|V| = 17|E| = 22
k =
5.Moeilijk
161994751120ABCDEF

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

start: Ak = 2
  1. 1kant AB
  2. 2kant AC
  3. 3kant BC
  4. 4kant BD
  5. 5kant CE
  6. 6kant DE
  7. 7kant DF
  8. 8kant BE
6.Moeilijk
7141414121413ABCDEF

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) =

Antwoordenblad

  1. 1. |E| = 7
  2. 2. B
  3. 3. H = 360
  4. 4. k = 6
  5. 5. kant BD
  6. 6. d(F) = 22

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