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
AABBCCDD0111100010011010

De adjacentiematrix van een enkelvoudige ongerichte graaf is getoond. Bepaal de graad deg(D) van hoekpunt D.

deg(D) =
2.Makkelijk
ABCDEFG

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

|V| = 7
Σ deg =
3.Gemiddeld

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

|V| = 13|E| = 18
k =
4.Gemiddeld

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

K8
H =
5.Moeilijk
8415757122511ABCDEFG

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
31110161218511714ABCDEFG

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

k = 2
  1. 1kant AB
  2. 2kant AC
  3. 3kant BC
  4. 4kant BD
  5. 5kant CE
  6. 6kant DE
  7. 7kant DF
  8. 8kant GB
  9. 9kant GC
  10. 10kant GE

Antwoordenblad

  1. 1. deg(D) = 2
  2. 2. Σ deg = 14
  3. 3. k = 6
  4. 4. H = 2520
  5. 5. d(F) = 18
  6. 6. kant AB

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