Als je er zelf wat over kan vertellen graag. Alle hulp is gewenst.
Bvd,
obl
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.
En ja ik zie dat ik het verkeerd heb geschreven. Ik wijt het aan het late tijdstip waarop ik deze topic opende
quote:Op dinsdag 3 januari 2006 15:14 schreef rudedeltadude het volgende:
huiswerk topic
Slotje dus!