Grafentheorie

Deel van een serie artikelen over
Wiskunde
Formules van een stochastisch proces
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  Portaalicoon   Wiskunde
Enkelvoudige graaf met zes knopen

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.


Grafentheorie

Dodaje.pl - Ogłoszenia lokalne