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
AABBCCDD0111101011001000

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

|E| =
2.Makkelijk

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

deg: 4, 4, 4, 3, 3, 2, 2
|E| =
3.Gemiddeld

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

K4
H =
4.Gemiddeld

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

|V| = 8|E| = 10
k =
5.Moeilijk
1315241796201ABCDEFG

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

start: Dk = 5
  1. 1kant AB
  2. 2kant AC
  3. 3kant BD
  4. 4kant DE
  5. 5kant DF
  6. 6kant EF
  7. 7kant GB
  8. 8kant GC
  9. 9kant GD
6.Moeilijk
ABCDEF

Hoeveel gesloten wandelingen van lengte 2 beginnen en eindigen bij C? Een wandeling mag hoekpunten en kanten herhalen. Noem het aantal N.

M = adjacentiematrixL = 2
N =

Antwoordenblad

  1. 1. |E| = 4
  2. 2. |E| = 11
  3. 3. H = 3
  4. 4. k = 3
  5. 5. kant AB
  6. 6. N = 3

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