Grafentheorie

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 $G=(V,E)$ is een geordend paar, waarin $V$ een willekeurige verzameling is en waarin $E$ een multiset bestaande uit multisets van twee al dan niet verschillende elementen uit $V$. De elementen van $V$ heten de knopen van de graaf $G$ en de elementen van $E$ heten de zijden van $G$. De knopen die een zijde vormen, heten de eindpunten van de zijde.

Ter verduidelijking schrijft men ook

$V_G\text{ of }V(G)$ voor de knopen van $G$

$E_G\text{ of }E(G)$ voor de zijden van $G$

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 $G$ voor een graaf betekent meestal dat $G$ willekeurig kan worden gekozen.
• De elementen van $V_G$ heten de knopen of punten van de graaf. $V_G$ kan ook als $V(G)$ worden genoteerd.
• De elementen van $E_G$ heten de zijden, lijnen, kanten, bogen of takken van de graaf. $E_G$ kan ook als $E(G)$ worden genoteerd.
• Twee knopen heten met elkaar verbonden als er een zijde tussen hen is. Deze knopen zijn dan adjacent.
• Men noteert $v_1\sim v_2$ als de twee knopen $v_1$ en $v_2$ met elkaar zijn verbonden.
• Als de knoop $v$ een begin- of eindpunt is van de zijde $e$, heet $v$ verbonden met $e$.
• Een lus is een zijde die een knoop met zichzelf verbindt.
• Een wandeling tussen twee knopen $a$ en $b$ is een rij verbonden knopen, waarvan $a$ het begin en $b$ het einde is. De rij van $n+1$ knopen $(v_0,\dots ,v_n)$ is dus een wandeling tussen $a$ en $b$, als

$a=v_0\sim v_1\sim \dots \sim v_n=b$, $n\ge 0$

• In een ongewogen graaf is de lengte van een wandeling het aantal zijden in de wandeling. Het aantal knopen was $n+1$, de lengte van de wandeling dus $n$.
• Een graaf heet samenhangend of transitief als er tussen elk paar knopen van de graaf een wandeling mogelijk is.
• Een pad tussen twee knopen $a$ en $b$ is een wandeling tussen $a$ en $b$ 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 $d(a,b)$ tussen twee knopen $a$ en $b$ is de lengte van het kortste pad tussen $a$ en $b$, tevens de lengte van de kortste wandeling tussen $a$ en $b$. Als er geen wandeling mogelijk tussen $a$ en $b,$ is de afstand tussen $a$ en $b$ ongedefinieerd.
• De diameter van een samenhangende graaf $G$ is de grootste afstand tussen twee knopen in $G$.
• 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 $\mathrm{d}\mathrm{e}\mathrm{g}(v)$ van een knoop $v$ is het aantal zijden waarmee $v$ verbonden is. Bij het bepalen van de graad telt een lus dubbel.
• Als alle knopen van een graaf dezelfde graad $g$ hebben, wordt de graaf $g$-regulier genoemd. Een graaf heet regulier als er een getal $g$ is, zo dat de graaf $g$-regulier is.
• Twee grafen $G_1$ en $G_2$ 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 $f:V(G_1)\to V(G_2)$ zodanig dat $(u,v)\in E(G_1)$ dan en slechts dan als $(f(u),f(v))\in E(G_2)$.
• De graaf $G_1$ heet een deelgraaf van de graaf $G_2,$ als de knopen en zijden van $G_1$ ook knopen en zijden van $G_2$ zijn, dus als $V(G_1)\subseteq V(G_2)$ en $E(G_1)\subseteq E(G_2)$.
• Een partitie van een graaf $G$ is een partitie van de verzameling knopen $V_G$ van $G$, 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

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

Graaf met twee componenten

Sjabloon:Zie hoofdartikel Binnen een enkelvoudige ongerichte graaf $G$ is een component van $G$ een deelgraaf $C=(V_C,E_C)$ waarbij tussen elk tweetal knopen van $C$ 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 $n\times n$, waarin $n$ het aantal knopen in de graaf is. Het element $a_{st}$ op rij $s$ en kolom $t$ in de bogenmatrix $A$ is 1 als er een zijde (boog) bestaat die van $s$ naar $t$ 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.

Gelabelde graaf	Bogenmatrix
	$\left(\begin{array}{cccccc}1& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right)$

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 $A$ tot de macht $n$ te verheffen, kan men in de kolom $t$ op rij $s$ aflezen hoeveel wandelingen er zijn van lengte $n$ van knoop $s$ naar knoop $t$.

In het bovenstaande voorbeeld is

$A^2=\left(\begin{array}{cccccc}3& 2& 1& 1& 2& 0\\ 2& 3& 0& 2& 1& 0\\ 1& 0& 2& 0& 2& 1\\ 1& 2& 0& 3& 0& 0\\ 2& 1& 2& 0& 3& 1\\ 0& 0& 1& 0& 1& 1\end{array}\right)\mathrm{e}\mathrm{n}{A}^3=\left(\begin{array}{cccccc}7& 6& 3& 3& 6& 1\\ 6& 3& 5& 1& 7& 2\\ 3& 5& 0& 5& 1& 0\\ 3& 1& 5& 0& 6& \mathrm{𝟑}\\ 6& 7& 1& 6& 3& 0\\ 1& 2& 0& 3& 0& 0\end{array}\right)$

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 $B$ 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 $B-A$ 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 $p$ het aantal zijden in de graaf, dan is de incidentiematrix een $n\times p$-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 $V_B$ heeft dus $|V_B|-1$ zijden.

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

Cykelgraaf $C_6$

De cykelgraaf $C_n$ met $n$ knopen is de enkelvoudige, samenhangende graaf met $n$ 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 $K_3$. 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 graaf $K_n$ met $n$ knopen is de graaf waarin elke knoop met elke andere knoop verbonden is.

De volgende grafen zijn voorbeelden van volledige grafen:

De volledige grafen $K_1...K_8$.

Het aantal zijden van $K_n$ is $\frac{1}{2}n(n-1)$, het $(n-1)$-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.

$K_3,K_5$ en de "zeven bruggen"

Sjabloon:Clearall De grafen $K_3$ en $K_5$ 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.

Behalve de eulercykels en -wandelingen is er nog een variant: de cykel en de wandeling, waarin iedere knoop één keer voorkomt. Dit zijn de hamiltoncykel en hamiltonwandeling. Deze variant is bedacht door William Hamilton. Er bestaat geen karakteristiek van grafen die een hamiltoncykel bevatten. De wiskundige Øystein Ore bewees wel de volgende stelling: De graaf $G$ bevat een hamiltoncykel als de som van de graden van elk tweetal niet-verbonden knopen samen groter is dan het aantal knopen van de graaf.

Over het algemeen is het vinden van een hamiltoncykel in een graaf een NP-volledig probleem; dit in tegenstelling tot het zoeken naar een eulercykel dat in polynomiale tijd kan worden opgelost dankzij de bovengenoemde regels. Een hamiltoncykel is een eenvoudig geval van het handelsreizigersprobleem. Bij dit probleem worden ook afstanden aan de verbindingen tussen de knopen of plaatsen toegevoegd en is het de opdracht de kortste rondreis te bepalen.

Overige grafen

Bipartiete graaf

Bipartiete graaf

Een bipartiete graaf $G$ is een graaf waarvan de knopen verdeeld zijn over een partitie $U,V$ met de eigenschap dat een knoop in de ene partitie alleen verbonden is met knopen in de andere partitie.

$V_G=U\cup V$

$U\cap V=\varnothing$

$u\in U\text{ en }u\sim v$, dan $v\in V$

Hierbij is het ook toegestaan dat een van beide partities leeg is, of zelfs allebei, zodat ook een graaf op 0 of 1 knoop bipartiet is.

De volledige bipartiete graaf met $n$ knopen in $U$ en $m$ knopen in $V$, waarin alle knopen in $U$ met alle knopen in $V$ verbonden zijn, wordt genoteerd als $K_{n,m}$.

Eveneens is duidelijk dat $C_3$ de kleinste, niet-bipartiete graaf is. Met dit inzicht valt ook goed in te zien dat een graaf niet-bipartiet is, als deze een cykel van oneven lengte bevat. Met name geldt voor alle grafen $C_{2n+1}$ dat deze niet bipartiet zijn, sterker nog:

Een graaf $G$ is bipartiet $\iff$ $G$ bevat geen oneven cykels Sjabloon:Uitklappen

Er zijn ook $k$-partiete grafen, waarbij de graaf wordt opgesplitst in $k$ partities waarvoor er wederom geen lijnen zijn tussen punten in dezelfde partitie. Voor $k=2$ heb je weer de bipartiete graaf.

Planaire graaf

Planaire of vlakke grafen zijn grafen die op een plat vlak kunnen worden getekend zonder dat de zijden van de graaf elkaar snijden.

De grafen $K_3$, $K_5$ en $K_{3,3}$
$K_3$ is planair, $K_5$ is niet planair

Dergelijke grafen zijn van belang bij de modellering van zaken als pijpleidingen en printplaten voor elektronica, waar de verbindingen geen contact mogen maken. Wat dat eerste betreft zijn planaire grafen dan ook bij het grotere publiek bekend in de vorm van puzzeltjes zoals "probeer drie huizen aan te sluiten op de gas-, water- en elektra-bronnen, zonder dat enige van de leidingen elkaar snijden". Dit is in feite de vraag of $K_{3,3}$ planair is.

Ook over planaire grafen heeft Leonhard Euler nagedacht en hij vond de stelling van Euler. Deze stelling is gebaseerd op het aantal knopen, zijden en gebieden van een graaf. Een gebied van een graaf is een deel van de graaf dat geheel door zijden of door buitenste knopen van de graaf wordt omgeven. Men kan een gebied zien als een gedeelte van het papier waarop de graaf is getekend. Het aantal gebieden hangt ervan af hoe de graaf precies getekend wordt, maar het blijkt dat een bepaalde graaf altijd met een aantal gebieden kan worden getekend dat niet verandert, hoe de graaf ook precies is getekend, behalve als de graaf niet-planair is getekend.

Stelling van Euler

Zij $G$ een samenhangende, planaire graaf met $v$ knopen, $e$ zijden en $f$ gebieden. Dan geldt

$v-e+f=2$

Met de stelling van Euler kan aangetoond worden dat een samenhangende graaf alleen planair kan zijn als hij niet al te veel zijden heeft.

Zij $G$ een samenhangende, planaire graaf met $v\ge 3$ knopen en $e$ zijden. Dan geldt

$e\le 3v-6$

Met deze informatie in de hand, kunnen we zo narekenen dat bijvoorbeeld $K_5$ niet planair is.

Op een soortgelijke manier als hierboven, kunnen we ook bewijzen voor samenhangende planaire grafen zonder driehoeken, dus met het "kleinste" gebied een vierhoek, dat $e\le 2v-4$. Hiermee is ook het puzzeltje opgelost: $K_{3,3}$ is niet planair.

Volgens de stelling van Kuratowski is een graaf $G$ planair dan en slechts dan als er in $G$ geen subgrafen voorkomen die isomorf zijn met een subdivisie van $K_5$ of $K_{3,3}$. Kazimierz Kuratowski heeft de stelling in 1930 bewezen. De wiskundige Karl Menger heeft ook in 1930 een soortgelijke stelling bewezen voor grafen waarin alle knopen de orde drie hebben. Het is in dat geval een nodige en voldoende voorwaarde dat er in $G$ geen subgraaf voorkomt die isomorf is met een subdivisie van $K_{3,3}$.

Petersengraaf

Petersengraaf

De volgende graaf staat bekend als de Petersengraaf, gedefinieerd door de Deense wiskundige Petersen.

Op zich is er niets speciaals mee aan de hand; de Petersengraaf komt echter binnen de grafentheorie vaak voor, als voorbeeld bij bewijzen of als tegenvoorbeeld om stellingen mee te ontkrachten. De Petersengraaf wordt dan vaak gebruikt als deelgraaf van een andere, meer complexe graaf.

De Petersengraaf bevat een subdivisie van $K_{3,3}$. Hij heeft ook $K_5$ als minor: als we de buitenste "ring" van knopen en de binnenste "ring" samentrekken, vinden we de $K_5$-graaf. We kunnen dan ook duidelijk zien dat de Petersengraaf niet planair is.

Graafoperaties, de 2-graaf en geïnduceerde grafen

De rechter graaf is een geïnduceerde subgraaf op de linker.

Uitgaande van een graaf $G$ (of een aantal verschillende grafen) kunnen we, via allerlei operaties, andere grafen maken.

Om te beginnen is er de op $G$ geïnduceerde graaf $G^{\prime }.$ Deze graaf is gedefinieerd door:

$G^{\prime }=(V^{\prime },E^{\prime })$

met

$V^{\prime }\subseteq V_G$

en zo dat voor alle knopen $v_1,v_2\in V^{\prime }$ geldt

$\{v_1,v_2\}\in E_G\Rightarrow \{v_1,v_2\}\in E^{\prime }$

De door $G$ geïnduceerde graaf $G^{\prime }$ is de graaf bestaande uit een aantal knopen van $G$ en de bijbehorende zijden van $G$.

Graaf met complementgraaf

Daarnaast is er de complementgraaf of complementaire graaf $\bar{G}$ van $G,$ gedefinieerd door:

$\bar{G}=(V_{\bar{G}},E_{\bar{G}})$

met

$V_{\bar{G}}=V_G$

en zo dat voor alle knopen $v_1,v_2\in V^{\prime },v_1\ne v_2$ geldt

$\{v_1,v_2\}\in ̸E_G\Rightarrow \{v_1,v_2\}\in E_{\bar{G}}$

De complementgraaf $\bar{G}$ van $G$ heeft dus dezelfde knopen als $G$, maar alle mogelijke zijden die juist niet in $G$ zitten.

Graaf met bijbehorende lijngraaf

Ook is er de lijngraaf $L(G)=(V_L,E_L)$ van $G$, die de zijden van $G$ als knopen heeft. De knopen van $L(G)$ worden verbonden door een zijde, als de oorspronkelijke zijden van $G$ - bij $\bar{G}$ knopen - een knoop gemeen hebben.

Deze graaf is gedefinieerd door:

$V_L=E(G)$

$\{\{v_1,v_2\},\{{v_1}^{\prime },{v_2}^{\prime }\}\}\in E_L$ als

$v_1={v_1}^{\prime }\text{ of }{v}_1={v_2}^{\prime }\text{ of }{v}_2={v_1}^{\prime }\text{ of }{v}_2={v_2}^{\prime }$

Vereniging van twee disjuncte grafen

Voor twee grafen $G$ die geen knopen of zijden gemeen hebben, kan ook de vereniging en het cartesisch product gedefinieerd worden. De vereniging van $G$ en $H$ is de graaf $G\cup H$ met

$V(G\cup H)=V(G)\cup V(H)$

$E(G\cup H)=E(G)\cup E(H)$

Cartesisch product van twee grafen

Het cartesisch product van $G$ en $H$ is de graaf $G\times H$ met als knopen de paren van knopen van $G$ en $H$ en twee dergelijke knopen zijn verbonden door een zijde als een van de knopen in de twee paren dezelfde zijn en de andere verbonden waren. De vereniging is dus gedefinieerd door:

$V(G\times H)=V(G)\times V(H)$

$\{(g,h),(g^{\prime },h^{\prime })\}\in E(G\times H)$ als

$(g=g^{\prime }\text{ en }h\sim h^{\prime })\text{ of }(g\sim g^{\prime }\text{ en }h=h^{\prime })$

vlnr $K_2^0,K_2^1,K_2^2$ en $K_2^3$

Een bekend voorbeeld van graaf-vermenigvuldiging is de rij van de 'machten' van de 2-graaf $K_2$: dit zijn de $n$-dimensionale kubussen hier rechts.

Gerichte grafen

Gerichte graaf

Een type graaf die naast de enkelvoudige graaf vaak voorkomt, is de gerichte graaf. Formeel is een gerichte graaf een graaf $G=(V,E)$ met

$E\subseteq \{(v_1,v_2)\mid v_1,v_2\in V,v_1=v_2\}$

Het verschil met de enkelvoudige graaf is dat de zijden niet langer ongeordende paren zijn, maar juist geordende paren (intuïtief wil dat zeggen: de zijden hebben een richting). Merk op dat in de bovenstaande definitie een zijde een geordend paar is en niet een verzameling. Dit betekent dat de zijde $(a,b)$ niet dezelfde is als de zijde $(b,a)$.

Vanwege de richting is het normaal om bij een gerichte graaf de zijden als pijlen te tekenen.

Veel van de concepten zoals die gedefinieerd zijn voor enkelvoudige grafen, bestaan ook voor gerichte grafen. Bomen, volledige grafen, somgrafen en productgrafen bestaan allemaal. Alleen is de uitwerking soms anders, omdat de richting nu meespeelt. Zo is het bij enkelvoudige grafen zo dat er voor iedere knoop zijde $k$ maar één pad is van de wortel naar $k$; bij een gerichte graaf kunnen er meerdere zijn, zonder dat dit een cykel oplevert.

Gerichte grafen worden vaak toegepast in de modellering van problemen waarbij het niet zinnig is om paden in meer dan één richting te doorlopen. Gebruik je bijvoorbeeld een graaf om aan tijdsplanning te doen voor de bouw van een woning, dan heeft het alleen zin om de bouw van de fundering voor de bouw van de muren plaats te laten vinden en andersom heeft geen zin.

Enige verschillen ten opzichte van enkelvoudige grafen

Er zijn een aantal typische dingen die anders zijn in gerichte grafen in vergelijking met enkelvoudige grafen. Graad heeft bijvoorbeeld een andere betekenis. De graad van een knoop is in een enkelvoudige graaf het aantal zijden waarmee de knoop verbonden is; in een gerichte graaf is de definitie iets anders:

• ingraad van een knoop $k$: het aantal zijden $(m,k)\in E$
• uitgraad van een knoop $k$: het aantal zijden $(k,n)\in E$

Een gerichte graaf bevat dan en slechts dan een eulerwandeling als voor alle knopen in de graaf de in- en uitgraad aan elkaar gelijk zijn. Het bewijs hiervoor is vrijwel hetzelfde als dat voor de enkelvoudige eulergraaf.

Een gerichte graaf heet samenhangend als er voor iedere partitie $V=V_1\cup V_2$ een zijde loopt van $V_1$ naar $V_2$ of omgekeerd. Loopt er altijd een dergelijke zijde in beide richtingen, dat wil zeggen als er tussen iedere twee knopen een wandeling is in beide richtingen, dan heet de graaf sterk samenhangend.

Gelabelde en gewogen grafen

Een andere uitbreiding op de enkelvoudige graaf die vaak voorkomt is die van labeling. Hierbij wordt de graaf $G$ uitgebreid met een of twee functies $f$ en $g:$

$f:E(G)\to A$

$g:V(G)\to B$

De functies $f$ voegt aan iedere zijde, en de functie $g$ aan iedere knoop een element toe uit een of andere verzameling symbolen. Het labelen van de zijden komt meer voor dan labelen van de knopen.

Als de symbolen getallen zijn ($\mathbb{N},\mathbb{Z},\mathbb{Q},ℝ,ℂ$, etc.), noemen we de labeling een weging. De graaf heet dan een gewogen graaf. Een gewogen, gerichte graaf wordt ook wel een netwerk genoemd.

Labeling en met name weging worden gebruikt om aan een graaf speciale betekenissen toe te kennen. Wordt een graaf gebruikt als model voor een wegennet bij routeplanning, dan kan bij een weging bijvoorbeeld gedacht worden aan de lengte van de weg, of de drukte. Optimaliseringsproblemen op grafen gebruiken meestal weging als criterium aan de hand waarvan wordt geoptimaliseerd.

Het aantal gelabelde bomen op $v$ knopen is $v^{v-2}$

Hypergrafen

Hypergrafen zijn een veralgemening van grafen, in zoverre dat in een hypergraaf een hyperzijde een willekeurig aantal knopen kan verbinden, gaande van 1 tot het aantal knopen in de graaf.

Problemen op grafen

• Kleuren van grafen
  • vierkleurenstelling
• Routeproblemen:
  • Zeven bruggen van Koningsbergen
  • Minimaal opspannende boom
  • Kortstepadprobleem
  • Chinees postbodeprobleem
  • Handelsreizigersprobleem
• Stromen:
  • Max-flow-min-cut-stelling

Belangrijke algoritmes op grafen

• Dijkstra's algoritme
• Kruskals algoritme
• Prims algoritme
• Hongaarse methode
• Algoritme van Bellman-Ford

Gerelateerde wiskundige gebieden

• Ramsey-theorie
• Combinatoriek
• Complexe netwerken

Websites

• MathWorld. Graph Theory. Engelse literatuurlijst
• J-T Tevet. Fundamentals of structural treatment of the graphs Sjabloon:Pdf