Profielwerkstuk: Grafentheorie

[Dux]

Beste studenten,

Wij zijn Duke Bouwer en Nisrin Saïdi. Wij gaan naar 6VWO van het Wateringse Veld College in Den Haag en voor ons profielwerkstuk willen wij een onderzoek afleggen met betrekking tot de grafentheorie. In specifiek over de (praktische) toepassingen van de grafentheorie.

Tot nu aan toe zijn wij na een gesprek met onze coördinator tot het volgende gekomen:

Deelvragen:
Literatuur

1.  Het onstaan van grafen theorie
   

a. Waarom
b. Wie
c. Hoe
2. De ontwikkelingen van grafen theorie
3. Wat zijn de toepassingen van grafen theorie?
a. Praktisch
b. Theoretisch
Praktijk
Experiment

En voor ons experiment hadden we het idee opgevat om een x aantal coördinaten (knopen) te weergeven op een assenstelsel en dan een shortest path algorithm er op los te laten. Met de weging van de wegen gekozen door de lengte berekend dmv. Pythagoras. En het aantal wegen van elke knoop te beperken door een limiet aan de lengte van een weg te stellen.
We wouden dit realiseren in Python.

Hierover hebben we een aantal vragen. Ten eerste of het mogelijk was om iemand te spreken over de theorie achter de Grafentheorie. Ten tweede of ons experiment te realiseren valt. Ten derde wat zijn interessante praktische applicaties van Grafentheorie b.v. bij een bedrijf zodat we daar ook mogelijk een kijkje zouden kunnen nemen. Ten vierde wat voor literatuur handig zou zijn voor ons om onszelf in te verdiepen. Ten vijfde of er een betere programmeer taal beschikbaar is om dit in te doen. Als laatst of er nog ergens aanvullingen zijn op onze deelvragen.

Wij zouden het erg op prijs stellen als jullie ons hiermee kunnen helpen!

Met vriendelijke groet,

Duke Bouwer en Nisrin Saïdi

[jip_rietveld]

Hey @Dux

Wat hebben jullie een vet PWS onderwerp gekozen zeg. Grafentheorie komt veel terug in mijn studie informatica en is ontzettend interessant! Jullie stellen mij veel vragen ik hoop dat ik ze structureel kan beantwoorden, maar je kunt natuurlijk altijd nog reageren en doorvragen.

Jullie eerste vraag is makkelijk, ik heb veel vakken gehad waarin grafentheorie is besproken en jullie kunnen mij gewoon hier op het forum al jullie vragen stellen over grafentheorie.

Jullie tweede vraag is ook gemakkelijk, hier bespreek ik ook jullie 5de vraag. De programmeer taal Python is een ontzettend krachtige programmeer taal met veel mogelijkheden. Ik weet niet hoeveel programmeer ervaring jullie hebben maar het is ook een goede instap programmeer taal. Er zullen denk ik wel zogenaamde libraries zijn die het implementeren best gemakkelijk kunnen maken. Anders is een graaf ook weer niet zo ingewikkeld of groot dat het onmogelijk is om te programmeren. Het enige wat ik denk dat jullie in de gaten moeten houden is hoeveel tijd jullie aan dit programmeren kwijt gaan zijn. Dit is al snel ter grootte van een eerstejaars opdracht op de universiteit, maar die studenten hebben dan al colleges gehad en kleinere opdrachten om mee te beginnen, als jullie dit gaan maken van de grond kan het lang duren.

Het prachtige aan de grafentheorie is hoe breed toepasbaar die is. Heel duidelijk is natuurlijk het voorbeeld van een route, dan is elke knoop een kruispunt en de waarde van de wegen hoe lang je erover doet om van knoop X naar knoop Y te gaan. Dit wordt gebruikt in elke route app. Maar het kan ook heel anders worden ingevuld. Zo is elke knoop opeens een waarde van afstand, denk meter, voet of lichtjaar. En is elke weg ertussen de ratio om van het een naar het ander te gaan (let op, dit is dus een graaf waar een weg een richting heeft). Zo kun je van elke afstand meter naar een andere gaan. Google gebruikt dit bijvoorbeeld.. Als laatste voorbeeld neem ik een netwerk tussen verschillende computers. Hier hebben wegen dus niet perse een waarde en representeren ze simpel dat er een connectie is tussen 2 plekken. Er zijn dus een hoop applicaties van de grafentheorie!

Goede voorbeelden van literatuur heb ik niet perse liggen, er is namelijk heel veel te lezen over de graaftheorie. Ik raad jullie aan om lekker rond te googlen. Als dat in het Nederlands niet altijd lukt kun je ook in het Engels naar graph theory googlen.

Als laatste bespreek ik jullie deelvragen. Als eerste wil ik zeggen dat ik nog geen hoofdvraag zie! Hoe kun je deelvragen hebben zonder hoofdvraag. Alle deelvragen samen zouden samen de hoofdvraag moeten beantwoorden en dat zie ik nog niet terug. Jullie eerste deelvraag vind ik bijvoorbeeld meer thuis in een werkstuk uit de 3 of 4de klas. Niet echt onderdeel van een PWS die een hoofdvraag probeert te antwoorden. Als jullie nog op zoek zijn naar een goede hoofdvraag zou ik kijken naar deel vraag 3. Er zijn namelijk zoveel verschillende toepassingen van de grafen theorie! Misschien dat jullie PWS de 5 belangrijkste op een rijtje zet en er eentje probeert te implementeren.

Alright, dat is een groot stuk tekst maar ik hoop dat jullie er wat aan hebben. Jullie zijn hier altijd welkom om vragen te stellen, dus vraaag maar raak.

Groetjes,
Jip

[Dux]

Hoi Jip Rietveld ,

Onze excusen voor de late reactie, bedankt voor de hulp tot nu aan toe.
Onze hoofdvraag is: Hoe en waar wordt grafentheorie gebruikt in de samenleving? En hoe werkt een kortste pad algoritme in een 3 dimensionale ruimte? Echter heeft onze begeleider ons aangeraden om dit te veranderen in een stelling. Daardoor hebben we dit als hoofdvraag(?) gekregen: Een overzichtelijke weergave van de verschillende toepassingen van de Grafentheorie. En een praktische toepassingen van een kortste pad algoritme in een 3 dimensionale ruimte.

Het programmeren gaat tot nu aan toe vrij goed. Door voornamelijk gebruik te maken van de modules matplotlib en random zijn we in ieder geval gekomen waar we visueel willen zijn. Dit is soort afbeeldingen krijg je dan willekeurig gegenereerd.

De wegen tussen de knopen worden beperkt door een maximale afstand. We zijn nu bezig met de implementatie van een kortste pad algoritme (Dijkstra) op de code. Echter lijkt het erop dat de manier waarop wij ervoor gekozen hebben om dit te doen zich niet meteen goed leent voor een toepassing van het Dijkstra algoritme. We hebben op het moment een list voor alles gemaakt. Dat ziet er enigzins als volgende uit voor deze afbeelding:
[((5.035439269159083, 8.592628401802553), (8.440459930424113, 8.203323745263509), 3.427203498370753), ((5.911103706821158, 6.593396217046729), (8.440459930424113, 8.203323745263509), 2.9982510822126276), ((8.817396026229495, 5.2710387199557385), (8.440459930424113, 8.203323745263509), 2.9564127401236107), ((7.35925437326913, 4.463425487622859), (8.440459930424113, 8.203323745263509), 3.8930507875349356), ((5.5144125037536025, 8.973001812872301), (8.440459930424113, 8.203323745263509), 3.025583889249003), ((6.132158968747671, 6.864454653985399), (8.440459930424113, 8.203323745263509), 2.668487169400719), ((5.911103706821158, 6.593396217046729), (5.035439269159083, 8.592628401802553), 2.1825942215514047), ((5.5144125037536025, 8.973001812872301), (5.035439269159083, 8.592628401802553), 0.611636567993422), ((6.132158968747671, 6.864454653985399), (5.035439269159083, 8.592628401802553), 2.046797157050516), ((2.757772695924386, 6.185367883006252), (5.035439269159083, 8.592628401802553), 3.314010896811615), ((5.911103706821158, 6.593396217046729), (6.627295770572238, 4.321878264034964), 2.3817482828869205), ((8.817396026229495, 5.2710387199557385), (6.627295770572238, 4.321878264034964), 2.386932068768133), ((7.35925437326913, 4.463425487622859), (6.627295770572238, 4.321878264034964), 0.7455192905401096), ((6.132158968747671, 6.864454653985399), (6.627295770572238, 4.321878264034964), 2.590338810127827), ((8.817396026229495, 5.2710387199557385), (5.911103706821158, 6.593396217046729), 3.1929867516112003), ((7.35925437326913, 4.463425487622859), (5.911103706821158, 6.593396217046729), 2.575638884031719), ((5.5144125037536025, 8.973001812872301), (5.911103706821158, 6.593396217046729), 2.4124441345398155), ((6.132158968747671, 6.864454653985399), (5.911103706821158, 6.593396217046729), 0.34976864505131655), ((2.757772695924386, 6.185367883006252), (5.911103706821158, 6.593396217046729), 3.179620037938984), ((7.35925437326913, 4.463425487622859), (8.817396026229495, 5.2710387199557385), 1.6668581862705498), ((6.132158968747671, 6.864454653985399), (8.817396026229495, 5.2710387199557385), 3.1224145134323953), ((6.132158968747671, 6.864454653985399), (7.35925437326913, 4.463425487622859), 2.696424334099007), ((6.132158968747671, 6.864454653985399), (5.5144125037536025, 8.973001812872301), 2.197175872856494), ((2.757772695924386, 6.185367883006252), (5.5144125037536025, 8.973001812872301), 3.9204548150755585), ((2.757772695924386, 6.185367883006252), (6.132158968747671, 6.864454653985399), 3.4420403194525635)]

Met (5.035439269159083, 8.592628401802553) als het eerste coordinaat, (8.440459930424113, 8.203323745263509) als het tweede coordinaat en 3.427203498370753 als de afstand tussen de coordinaat. Weet je misschien een manier waardoor we hier het dijkstra algoritme oid op kunnen los laten of moet dit eerst omgezet worden naar een andere vorm, bijvoorbeeld een matrice, om dit te doen. Indien dat zou moeten heb je enig idee hoe?

We zullen zeker kijken naar het gelinkte artikel.

Bedankt in ieder geval voor de hulp.

Met vriendelijke groet,

Duke Bouwer

[jip_rietveld]

Hey Duke,

Als jullie de afstand tussen twee coordinaten al weten, dan is dijkstra niet moeilijk om te implementeren. Een visueel voorbeeld kunnen jullie op de website https://visualgo.net/en/sssp vinden.

Weten jullie welk coordinaat welk punt is? Heeft elk knooppunt een ID zegmaar? Die zal wel nodig zijn. Daar komt eventueel een matrix toch handig bij kijken. Die wordt dan NxN groot. Waar N het aantal knooppunten is. Dan is punt (i,j) in die matrix de afstand van knoop i naar knoop j. (Voor de oplettende kijkers, (j,i) zal hetzelfde moeten zijn.) Als i=j dan staat er nul. (De afstand tot jezelf is nul). Met een matrix als dit, is een kortste pad algoritme makkelijker te doen.

Is dit te volgen?

Groetjes,
Jip

[Dux]

Hoi Jip Rietveld,

Bedoelt u dan dat we elke punt (x,y) een eigen id geven en dat id dan in een matrix stoppen?

Met vriendelijke groet,

Duke

[jip_rietveld]

Ha Dux,

Ja dus nu hebben jullie een grote lijst met de coordinaten (x,y) wat vervolgens samen met andere coordinaten gecombineerd wordt om een afstand te berekenen. Wat ik zou doen is die coordinaten echt als knooppunt te zien.

Dan hebben ze dus niet alleen coordinaten (x, y) maar ook een ID. Dat is dan een nummer [0, 1, 2, ..., N].

Die knooppunten stop je vervolgens in een Graaf G. Dan kun je daarna (als je het goed programmeert) makkelijk aan G vragen: "Geef mij de coordinaten van knooppunt 3. Dan geeft G de x en y terug. Is dit te volgen?

Hoe je die opslaat in G moet je even over nadenken. Dat kan in een matrix of in een lijst. In een dictionary misschien ook. Meerdere antwoorden zijn mogelijk!

Groetjes,
Jip