Profielwerkstuk: Grafentheorie



  • 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

    1.  De ontwikkelingen van grafen theorie
      
    2.  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


  • PWS TU Delft admin

    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



Het lijkt erop dat je verbinding naar Forum verloren is gegaan, wacht even terwijl we de verbinding proberen te herstellen.