Grafentheorie

Deel van een serie artikelen over Wiskunde
Formules van een stochastisch proces
Kwantiteit
Complex getal · Geheel getal · Natuurlijk getal · Oneindigheid · Reëel getal · Rekenkunde
Structuur en ruimte
Algebra · Functie · Getaltheorie · Goniometrie · Groepentheorie · Meetkunde · Topologie
Verandering
Analyse · Chaostheorie · Differentiaalrekening · Dynamische systemen · Vectoren
Toegepaste wiskunde
Discrete wiskunde · Grafentheorie · Informatietheorie · Kansrekening · Statistiek · Wiskundige natuurkunde
Portaal    Wiskunde

De grafentheorie is een deelgebied van de wiskunde dat de eigenschappen van grafen bestudeert.

Een graaf bestaat uit een verzameling punten, knopen genoemd, waarvan sommige verbonden zijn door lijnen, de zijden, kanten, takken of bogen. Afhankelijk van de toepassing kunnen de lijnen gericht zijn, dan worden ze ook wel pijlen genoemd, men spreekt dan van een gerichte graaf. Ook worden wel gewichten aan de lijnen toegekend door middel van getallen, deze stellen dan bijvoorbeeld de afstand tussen twee punten voor. Een graaf met gewichten noemt men een gewogen graaf.

Structuren die als grafen weergegeven kunnen worden, komen veel voor. Grafen worden bijvoorbeeld gebruikt om eindigetoestandsautomaten te modelleren, om een schematische routekaart te maken tussen een aantal plaatsen met de afstanden daartussen en bij patroonvergelijking. Verschillende soorten grafen spelen in de informatica nog een rol, niet alleen in de vorm van boomstructuren, maar ook om gegevensoverdracht over netwerken weer te geven. Er kunnen algoritmes worden uitgevoerd om bepaalde eigenschappen van zo'n graaf te berekenen en aan de hand daarvan voorspellingen te doen of beslissingen te nemen over de optimale route voor een datapakket. Dit is binnen de informatica dan ook een belangrijk onderwerp.

Complexe netwerken vormen een vrij recent gebied in het onderzoek rond grafen, dat minder is gericht op de studie van kleine grafen en de eigenschappen van individuele knopen en zijden in deze grafen, maar eerder op de statistische eigenschappen van grootschalige netwerken.