Resultaten

Vragen bij het wetenschappelijk materiaal

9.1 Prototype example, p. 374-376

In dit gedeelte worden drie problemen genoemd die kunnen voorkomen in netwerken.

1. Beschrijf elk probleem in eigen woorden

Er zijn drie soorten problemen: the shortest path problem, the minimum spanning tree problem en the maximum flow problem.

The shortest path problem gaat om het vinden van de kortste route van twee willekeurige punten in een netwerk.

The miniminum spanning tree problem gaat om het vinden van een verbinding tussen alle punten in een netwerk met zo min mogelijk kosten, afstand, of materialen.

The maximum flow problem gaat om het vinden van een route van twee willekeurige punten in een netwerk waarbij de capaciteit het grootst is. Dit wil dus zeggen dat er naar een route moet worden gezocht waar er zoveel mogelijk eenheden (bijvoorbeeld passagiers, water etc.) per tijdseenheid kan worden getransporteerd

1. Vergelijk je antwoord met wat een medeleerling erover heeft opgeschreven.

De antwoorden zijn vergeleken met de antwoorden van Auke Molenkamp en kwamen erg overeen met mijn eigen antwoorden.

9.2 The terminology of networks, p. 376-379

1. In de alinea’s 1,2 en 3 worden de woorden arc en directed arc gebruikt.
   Wat is het verschil?

Een arc zijn verbindingen tussen 2 punten waar geen ander knooppunt tussen zit.

Een directed arc is een speciale soort arc. Een directed arc is namelijk een arc met een richting. Dus een directed arc van A naar B betekent dat de route alleen kan worden afgelegd van A naar B en niet andersom.

1. Is er een verschil tussen een directed arc AB en een directed arc BA?

Een directed arc AB wil zeggen dat alleen verbinding A à B mogelijk is, terwijl directed arc BA wil zeggen dat alleen verbinding B àA mogelijk is.

1. Welk woord heeft de voorkeur van de schrijvers?

Er zijn 2 woorden voor een lijn tussen twee punten in een netwerk: Arc en link. De schrijver heeft voorkeur voor links als het gaat om undirected arcs, wat voor te stellen is omdat link een korter woord is.

1. Verbindingen in netwerken tussen twee knooppunten kunnen twee richtingen hebben. Welke aanname wordt in het eerste gedeelte van deze alinea gemaakt? Hoe wordt dit in deze alinea nader uitgewerkt?

Als men een undirected arc tussen twee punten heeft, dan wordt de aanname gemaakt dat deze in twee richtingen kan worden gebruikt, maar niet in twee richtingen tegelijkertijd. Als men wilt aangeven dat dit wel mogelijk is zal men 2 arcs moeten tekenen. Het is dat geval ook mogelijk dat beide arcs verschillende capaciteiten hebben.

1. Welke opmerking wordt in de laatste twee regels gemaakt?

In een directed arc kunnen eenheden in de verkeerde richting worden gestuurd om de hoeveelheid in de goede richting te verminderen.

1. Welke naam kun je geven aan een netwerk als er gerichte en ongerichte verbindingen voorkomen?

In de tekst staat dat er dan “a network with a mixture of directed and undirected arcs” ontstaat. Deze kunnen echter wel worden omgezet naar een directed network door bij alle directed arcs een directed arc toe te voegen in tegenovergesteld richting.

1. Kunnen in een ongericht pad gerichte verbindingen voorkomen?

Nee, in de tekst wordt gezegd dat een path met één of meerdere undirected arcs een undirected path is. Ook wordt er gezegd dat een directed path een undirected path genoemd kan worden maar niet andersom.

1. Welke paden spelen een belangrijke rol in gerichte netwerken?

Zoals de tekst zelf verklaard is het verrassend dat de undirected paths een belangrijke rol spelen in directed networks.

1. Let alleen op de eerste twee zinnen. Begrijp je wat een cycle is?

Ja, een cycle is een path dat begint in hetzelfde punt als waar het eindigt.

1. Maak een overzicht van de begrippen uit deze paragraaf.

1. Wanneer spreken we van een “spanning tree”? (opspannende boom)

Een spanning tree is een netwerk waar alle knooppunten met elkaar verbonden zijn en waar geen cykels in voorkomen.

1. Waarom kan in een opspannende boom met n knooppunten het aantal verbindingen niet tenminste gelijk zijn aan n?

Als men meer dan n-1 verbindingen gebruikt krijgt men automatisch een cykel en als men minder dan n-1 verbindingen gebruikt zullen niet alle punten met elkaar verbonden zijn. In een opspannende boom zijn dus altijd n-1 verbindingen aanwezig.

1. In figuur 9.3 is een opspannende boom gemaakt van figuur 9.2. Teken nog een aantal opspannende bomen van figuur 9.2.

9.4 The minimum spanning tree problem, p. 384-388

1. In de tekst wordt uitgelegd wat het verschil is tussen het vinden van de minimaal opspannende boom (the minimum spanning tree) en het vinden van het kortste pad (the shortest -path problem). Leg uit wat het verschil is tussen de twee genoemde problemen.

In een minimum spanning tree problem moeten alle punten met zo min mogelijk lengte aan arcs worden verbonden, terwijl bij een shortest-path problem er maar naar twee punten wordt gekeken die zo kort mogelijk met elkaar moeten worden verbonden.

1. Waar het bij het vinden van de minimaal opspannende boom om gaat wordt in drie punten uitgelegd. Vertaal deze zinnen voor jezelf in het Nederlands.

1. De punten in het netwerk zijn gegeven maar niet de verbindingen. In plaats van verbindingen worden mogelijke verbindingen voorgesteld met hun respectievelijke lengte

2. Men moet een aantal verbindingen gebruiken zodat er een pad mogelijk is tussen elk punt in het netwerk.

3. Het doel is om met zo min mogelijk totale lengte aan de bovengenoemde eisen te voldoen.

1. Ga bij jezelf na of je uit de tekst die je tot nu toe hebt gelezen en uit figuur 9.5 kunt begrijpen wat een “spanning tree” is.

Een spanning tree is een netwerk waarbij het aantal verbindingen n-1 is, waarbij n staat voor het aantal knooppunten. Ook mogen er geen cykels in het netwerk voorkomen.

1. Waarom is figuur 9.5c volgens de schrijvers niet de minimaal opspannende boom?

De auteur beweert dat er een opspannende boom mogelijk is van 14 mijlen, terwijl deze boom 24 mijlen bevat.

1. In de eerste zin staat het woord greedy. Wat houdt dit woord in?

Greedy betekent hebzuchtig. Hiermee bedoelt de auteur dat je hebzuchtig moet zijn voor de kortste weg omdat dit zal resulteren in een minimaal opspannende boom.

1. Om de minimaal opspannende boom te vinden wordt een uitleg gegeven in drie stappen.

   1. Ga elk van de stappen na aan de hand van het uitgewerkte voorbeeld.

De auteur kiest een willekeurig knooppunt (O) en verbindt het met de dichtstbijzijnde knooppunt (A)(stap 1). Daarna zoekt hij naar de volgende dichtstbijzijnde knooppunt (B) (stap 2). Hij herhaalt de stappen 1 en 2 totdat er een minimaal opspannende boom ontstaat en let daarbij op dat er geen cykels onstaan.

1. Vergelijk het resultaat met wat er in de alinea onder figuur 9.5 staat.

Het tweede figuur is aanzienlijk korter in lengte dan figuur 9.5 (24 tegen 14 mijlen). Ook is figuur 9.5 een lange lijn terwijl het tweede figuur veel meer vertakkingen heeft.

1. Vergelijk de methode van Hillier en Lieberman met het algoritme van Kruskal en met het algoritme van Prim. Op welk algoritme lijkt de methode het meest?

Het algoritme van Prim komt het meest in de buurt. Daarbij moet je ook een willekeurig punt kiezen en vanuit daar steeds de kortste verbinding naar het volgende punt zoeken.

1. Is het, volgens hetgeen in de tekst staat, noodzakelijk om in punt O te beginnen om de minimaal opspannende boom te vinden?

Nee, er wordt beweert dat als men in een ander punt begint en hetzelfde algoritme gebruikt, het resultaat hetzelfde zal zijn.

Opgaven over Steinerbomen

1. Ga na dat in geval van een gelijkzijdige driehoek inderdaad voor de lengte van de kortste Steinerboom en de lengte van de minimale-opspannende boom (zonder de hulppunten) geldt: .

2. Hiernaast zie je de kortste Steinerboom van driehoek ABC. Bereken de lengte van de oorspronkelijke minimale-opspannende boom.

De minimaal opspannende boom wordt dan als volgt: Vanuit punt A is AB kortste route, daarna BC.

3. Teken een driehoek ABC, met .

Construeer het punt van Toricelli P.

Vergelijk de minimale-opspannende boom van driehoek ABC met de minimale-opspannende boom van driehoek ABC en het extra punt P.

Opmerking: punt C=punt P

De minimaal opspannende boom is hetzelfde met punt P als zonder punt P omdat P=C en er dus niets aan de driehoek veranderd qua punten.

4. Teken een driehoek ABC, waarbij .

Construeer het punt van Toricelli P.

Vergelijk nu de minimale-opspannende boom van driehoek ABC met de minimale-opspannende boom van driehoek ABC en het extra punt P.

Hier met het punt P wordt de minimaal opspannende boom zelfs langer in lengte omdat het punt P nu een omweg is i.p.v. een centraal punt. Zonder punt P is de minimaal opspannende boom CB+CA en met punt P CB+CA+PC. Natuurlijk geldt CB+CA+PC > CB+CA.

5. Gegeven is een rechthoek ABCD met  en . Teken de rechthoek en construeer de twee Steinerpunten zoals hierboven beschreven. Bereken exact de lengte van de aldus verkregen Steinerboom.

6. Toon aan dat de bij een rechthoekige graaf met lengte x en breedte y geldt dat de punten die worden toegevoegd, zoals beschreven in de theorie hierboven, om de Steinerboom te vormen, liggen op een afstand  van de langste zijden en een afstand  van de kortste zijden.

7. Toon aan dat de bij een rechthoekige graaf met lengte x en breedte y, waarbij , geldt dat de lengte van de Steinerboom, zoals geconstrueerd in de theorie hierboven, gelijk is aan .

8. In de driehoek hiernaast is en

a. Voeg als Steinerpunt het punt van Toricelli toe en bereken exact de lengte van de aldus verkregen Steinerboom.

b. Bereken hoeveel procent de lengte van die Steinerboom korter is dan de lengte van de minimale-opspannende boom.

9. Toon aan dat voor de Steinerpunten die in een willekeurige vierhoek geconstrueerd worden als boven, geldt: <  (vervalt)

10. Gegeven is een trapezium ABCD. (zie de figuur hier naast).

         Teken de Steinerpunten op de manier          zoals in de          theorie beschreven en     bereken exact de lengte van de aldus verkregen Steinerboom.

11. Gegeven is een gelijkbenig trapezium ABCD.(zie de figuur hier naast)

a. Construeer een Steinerboom als in de theoriebeschreven.

b. Bereken exact de lengte van die Steinerboom.

c. Bereken exact de afstand tussen die Steinerpunten

12. Gegeven is een ruit ABCD. Construeer de Steiner-punten zoals beschreven in de theorie.

Maakt het uit op welke zijden je de gelijkzijdige driehoeken, die voor de constructie nodig zijn, tekent?

Ja, want de zijde EF is korter dan de zijde GH en zal daarom dus Steinerpunten opleveren met een kortere boom.

Het lijkt er op dat de lijn die door de Steiner-punten gaat ook door het snijpunt M van de diagonalen AC en BD gaat. Is dit vermoeden juist? Leg dit uit.

Ja, de lijn EG gaat door het midden van zijden AB en DC. Omdat we met een ruit te maken hebben is ∠ABC gelijk aan ∠ADC en ∠BCA gelijk aan ∠DAB. EG gaat dus door het middelpunt net als de twee diagonalen die het middelpunt bepalen.

Bronvermelding

operation research

optimaliseren netwerken TU delft

http://nl.prevos.net/files/2013/09/netwerk.jpg

http://www.slideshare.net/DelftOpenEr/optimaliseren-in-netwerken-steinerpunten?redirected_from=save_on_embed

Logboek