Grafen theorie

Dit forum is voor het voortgezetonderwijs (of 2de/3de graad ASO), als je in de bovenbouw zit. We gaan er vanuit dat je een Grafische Rekenmachine hebt.
Plaats reactie
ipass
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 09 jun 2016, 15:40

Grafen theorie

Bericht door ipass » 09 jun 2016, 15:47

Hallo,

Zou iemand deze opdracht voor mij kunnen controleren en mij op weg willen helpen
met de tweede opdracht van de grafen theorie?

Eerste: https://gyazo.com/c15d6cd46c8088a1594d47a944acfc12
Tweede: https://gyazo.com/abbd58ea032aa2dfb816c8859aef511c


Bij voorbaat dank.

arie
Moderator
Moderator
Berichten: 3910
Lid geworden op: 09 mei 2008, 09:19

Re: Grafen theorie

Bericht door arie » 09 jun 2016, 23:48

Je eerste antwoord klopt niet. Het gaat niet om de kortste afstand naar naar een buur van elk punt, maar om de kortste afstand van elk punt naar punt A.

Het algoritme van Dijkstra vind je hier:
https://nl.wikipedia.org/wiki/Kortstepad-algoritme

We zoeken dus de kortste verbinding van elk punt naar punt A (= gb = beginpunt = startpunt).

We beginnen (= "initieel geldt" op die wiki pagina):
A = {A} verzameling A bestaat uit punt A
X = {F, E, G, B} deze punten zijn direct verbonden met punt A
d(A) = 0

voor alle punten g in X geldt: d(g) = gewicht(gb, g), dus:
- d(F) = gewicht(A, F) = 2, vanaf punt A
- d(E) = gewicht(A, E) = 20, vanaf punt A
- d(G) = gewicht(A, G) = 4, vanaf punt A
- d(B) = gewicht(A, B) = 8, vanaf punt A

Voor alle andere punten geldt: d(g) = oneindig = oo, dus:
- d(H) = oo
- d(C) = oo
- d(D) = oo

Nu gaan we de volgende lus steeds herhalen, totdat we alle afstanden gevonden hebben:

1. Kies uit X het punt x met minimale waarde d(x). Bij ons is dat punt F met waarde d(F) = 2
Deze waarde is definitief. We weten nu dus:
d(A) = 0
d(F) = 2 (vanuit punt A)
Verplaats x naar verzameling A:
A = { A, F }

2. Voor alle punten z bereikbaar vanuit x (= punt F), en die nog niet in verzameling A zitten doen we het volgende: ...
de punten bereikbaar vanuit F zijn punt A en punt E, alleen punt E zit nog niet in verzameling A, dus voor punt E:
2.1 zit E nog niet in X: niet waar want E zit wel in X, dus doen we bij 2.1 niets
2.2 zit E wel in X: klopt, dus vergelijken we:
- de huidige d(E) = 20, met:
- d(F) + gew(F, E) = 2 + 14 = 16
De laatste is kleiner, dus nu wordt
d(E) = 16, vanaf punt F

Onze eerste lus is nu klaar, en we hebben nu deze situatie:
A = { A, F }
X = { E, G, B }
d(A) = 0
d(F) = 2, pad komt vanaf punt A

d(E) = 16, pad komt vanaf punt F
d(G) = 4, vanaf punt A
d(B) = 8, vanaf punt A

d(H) = oo
d(C) = oo
d(D) = oo

Hier in een plaatje, in rood de definitieve verbinding, in blauw de mogelijke verbindingen.

Afbeelding

Kan je nu zelf de lus nog een keer uitvoeren?
En nog een keer en nog een keer ... totdat alle punten hun definitieve afstand tot punt A hebben?

Je tweede opdracht volgt hetzelfde schema, maar nu vanuit een matrix = tabel M.
Als je het gemakkelijker vindt, kan je M ook eerst tekenen als een graaf zoals in de eerste opdracht.

ipass
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 09 jun 2016, 15:40

Re: Grafen theorie

Bericht door ipass » 02 jul 2016, 17:55

Bedankt voor uw uitleg. Ik heb inmiddels een andere grafen opdracht ontvangen.
Zou u willen kijken of ik het nu wel goed heb toegepast?
Verder heb ik bij de tweede opdracht wat redundante waardes, moet ik het zo laten of veranderen?

Bij voorbaat dank.

Opdracht 1. https://gyazo.com/9dde22749cdcf7cf03819eff5eee9221
Opdracht 2. https://gyazo.com/76ff0c9d751f7b6760d95d54200325a7

arie
Moderator
Moderator
Berichten: 3910
Lid geworden op: 09 mei 2008, 09:19

Re: Grafen theorie

Bericht door arie » 08 jul 2016, 21:58

Opdracht 1:

Bijna OK, kijk nog eens goed naar B = [24,C]: dat kan korter


Opdracht 2:

De eerste regel van de tabel is al gegeven:

Code: Selecteer alles

A      B      C      D      E      F      G      H      afg.
0,A    oo,-   oo,-   oo,-   oo,-   oo,-   oo,-   oo,-   A
A is afgehandeld = daar kan een streep onder = we zijn klaar met A.
Vervolgens kijken we welke punten we vanuit A kunnen bereiken.
Dit gaat via de eerste regel van matrix M, dat had je zelf al gevonden:

Code: Selecteer alles

A      B      C      D      E      F      G      H      afg.
0,A    oo,-   oo,-   oo,-   oo,-   oo,-   oo,-   oo,-   A
===
       28,A   oo,-   oo,-   oo,-    3,A   12,A   24,A
Van de nog niet afgehandelde punten kijken we nu welk punt de kleinste afstand heeft, dat is punt F op afstand 3.
Punt F is daarmee ook afgehandeld, daar kan een streep onder.
Nu kijken we welk van de onafgehandelde punten we via F kunnen bereiken en wat de afstand via F is.
Voor elk punt vergelijken we dit met de afstand die we al hadden.
We vullen steeds de kortste route in.

De punten die we vanuit F kunnen bereiken lezen we af uit regel 6 (= F) van de matrix M:
A: is al afgehandeld
B: niet vanuit F te bereiken (oo), dus blijft [28,A]
C: niet vanuit F te bereiken (oo), dus blijft [oo,-]
D: niet vanuit F te bereiken (oo), dus blijft [oo,-]
E: afstand 20 tot F, dus AE via F = AF + FE = 3 + 20 = 23, via F: [23,F]
F: is al afgehandeld
G: afstand 6 tot F, dus AG via F = AF + FG = 3 + 6 = 9, dit is korter dan de afstand 12 die we al hadden, dus dit veranderen we in [9,F]
H: niet vanuit F te bereiken (oo), dus blijft [24,A]

Code: Selecteer alles

A      B      C      D      E      F      G      H      afg.
0,A    oo,-   oo,-   oo,-   oo,-   oo,-   oo,-   oo,-   A
===
       28,A   oo,-   oo,-   oo,-    3,A   12,A   24,A   F
                                   ====
       28,A   oo,-   oo,-   23,F           9,F   24,A
We herhalen steeds bovenstaand schema, dus:
Van de nog niet afgehandelde punten kijken we nu welk punt de kleinste afstand heeft, dat is punt G op afstand 9 vanaf A.
.... etc.

Kan je nu de tabel verder invullen?

Noot:
[1] er kunnen geen punten dubbel afgehandeld worden (zoals F in jouw tabel)
[2] je bent klaar als alle punten afgehandeld zijn, de uiteindelijke tabel heeft dus 8 regels.

Plaats reactie