SES School, Studie en Onderwijs
Wiskunde in de brugklas, Frans voor het examen of een studie Personeel en Arbeid? Moeilijke formulieren van DUO? Iets weten over studiefinanciering of studentenverenigingen? Dit is het forum voor leerkrachten, scholieren en studenten, van brugklas tot uni
Ik ben op zoek naar handige links over dit onderwerp. Ik ben al aardig ver, zoek alleen nog wat sites voor toepassingen van die theorie in de praktijk. En nog wat over geschiedenis.
Als je er zelf wat over kan vertellen graag. Alle hulp is gewenst.
Bvd,
obl
Als je er zelf wat over kan vertellen graag. Alle hulp is gewenst.
Bvd,
obl
Allereerst zou ik het correct spellen, grafentheorie.
Het oudste grafentheoretische probleem zijn de bruggetjes in Koningsbergen (Ook bekend als Königsberg, Monteregium, etc.) (huidige Kaliningrad); Euler heeft dit opgelost. De vraag was namelijk of je een rondje door de stad kon lopen waarbij je elke brug precies éénmaal passeerde en dan weer eindige op de plek waar je begon. Dit wordt een eulertour genoemd.
Daarna komt Kirchhoff met z'n stroomwetten, dat is ook gerelateerd aan grafen, en in de 19e eeuw wordt het vierkleurenprobleem geformuleerd, d.i. kun je elke landkaart kleuren met vier kleuren zodat geen van de aangrenzende landen dezelfde kleur heeft. Dit is pas in de jaren 70 met behulp van een computerbewijs opgelost. (Lelijk, aldus veel wiskundigen).
De echte boost voor grafentheorie kwam, geloof ik, tijdens WO II, waar er veel logistieke problemen waren die met grafentheorie opgelost kunnen worden. Dat is ook waar veel toepassingen te vinden. Bijvoorbeeld, je routeplanner, de korste weg van punt a naar b. Daar heeft de Nederlander Edsger Wybe Dijkstra een algoritme voor bedacht (Dijkstra's kortstepadalgoritme). Voor netwerken van computers. Je wilt dat ze resistent zijn tegen uitval en niet al te duur. Stel je voor, je hebt een netwerk in de vorm van een ster, dus in het midden een centraal schakelpunt, en dan elke computer daarmee verbonden. Dan heb je een kabel minder nodig dan het aantal computers dat je wilt aansluiten (de eerste zet je in het midden, de tweede verbind je middels een kabel met de eerste, de derde ook, etc.). Maar, als die middelste nu kapot gaat, dan heb je een probleem. Je kunt 't ook in een ring doen, dan heb je altijd evenveel stukken kabel nodig als er computers zijn. (1 verbinden met 2, 2 met 3 en 3 weer met 1). Maar je hebt nu dat als computer 2 b.v. kapot gaat 1 en 3 nog wel kunnen communiceren.
Dan is er nog theorie met betrekking tot matchings, kleuringen, etc. om optimale verdelingen en toewijzingen van grondstoffen te bepalen. Gerelateerd aan de eulertour is de hamiltontour (dat is, bezoek elk punt in een graaf precies een keer), dit is b.v. handig voor een vertegenwoordig die de kortste route wil vinden door een aantal steden. (Dit probleem blijkt echter heel lastig, d.w.z. erg rekenintensief te zijn (althans, er is momenteel nog geen slimme methode gevonden, en de vraag is of dat überhaupt kan)).
Volgens mij moet dit wel genoeg opstapjes geven. Leuke toepassingen zijn dus (denk ik), samengevat, Kirchhoff, korstepadalgoritme, en matchings.
Het oudste grafentheoretische probleem zijn de bruggetjes in Koningsbergen (Ook bekend als Königsberg, Monteregium, etc.) (huidige Kaliningrad); Euler heeft dit opgelost. De vraag was namelijk of je een rondje door de stad kon lopen waarbij je elke brug precies éénmaal passeerde en dan weer eindige op de plek waar je begon. Dit wordt een eulertour genoemd.
Daarna komt Kirchhoff met z'n stroomwetten, dat is ook gerelateerd aan grafen, en in de 19e eeuw wordt het vierkleurenprobleem geformuleerd, d.i. kun je elke landkaart kleuren met vier kleuren zodat geen van de aangrenzende landen dezelfde kleur heeft. Dit is pas in de jaren 70 met behulp van een computerbewijs opgelost. (Lelijk, aldus veel wiskundigen).
De echte boost voor grafentheorie kwam, geloof ik, tijdens WO II, waar er veel logistieke problemen waren die met grafentheorie opgelost kunnen worden. Dat is ook waar veel toepassingen te vinden. Bijvoorbeeld, je routeplanner, de korste weg van punt a naar b. Daar heeft de Nederlander Edsger Wybe Dijkstra een algoritme voor bedacht (Dijkstra's kortstepadalgoritme). Voor netwerken van computers. Je wilt dat ze resistent zijn tegen uitval en niet al te duur. Stel je voor, je hebt een netwerk in de vorm van een ster, dus in het midden een centraal schakelpunt, en dan elke computer daarmee verbonden. Dan heb je een kabel minder nodig dan het aantal computers dat je wilt aansluiten (de eerste zet je in het midden, de tweede verbind je middels een kabel met de eerste, de derde ook, etc.). Maar, als die middelste nu kapot gaat, dan heb je een probleem. Je kunt 't ook in een ring doen, dan heb je altijd evenveel stukken kabel nodig als er computers zijn. (1 verbinden met 2, 2 met 3 en 3 weer met 1). Maar je hebt nu dat als computer 2 b.v. kapot gaat 1 en 3 nog wel kunnen communiceren.
Dan is er nog theorie met betrekking tot matchings, kleuringen, etc. om optimale verdelingen en toewijzingen van grondstoffen te bepalen. Gerelateerd aan de eulertour is de hamiltontour (dat is, bezoek elk punt in een graaf precies een keer), dit is b.v. handig voor een vertegenwoordig die de kortste route wil vinden door een aantal steden. (Dit probleem blijkt echter heel lastig, d.w.z. erg rekenintensief te zijn (althans, er is momenteel nog geen slimme methode gevonden, en de vraag is of dat überhaupt kan)).
Volgens mij moet dit wel genoeg opstapjes geven. Leuke toepassingen zijn dus (denk ik), samengevat, Kirchhoff, korstepadalgoritme, en matchings.
Het is tijd voor wat anders.
Hartstikke bedankt!
En ja ik zie dat ik het verkeerd heb geschreven. Ik wijt het aan het late tijdstip waarop ik deze topic opende
En ja ik zie dat ik het verkeerd heb geschreven. Ik wijt het aan het late tijdstip waarop ik deze topic opende
huiswerk topic
Op dinsdag 13 maart 2007 15:37 schreef Tha-CheF het volgende:
rudedeltadude, wie heeft nou zo'n nickname !
Op vrijdag 6 maart 2009 00:34 schreef Gabbylicious het volgende:
Rudedeltatoedeloe :W
rudedeltadude, wie heeft nou zo'n nickname !
Op vrijdag 6 maart 2009 00:34 schreef Gabbylicious het volgende:
Rudedeltatoedeloe :W
quote:Op dinsdag 3 januari 2006 15:14 schreef rudedeltadude het volgende:
huiswerk topic
Heads I win, tails you lose
Out of my way, I'm coming through
Out of my way, I'm coming through
Zo'n profielwerkstuk is toch wel iets langer dan een gemiddelde reactie op Fok! (Mag ik hopen...) Ik heb niet echt het gevoel nu z'n werkstuk af te hebben gemaakt. Bovendien, als-ie geen bronnen geeft mag 't toch ook wel afgekeurd worden. Of voldoet bron Proefielwerkstuk: Graventheorie( WI B )
Het is tijd voor wat anders.
