thumb|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.
Definitie Er zijn verschillende definities gangbaar om grafen te definiëren. Hier volgen de definities zoals ze in deze encyclopedie worden gehanteerd.
Een graaf bestaat uit een verzameling knopen, punten of toppen, Engels: vertices, en een verzameling zijden, kanten, bogen of takken, Engels: edges, van paren knopen. Formeler:
Een graaf is een geordend paar, waarin een willekeurige verzameling is en waarin een multiset bestaande uit multisets van twee al dan niet verschillende elementen uit . De elementen van heten de knopen van de graaf en de elementen van heten de zijden van . De knopen die een zijde vormen, heten de eindpunten van de zijde.
Ter verduidelijking schrijft men ook voor de knopen van voor de zijden van
Een zijde verbindt twee verschillende knopen met elkaar of is een lus die bij dezelfde knoop terugkomt.
Twee knopen kunnen door meer dan een zijde zijn verbonden. In de grafische voorstelling wordt soms, in plaats van elke zijde afzonderlijk, het aantal zijden tussen twee knopen weergegeven als één zijde met daarnaast een getal dat het aantal zijden voorstelt.
Terminologie en notatie Terminologie en notatie voor alle hier besproken grafen: De aanduiding voor een graaf betekent meestal dat willekeurig kan worden gekozen. De elementen van heten de knopen of punten van de graaf. kan ook als worden genoteerd. De elementen van heten de zijden, lijnen, kanten, bogen of takken van de graaf. kan ook als worden genoteerd. Twee knopen heten met elkaar verbonden als er een zijde tussen hen is. Deze knopen zijn dan adjacent. Men noteert als de twee knopen en met elkaar zijn verbonden. Als de knoop een begin- of eindpunt is van de zijde , heet verbonden met . Een lus is een zijde die een knoop met zichzelf verbindt. Een wandeling tussen twee knopen en is een rij verbonden knopen, waarvan het begin en het einde is. De rij van knopen is dus een wandeling tussen en , als , In een ongewogen graaf is de lengte van een wandeling het aantal zijden in de wandeling. Het aantal knopen was , de lengte van de wandeling dus . Een graaf heet samenhangend of transitief als er tussen elk paar knopen van de graaf een wandeling mogelijk is. Een pad tussen twee knopen en is een wandeling tussen en waarin geen knoop meer dan eenmaal voorkomt. Een multigraaf is een graaf met multisets van twee knopen die door meer dan een zijde zijn verbonden. De afstand tussen twee knopen en is de lengte van het kortste pad tussen en , tevens de lengte van de kortste wandeling tussen en . Als er geen wandeling mogelijk tussen en is de afstand tussen en ongedefinieerd. De diameter van een samenhangende graaf is de grootste afstand tussen twee knopen in . Een cykel in een graaf is een pad met lengte groter dan nul van een knoop naar zichzelf. Een cykel kan dus uit een lus van een knoop naar zichzelf bestaan. De taille van een samenhangende graaf is de lengte van de kortste cykel in de graaf. De graad van een knoop is het aantal zijden waarmee verbonden is. Bij het bepalen van de graad telt een lus dubbel. Als alle knopen van een graaf dezelfde graad hebben, wordt de graaf -regulier genoemd. Een graaf heet regulier als er een getal is, zo dat de graaf -regulier is. Twee grafen en heten isomorf, als de ene graaf ontstaat uit de andere door alleen de namen van de knopen te veranderen. Meer formeel is er dan een bijectie zodanig dat dan en slechts dan als . De graaf heet een deelgraaf van de graaf als de knopen en zijden van ook knopen en zijden van zijn, dus als en . Een partitie van een graaf is een partitie van de verzameling knopen van , dus een disjuncte opdeling van de knopen. Een subdivisie van een graaf is die graaf waarin bogen door paden van willekeurige lengte zijn vervangen.
Enkelvoudige graaf thumb|Enkelvoudige graaf
De enkelvoudige graaf is de meest gebruikte soort graaf. In een enkelvoudige graaf komen geen lussen voor en is er niet meer dan één zijde tussen twee knopen. De enkelvoudige graaf vindt veel toepassing binnen de wiskunde en de informatica. Over deze grafen is een groot aantal stellingen bewezen.
Componenten en samenhangende grafen thumb|100px|Graaf met twee componenten
Binnen een enkelvoudige ongerichte graaf is een component van een deelgraaf waarbij tussen elk tweetal knopen van een wandeling is, en er geen wandeling is naar enige andere knoop. Dat betekent dat de zijden van een enkelvoudige ongerichte graaf alleen tussen de knopen in dezelfde component lopen. Een graaf die uit maar een component bestaat, dus waarin een wandeling tussen elk paar punten bestaat, is daarmee een samenhangende graaf. De componenten van een enkelvoudige ongerichte graaf zijn samenhangende deelgrafen. Een enkelvoudige ongerichte graaf valt in een partitie uiteen in onderling disjuncte componenten.
Matrixvoorstelling van een graaf Een eindige graaf kan eenvoudig voorgesteld worden in een matrix, de bogenmatrix. Zijde en boog zijn ten aanzien van grafen synoniem. De bogenmatrix is een vierkante matrix met dimensies , waarin het aantal knopen in de graaf is. Het element op rij en kolom in de bogenmatrix is 1 als er een zijde (boog) bestaat die van naar gaat en 0 als dit niet het geval is. Soms worden lussen dubbel geteld, zodat de graad van een knoop uit de bogenmatrix kan worden uitgelezen door de elementen in de overeenkomstige rij of kolom bij elkaar op te tellen. Hieronder doen we dat echter niet.
{| class="wikitable" ! Gelabelde graaf ! Bogenmatrix |- | 160px
Is de bogenmatrix opgesteld, dan kan deze worden gebruikt om af te lezen hoeveel wandelingen er van een knoop naar een andere zijn. Door de bogenmatrix tot de macht te verheffen, kan men in de kolom op rij aflezen hoeveel wandelingen er zijn van lengte van knoop naar knoop .
In het bovenstaande voorbeeld is
Er zijn dus bijvoorbeeld drie wandelingen van lengte drie van knoop 4 naar knoop 6, namelijk 4~3~4~6, 4~5~4~6, en 4~6~4~6.
Voor een enkelvoudige graaf zonder lussen kan een matrix worden gemaakt, waarin op de hoofddiagonaal de graad van ieder van de knopen in de graaf staan. Er geldt dan dat in de matrix van Laplace de som van de elementen in alle rijen en in alle kolommen gelijk is aan 0. De graad van knoop 1 is drie en dat is ook de som van de elementen in zowel de eerste rij als in de eerste kolom van de bogenmatrix.
Komen er in een graaf veel meer knopen dan zijden voor, dan is het gunstig om de graaf in een incidentiematrix vast te leggen. Is het aantal zijden in de graaf, dan is de incidentiematrix een -matrix.
Boom Een boomstructuur is een samenhangende graaf zonder cykels. Een samenhangende graaf zonder cykels heet een boom, omdat een dergelijke graaf in een tekening vaak op een boom lijkt. Een boom heeft één zijde minder dan het aantal knopen. Een boom met de verzameling knopen heeft dus zijden.
thumb|Boom met zes knopen en vijf zijden
Het is bij algoritmes op bomen vaak handig en ook gebruikelijk om een knoop in de boom aan te wijzen en deze een speciale status binnen de boom te geven, vaak wordt deze knoop gezien als het 'begin' van de boom. Deze knoop wordt dan de wortel van de boom genoemd. Bomen behoren tot de fundamentele structuren in de wiskunde en de informatica. Bomen worden vaak gebruikt om model te staan voor verzamelingen van objecten met een bepaalde hiërarchie en zijn terug te vinden in bijvoorbeeld: onderzoek naar taal en structuur van wiskunde, als model van de opbouw van termen, documenten en dergelijke compilatie, als model voor de structuur van formele talen bestandssystemen, als het model waarnaar een bestandssysteem opgebouwd wordt codeertheorieën, zoals Huffmancodering
De veelvuldigheid en populariteit van bomen maakt dat er voor bomen als zodanig vele algoritmen gedefinieerd zijn. Voorbeelden hiervan zijn breadth-first search depth-first search minimaal opspannende boom
Cykelgraaf thumb|Cykelgraaf
De cykelgraaf met knopen is de enkelvoudige, samenhangende graaf met knopen, waarin iedere knoop verbonden is met twee andere. Een dergelijke graaf heeft de vorm van een cirkel en er komen evenveel knopen als zijden in voor. De cykelgraaf met het minste aantal knopen en zijden is de volledige graaf . Cykelgrafen zijn binnen de informatica zeer bekend als netwerkmodel. Het Token Ring netwerk is hierop gebaseerd. Cykelgrafen dienen ook vaak als model voor lokale zoekalgoritmen.
Volledige graaf De volledige of complete graaf met knopen is de graaf waarin elke knoop met elke andere knoop verbonden is.
De volgende grafen zijn voorbeelden van volledige grafen:
70px 70px 70px 70px 70px 70px 70px 70px
De volledige grafen .
Het aantal zijden van is , het -ste driehoeksgetal.
Een clique of kliek is een deelverzameling knopen waarin elke knoop verbonden is met alle andere knopen in die deelverzameling. Samen met de zijden waarmee ze verbonden zijn, vormen ze een volledige graaf.
Euler en Hamilton De wiskundige Leonhard Euler heeft zich onder meer beziggehouden met het probleem van de zeven bruggen van Koningsbergen. Dit probleem komt neer op de vraag of het mogelijk is in een samenhangende graaf, zoals bij de zeven bruggen, een wandeling te vinden waarin alle zijden één keer voorkomen. Zo'n wandeling heet een eulerwandeling. Het is ook de vraag dat een dergelijke wandeling bestaat zodat deze begint en eindigt in dezelfde knoop, dat heet een eulercykel. Een eulergraaf is een graaf met een eulercykel. Euler heeft dit probleem in 1736 opgelost. Wat betreft het tweede probleem bewees hij het volgende:
Een samenhangende graaf bevat dan en slechts dan een eulercykel als de graad van alle knopen even is.
|width="120px"| 100px |width="120px"| 100px |width="120px"| 100px |- | colspan="3" align="center" | en de "zeven bruggen"
De grafen en bevatten beide eulercykels. De graaf die het probleem van de zeven bruggen voorstelt, bevat geen eulercykel.
De voorwaarde voor een eulerwandeling is iets minder streng.
Een samenhangende graaf bevat een eulerwandeling dan en slechts dan als de graad van alle knopen, eventueel op twee na, even is.