(Fr.: théorie des graphes; Du.: Theorie der Graphen; Eng.: graph theory), tak van de wiskunde, ontstaan in 1736 toen de wiskundige L.Euler een artikel publiceerde waarin hij het zgn. Königsberger bruggenprobleem oploste;
ongeveer honderd jaar later paste de natuurkundige G.R. Kirchhoff de ‘theorie van de bomen’ toe op een probleem uit de netwerktheorie; in 1847 gebruikte de wiskundige A. Cayley het begrip boom bij het tellen van isomeren van verzadigde alcoholen. De eigenlijke ontwikkeling van de grafentheorie begint echter eerst in de jaren twintig van deze eeuw. Thans is de grafentheorie een belangrijk onderdeel van de zuivere wiskunde dat wordt toegepast in o.a. de topologie, combinatorische wiskunde, operationele analyse, besliskunde, informatica, de natuurkunde, de technische en de sociale wetenschappen.
Definities (afb. 1). Een graaf G is een geordend paar < K(G), T(G) >; hierin is K(G) een eindige verzameling knooppunten van G, en T(G) een eindige verzameling takken van G; aan iedere tak t ∈ T(G) voegt men een verzameling {u, v} toe: (u,v ∈ K(G)). G is een gerichte graaf ofwel digraaf als aan iedere t ∈ T(G) een geordend paar knooppunten (u,v) toegevoegd is. De knooppunten, toegevoegd aan de tak, noemt men incident met t; zij zijn de eindpunten van de verbindingstak en kunnen verscheidene verbindingstakken of meervoudige verbindingen hebben; bovendien kan een knooppunt een verbinding met zichzelf (lus) bezitten. In een digraaf noemt men de takken t en t' parallel als aan beide het gerichte paar (u, v) toegevoegd is. Een (di)graaf is enkelvoudig als zij geen meervoudige takken of lussen bevat; in dit geval identificeert men de takken vaak met {u, v} of met (u, v). Een (di)graaf is gewogen als men aan de knooppunten of aan de takken elementen uit een gegeven verzameling L toevoegt. Een graaf G kan meetkundig gerepresenteerd worden in het euclidische vlak door de knooppunten van G te tekenen als punten en de tak t, waaraan toegevoegd {u, v}, als een verbindingslijn van de met u en v overeenkomstige punten; in het geval G een digraaf is, geeft men de verbinding die correspondeert met de tak t, waaraan toegevoegd (u, v), de richting ‘van u naar v’.
Een (di)graaf is planair als er een meetkundige representatie bestaat waarvan de takken elkaar alleen snijden in de knooppunten; een (di)graaf G' is een deel(di)graaf van de (di)graaf G als alle knooppunten en takken van G' tevens knooppunten en takken van G zijn. Een graaf G is volledig als ze enkelvoudig is en elk tweetal knooppunten van G incident is. De valentie d(v) van een knooppunt v is gelijk aan het aantal takken dat incident is met v (lussen worden dubbel geteld!). De plusvalentie d+(v) van een knooppunt van een digraaf is gelijk aan het aantal takken t met (u, v); de minvalentie d− (v) van een knooppunt van een digraaf is gelijk aan het aantal takken t met (v, w). Een graaf is regulier als alle knooppunten dezelfde valentie bezitten.
Een (di)graaf kan op verschillende manieren met een matrix gerepresenteerd worden. Voor bijv. de incidentiematrix van een enkelvoudige graaf G nummert men de knooppunten in K(G) van 1 tot en met n; de elementen aij van deze n × n-matrix zijn dan als volgt gedefinieerd:
aij = 1 als de knooppunten vi en vj incident zijn,
aij = 0 als vi en vj niet incident zijn.
Voorbeelden.
Het Königsberger bruggenprobleem (afb. 2): twee eilanden in de rivier de Pregel in Königsberg (thans Kaliningrad) zijn door zeven bruggen met elkaar en de beide oevers verbonden. Is het mogelijk een wandeling te maken die start in A, B, C of D, alle bruggen één keer passeert en in het startpunt eindigt? Hierna zal blijken dat dit probleem onoplosbaar is. In het utiliteitsprobleem moeten drie huizen H1 , H2 en H3 elk afzonderlijk aangesloten worden op het gas-, water- en elektriciteitsnet (G, W en E) zonder dat de aansluitingen elkaar kruisen (afb. 3). Men kan bewijzen dat de graaf K5 geen planaire representatie bezit: er is geen stel verbindingen mogelijk dat aan de eis voldoet.
Voor andere voorbeelden zie afb. 4.
Paden, wegen en circuits.
Een weg in een graaf G is een eindige rij knooppunten u0, u1, ..., un, n > 0 en ui ∈ K(G), waarvan elk paar opeenvolgende termen incident is; u0 en un zijn de eindpunten. Bij een gesloten weg zijn de eindpunten gelijk, bij een open weg verschillend. Bij een pad zijn alle knooppunten verschillend; bij een circuit zijn de eindpunten gelijk en de overige knooppunten twee aan twee verschillend. Een graaf G is samenhangend als elk paar knooppunten door een weg verbonden is. Een niet-samenhangende graaf bestaat uit twee of meer samenhangende deelgrafen of componenten. Een bekend probleem is de vraag of een samenhangende graaf G een gesloten weg bezit die elke tak van G precies één keer bevat; een dergelijke lijn noemt men een eulerlijn. Een samenhangende graaf G blijkt dan en slechts dan een eulerlijn te bevatten als elk knooppunt van G een even valentie heeft. Hieruit volgt dat het Königsberger bruggenprobleem onoplosbaar is. Voor digrafen kan een analoog resultaat bewezen worden.
In 1859 werd door Sir William Rowan Hamilton de vraag gesteld of een samenhangende graaf G een circuit heeft dat elk knooppunt van G precies één keer bevat (hamiltoncircuit). Tot op heden is niet bekend onder welke voorwaarden een samenhangende graaf een dergelijk circuit heeft. Een bekende voldoende voorwaarde van Dirac luidt: een samenhangende graaf met n knooppunten (n > 0) heeft een hamiltoncircuit als de valentie van elk knooppunt minstens ½n is.
Het probleem van de ‘travelling salesman’ is nauw verwant met het zoeken naar hamiltoncircuits. Een vertegenwoordiger moet een aantal steden bezoeken; als de afstanden daartussen gegeven zijn, is de vraag welke de kortste route is waarlangs alle steden één keer worden aangedaan die eindigt in het uitgangspunt. Dit probleem kan gerepresenteerd worden door een volledige gewogen graaf; de knooppunten zijn de steden, de takken de wegen daartussen en de gewichten van de takken de afstanden.
Het totale aantal verschillende hamiltoncircuits is gelijk aan ½(n−1)!. Als men nu van elk hamiltoncircuit de lengte berekent, is hiermede het probleem opgelost. Deze methode is voor grotere waarden van n onbruikbaar. Thans zijn er diverse efficiënte algoritmen voor de oplossing van het probleem van de travelling salesman bekend; geen enkele is echter efficiënt voor willekeurig grote n.
Een ander probleem is het plannen van activiteiten. Een bouwproject bijv. bestaat uit een aantal deelactiviteiten A0, A1,..., An die elk een tijdvak li duren (i = 0, 1,..., n). Het project start met A0 en eindigt met An; sommige activiteiten Ai kunnen pas een tijdvak ki na de start van A0 beginnen, andere activiteiten Aj pas een tijdvak mij na de start van Ai. Het verloop en de samenhang van de activiteiten kunnen worden weergegeven door middel van een digraaf of een planningsnetwerk (afb. 5). De kortst mogelijke termijn waarop het project na de start op het tijdstip t = t0 gereed kan zijn, wordt berekend door de langste weg in het planningsnetwerk te bepalen. Een bekende methode voor de berekening van de lengte van de langste weg is de metra-potentialmethode (MPM).
Doorgaans zijn ki , mij en li niet exact bekend; dan kan men ook stochastische modellen gebruiken, bijv. programme evaluation and review technique (PERT).
Bomen.
Een boom is een samenhangende graaf zonder circuits; een woud een graaf waarvan de componenten bomen zijn. Men kan bewijzen dat een graaf G met n knooppunten dan en slechts dan een boom is als G samenhangend is en precies n − 1 takken heeft, óf als G geen circuits heeft en n − 1 takken bevat, óf als elke twee knooppunten door één pad zijn verbonden. Uit het voorgaande volgt dat een woud met n knooppunten en k componenten precies n − k takken bevat.
Een skelet van een samenhangende graaf G is een boom die alle knooppunten van G bevat. Hieruit volgt dat men een skelet van G kan construeren door van elk circuit een tak te verwijderen; de zo verkregen deelgraaf van G is een skelet van G. Via het begrip ‘skelet’ kan men interessante verbanden leggen tussen grafen, vectorruimten en matrixrepresentaties van grafen. Toepassingen van deze theorie zijn o.a. te vinden in de coderingstheorie.
Een samenhangende graaf G kan men door de verwijdering van een voldoend aantal takken doen uiteenvallen in twee componenten; een dergelijke verzameling takken heet een scheidende verzameling (van G). Een snede (van G) is een scheidende verzameling waarvan elke echte deelverzameling geen scheidende verzameling is. Een maat voor de samenhang van G is het minimale aantal takken dat een snede van G kan bevatten; dit getal noemt men de taksamenhang van G.
De eigenschappen van sneden kunnen bijv. van belang zijn bij de aanleg van een communicatienetwerk tussen n stations met m lijnen (m > n − 1) waarbij bovendien wordt geëist dat het netwerk weinig kwetsbaar is ten opzichte van draadbreuken. Dit probleem is opgelost als men er in slaagt een graaf te construeren met n knooppunten, m takken en met een zo groot mogelijke taksamenhang.
Tellen van bomen.
De grafentheoretische telproblemen omvatten:
1. het tellen van het aantal grafen van een bepaalde soort, bijv. het aantal samenhangende grafen met n knooppunten en m takken;
2. het tellen van het aantal deelgrafen met bepaalde eigenschappen van een gegeven graaf G, bijv. het aantal skeletten van een gegeven samenhangende graaf.
De berekening van het aantal verschillende gelabelde bomen met n > 2 knooppunten is een voorbeeld van een telprobleem van de eerstgenoemde soort; Cayley bewees dat er nn−2 van zulke bomen bestaan. Hieruit volgt direct dat er nn−1 verschillende gelabelde wortelbomen (bomen waarvan één knooppunt gemarkeerd is als wortel) met n knooppunten bestaan. Het tellen van ongelabelde bomen is doorgaans moeilijker.
De stelling van Kirchhoff die een formule geeft voor het aantal skeletten van een gegeven samenhangende graaf, is een resultaat dat tot de 2de categorie behoort.
Planairiteit van grafen.
Voor de oplossing van praktische problemen is het vaak van belang te weten of een gegeven graaf planair is, bijv. bij het ontwerpen van gedrukte elektronische schakelingen. De algoritmen waarmee men de planairiteit onderzoekt gaan doorgaans uit van een meetkundige representatie van een planaire deelgraaf van G, waarmee men tracht deze aan te vullen tot een meetkundige representatie van G, waarvan de takken elkaar slechts snijden in de knooppunten. Voorbeelden van niet-planaire grafen zijn die van Kuratowski K5 en K3,3 (afb. 3 en 6). Twee grafen zijn homeomorf als zij isomorf (afb. 1) zijn of als zij beide ontstaan zijn uit een gegeven graaf door op de takken knooppunten van valentie twee te plaatsen. Het planairiteitscriterium van Kuratowski luidt: een graaf G is dan en slechts dan planair als G geen deelgraaf bevat die homeomorf is met K5 of K3,3. Alhoewel dit resultaat zeer fraai is, is het totaal ongeschikt om hiermede met behulp van een rekenautomaat de planairiteit van een gegeven graaf te testen.
Het kleuren van grafen.
Een samenhangende enkelvoudige graaf G is k-kleurbaar, als men aan elk knooppunt van G één van de gegeven k verschillende kleuren kan toevoegen én twee naburige knooppunten verschillende kleuren hebben; een realisatie van zo’n toevoeging noemen we een k-kleuring. G is k-chromatisch als G k-kleurbaar is, maar niet (k − 1)-kleurbaar; in dit geval is k het chromatische getal van G. Het beroemde vierkleurenprobleem, dat tot op heden niet is opgelost, luidt: iedere planaire samenhangende enkelvoudige graaf is 4-kleurbaar. Van een groot aantal speciale gevallen is echter de oplossing bekend; bijv. iedere planaire samenhangende enkelvoudige graaf met minder dan 40 knooppunten is 4-kleurbaar. Het vierkleurenprobleem is ontstaan als het kleuren van een willekeurige geografische kaart met vier kleuren, zodanig dat twee nabuurlanden een verschillende kleur hebben. Beschouwt men nu een kaart als een meetkundige representatie van een planaire enkelvoudige samenhangende graaf, dan heeft men zo de grafentheoretische vorm van dit probleem verkregen.
Men kan bewijzen dat de beide grafentheoretische versies van het vierkleurenprobleem equivalent zijn.
Een toepassing van het kleuren van grafen is het opstellen van een collegerooster waarvan sommige colleges niet mogen samenvallen, omdat zij bestemd zijn voor dezelfde studenten. Voor de oplossing hiervan construeert men een graaf waarvan de knooppunten de colleges voorstellen; de takken verbinden de knooppunten van colleges die niet tegelijkertijd gegeven mogen worden. Met elk van de k tijdvakken waarin een college gegeven kan worden, associeert men een kleur; de k kleuren zijn onderling verschillend. Een k-kleuring van de knooppunten correspondeert nu met een college-indeling die aan de eisen voldoet.
Stromingsproblemen op digrafen.
Een uv-pad in de samenhangende (di)graaf G is een (gericht) pad dat de knooppunten u en v van G verbindt; twee uv-paden zijn (tak)knooppuntdisjunct als zij geen enkel (tak)knooppunt gemeen hebben.
Een uv-scheidende verzameling van de samenhangende graaf G is een scheidende verzameling van G, die met ieder uv-pad één tak gemeen heeft; een uv-scheidende verzameling is minimaal als zij geen echte deelverzameling bevat, die tevens een uv-scheidende verzameling is.
In een samenhangende graaf G is het maximale aantal takdisjuncte uv-paden (u en v zijn verschillende knooppunten van G) gelijk aan het aantal takken van de minimale scheidende verzameling van G. Dit resultaat staat bekend als de ‘takvorm’ van de stelling van Menger. Een gevolg van deze stelling is de oplossing van het zgn. marriageprobleem. Dit luidt: gegeven zijn een eindige verzameling jongens en meisjes; onder welke voorwaarde kan men elke jongen uithuwelijken aan een meisje dat hij kent? Een noodzakelijke en voldoende voorwaarde hiervoor (stelling van Hall) is dat iedere deelverzameling van k jongens als collectief ten minste k (verschillende) meisjes kent. De stelling van Hall heeft interessante toepassingen bij de constructie van Latijnse vierkanten, het samenstellen van lesroosters, de theorie van 0,1-matrices en de transversalentheorie.
Stelling van Ford-Fulkerson.
In de huidige samenleving kent men diverse realisaties van netwerken: een spoorwegnet, het telefoonnet, de netwerken voor elektriciteits- en watervoorziening. Uitgaande van deze situaties kan men een netwerk N definiëren als een geordend paar N = < G, 𝜓 >; G is een enkelvoudige samenhangende digraaf en 𝜓: T(G) ↦ ℝ een functie met de eigenschap 𝜓(t) ≧ 0 voor alle t ∈ T(G); 𝜓(t) is de capaciteit van tak t.
De uitgraad d(→)(v) van een knooppunt v van het netwerk N is de som van de capaciteiten van de takken (v, u); de ingraad d(←)(v) van een knooppunt van het netwerk N is de som van de capaciteiten van de takken (w, v).
Een bron is een knooppunt v van N, waarin geldt d(←)(v) = 0; een put een knooppunt w, waarin geldt d(→)(w) = 0.
Een stroom Φ in een netwerk < G, 𝜓 > is een functie Φ: T(G) ↦ ℝ met de eigenschappen:
0 ≦ Φ(t) ≦ 𝜓(t) voor alle t ∈ T(G); voor het netwerk < G, φ > geldt in alle knooppunten u ∈ K(G): d(→)(u) = d(←)(u) behalve in v en w (de laatste voorwaarde staat bekend als de 2de wet van Kirchhoff).
Een eenvoudige overweging leert dat de som van de stromen in de takken incident met de bron v gelijk moet zijn aan de som van stromen in de takken incident met de put w; de waarde van deze som noemt men de grootte van de stroom Φ in het netwerk N.
De studie van de maximale stroom in een netwerk N is nauw verbonden met het begrip snede. Een snede van een netwerk N is een vw-scheidende verzameling van G; de capaciteit van een snede is de som der capaciteiten van de takken behorend tot deze snede. De maximale stroom in een netwerk kan nooit groter zijn dan de capaciteit van een minimale snede (snede met zo klein mogelijke capaciteit). Minder evident is dat deze twee grootheden aan elkaar gelijk zijn, zoals bewezen is door Ford en Fulkerson in 1955 (max-flow min-cut-stelling); Ford bewees dat deze stelling equivalent is met de stelling van Menger.