Een 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 of om een schematische routekaart te maken tussen een aantal plaatsen met de afstanden daartussen. Verschillende soorten grafen spelen in de informatica een rol, niet alleen in de vorm van boomstructuren, maar ook om dataverkeer 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; binnen de informatica is dit 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 of toppen (Engels: vertices) en een verzameling zijden, kanten, bogen of takken (Engels: edges) van paren knopen. Formeler:

Een graaf G=(V,E)displaystyle G=(V,E) is een geordend paar, waarin Vdisplaystyle V een willekeurige verzameling is en waarin Edisplaystyle E een verzameling is bestaande uit multisets van twee al dan niet verschillende elementen uit Vdisplaystyle V. De elementen van Vdisplaystyle V heten de knopen (of punten) van de graaf Gdisplaystyle G en de elementen van Edisplaystyle E heten de zijden (ook kanten, lijnen, bogen of takken) van Gdisplaystyle G. De knopen die een zijde vormen, heten de eindpunten van de zijde.

Ter verduidelijking schrijft men ook

VG of V(G)displaystyle V_Gtext of V(G) voor de knopen van Gdisplaystyle G

EG of E(G)displaystyle E_Gtext of E(G) voor de zijden van Gdisplaystyle G

Normaal wordt ervan uitgegaan dat een zijde twee verschillende knopen met elkaar verbindt of eventueel een lus is en bij dezelfde knoop terugkomt.

Een ruimer begrip graaf laat toe dat twee knopen door meer dan één zijde zijn verbonden: men spreekt van een multigraaf. De verzameling zijden Edisplaystyle E is dan een multiset van deelverzamelingen van Vdisplaystyle V met twee elementen. 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

• De elementen van VGdisplaystyle V_G heten de knopen of punten van de graaf Gdisplaystyle G.


• De elementen van EGdisplaystyle E_G heten de zijden, lijnen, kanten, bogen of takken van de graaf Gdisplaystyle G.


• Men noteert v1∼v2displaystyle v_1sim v_2 als de twee knopen v1displaystyle v_1 en v2displaystyle v_2 met elkaar zijn verbonden.


• Twee knopen heten met elkaar verbonden als er een zijde tussen hen is.


• Als de knoop vdisplaystyle v een begin- of eindpunt is van de zijde edisplaystyle e, heet vdisplaystyle v verbonden met edisplaystyle e.


• Een lus is een zijde die een knoop met zichzelf vebindt.


• Een wandeling tussen twee verbonden knopen adisplaystyle a en bdisplaystyle b is een rij verbonden knopen, waarvan adisplaystyle a het begin en bdisplaystyle b het einde is. De rij knopen (v1,…,vn)displaystyle (v_1,ldots ,v_n) is dus een wandeling tussen adisplaystyle a en bdisplaystyle b, als

a=v1∼v2∼…∼vn=bdisplaystyle a=v_1sim v_2sim ldots sim v_n=b

• In een ongewogen graaf is de lengte van een wandeling het aantal zijden in de wandeling (het aantal knopen min 1).


• Een graaf heet samenhangend, als er tussen elk paar knopen van de graaf een wandeling mogelijk is.


• Een pad tussen twee verbonden knopen adisplaystyle a en bdisplaystyle b is een wandeling tussen adisplaystyle a en bdisplaystyle b waarin geen knoop meer dan eenmaal voorkomt.


• De afstand d(a,b)displaystyle d(a,b) tussen twee knopen adisplaystyle a en bdisplaystyle b de lengte van het kortste pad tussen adisplaystyle a en bdisplaystyle b. Als er geen wandeling mogelijk tussen adisplaystyle a en b,displaystyle b, is de afstand tussen adisplaystyle a en bdisplaystyle b ongedefinieerd.


• De diameter van een samenhangende graaf Gdisplaystyle G is het maximum van de lengtes van de kortste paden tussen twee knopen in Gdisplaystyle G.


• Een cykel in een graaf is een pad met lengte groter dan nul van een knoop naar zichzelf.


• De taille van een samenhangende graaf is de lengte van de kortste cykel in de graaf.


• De graad deg(v)displaystyle mathrm deg (v) van een knoop vdisplaystyle v is het aantal zijden waarmee vdisplaystyle v verbonden is.


• Als alle knopen van een graaf dezelfde graad gdisplaystyle g hebben, wordt de graaf gdisplaystyle g-regulier genoemd. Een graaf heet regulier als er een getal gdisplaystyle g is, zo dat de graaf gdisplaystyle g-regulier is.


• Twee grafen G1displaystyle G_1 en G2displaystyle G_2 heten isomorf, als de ene graaf ontstaat uit de andere door slechts de namen van de knopen te veranderen. Meer formeel is er dan een bijectie f:V(G1)→V(G2)displaystyle f:V(G_1)to V(G_2) zodanig dat (u,v)∈E(G1)displaystyle (u,v)in E(G_1) dan en slechts dan als (f(u),f(v))∈E(G2)displaystyle (f(u),f(v))in E(G_2).


• De graaf G1displaystyle G_1 heet een deelgraaf van de graaf G2,displaystyle G_2, als de knopen en zijden van G1displaystyle G_1 ook knopen en zijden van G2displaystyle G_2 zijn, dus als V(G1)⊆V(G2)displaystyle V(G_1)subseteq V(G_2) en E(G1)⊆E(G2)displaystyle E(G_1)subseteq E(G_2).


• Een partitie van een graaf Gdisplaystyle G is een partitie van de verzameling knopen VGdisplaystyle V_G van Gdisplaystyle G, dus een disjuncte opdeling van de knopen.

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

Een graaf, die bestaat uit twee componenten.

Binnen een enkelvoudige ongerichte graaf Gdisplaystyle G is een component van Gdisplaystyle G een deelgraaf C=(VC,EC)displaystyle C=(V_C,E_C) waarvan alle knopen onderling verbonden zijn en niet verbonden met enige andere knoop. Dus:

VC⊆VGdisplaystyle V_Csubseteq V_G

als v,v′∈VCdisplaystyle v,v'in V_C, dan v∼v′displaystyle vsim v' en

voor alle v∈VC,v′∈VG∖VCdisplaystyle vin V_C,v'in V_Gsetminus V_C geldt: v≁v′displaystyle vnot sim v'

Een graaf die slechts 1 component heeft, en waarin dus een wandeling tussen elk paar punten bestaat, is daarmee een samenhangende graaf. Verder volgt dat de zijden van een graaf alleen tussen knopen in dezelfde component lopen, dus zijn de componenten van een graaf in het bijzonder samenhangende deelgrafen. Een enkelvoudige ongerichte graaf valt uiteen in onderling disjuncte componenten.

Matrixvoorstelling van een graaf

We kunnen een eindige graaf eenvoudig voorstellen in een matrix, de bogenmatrix. Dit is een vierkante matrix met dimensies n×ndisplaystyle ntimes n, waarin ndisplaystyle n het aantal knopen in de graaf is. Het element aijdisplaystyle a_ij in de bogenmatrix Adisplaystyle A is 1 als er een zijde (boog) bestaat die van idisplaystyle i naar jdisplaystyle j gaat en 0 als dit niet het geval is.

Gelabelde graaf	Bogenmatrix
	(110010101010010100001011110100000100)displaystyle beginpmatrix1&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\endpmatrix

Is de bogenmatrix opgesteld, dan kan deze worden gebruikt om af te lezen hoeveel paden er van een knoop naar een andere zijn. Door de bogenmatrix Adisplaystyle A tot de macht ndisplaystyle n te verheffen, kan men in de kolom sdisplaystyle s op rij tdisplaystyle t aflezen hoeveel paden er zijn van lengte ndisplaystyle n van knoop sdisplaystyle s naar knoop tdisplaystyle t.

In het bovenstaande voorbeeld is

A2=(321120230210102021120200202031001011)displaystyle A^2=beginpmatrix3&2&1&1&2&0\2&3&0&2&1&0\1&0&2&0&2&1\1&2&0&2&0&0\2&0&2&0&3&1\0&0&1&0&1&1\endpmatrix

De boom

Een boom met 6 knopen en 5 lijnen.

Een samenhangende graaf zonder cykels heet een boom. Dit omdat een dergelijke graaf in een tekening vaak op een boom lijkt. Een boom heeft één kant minder dan hij knopen heeft.

Een boom met verzameling knopen VBdisplaystyle V_B heeft |VB|−1-1 kanten

Bewijs

Het bewijs gaat met volledige inductie naar het aantal knopen.

1. Met maar één knoop zijn er geen zijden en is de uitspraak waar,


2. Stel dat de uitspraak waar is voor een grotere boom.


3. Een nieuwe knoop is via precies één zijde met deze boom verbonden, want als de knoop met twee zijden met de boom wordt verbonden, ontstaat een cykel.


4. Per nieuwe knoop komt er dus één nieuwe zijde bij.

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 (of gekozen) om model te staan voor verzamelingen van objecten waar een inherente hiërarchie in zit. Bomen zijn terug te vinden in aandachtsgebieden als:

• 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

De cykelgraaf

De cykelgraaf C6displaystyle C_6

De cykelgraaf met ndisplaystyle n knopen, Cndisplaystyle C_n, is de enkelvoudige, samenhangende graaf met ndisplaystyle 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 graaf K3displaystyle 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.

De volledige graaf

De volledige graaf met ndisplaystyle n knopen, Kndisplaystyle K_n, is de graaf waarin alle knopen onderling verbonden zijn.

De volgende grafen zijn voorbeelden van volledige grafen:

De volledige grafen K1...K8displaystyle K_1...K_8.

Het aantal zijden van Kndisplaystyle K_n is 12n(n−1)displaystyle tfrac 12n(n-1), het (n−1)displaystyle (n-1)-ste driehoeksgetal.

Bewijs

Het aantal zijden is gelijk aan het aantal mogelijke paren knopen, dus het aantal manieren om uit ndisplaystyle n objecten er 2 te kiezen. Dat aantal is de binomiaalcoëfficiënt (n2)=12n(n−1)displaystyle binom n2=tfrac 12n(n-1).

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 eulergraaf is een speciaal soort graaf die is bedacht door de wiskundige Leonhard Euler toen hij bezig was met het probleem van de zeven bruggen van Koningsbergen. Dit probleem komt neer op de vraag of het mogelijk is in een samenhangende graaf een wandeling te maken waarin alle kanten van de graaf precies één keer voorkomen, een eulerwandeling, of zelfs een dergelijke wandeling te maken zodat deze begint en eindigt in dezelfde knoop, een eulercykel.

In 1736 loste Euler dit probleem op:

Een enkelvoudige samenhangende graaf bevat een eulercykel dan en slechts dan als de graad van alle knopen even is.

Bewijs

⇒displaystyle Rightarrow

Iedere keer dat een eulercykel langs een knoop komt, is er een zijde waarover de cykel aankomt en een waarover de cykel vertrekt.

⇐displaystyle Leftarrow

Stel, er zijn twee gesloten wandelingen, dus cykels, allebei zonder dubbel gebruikte kanten, die niet een kant maar wel een knoop kdisplaystyle k gemeen hebben. Die cykels kunnen aan elkaar geplakt tot een nieuwe wandeling: start de eerste wandeling in k.displaystyle k. Maak hem af en ga dan verder met de volgende, die weer eindigt in k.displaystyle k. Stel nu dat in een enkelvoudige samenhangende graaf alle knopen een even graad hebben. In deze graaf kan een cykel worden gemaakt zonder dubbele kanten: kies een knoop en begin over kanten te lopen totdat het niet verder kan. Het eindpunt is gelijk aan het beginpunt (alle knopen hebben even graad, dus de enige knoop die tijdens de wandeling een ongebruikte ingang en geen ongebruikte uitgangen heeft is die knoop waar is begonnen). Haal nu de kanten die in de cykel zijn gebruikt weg. Herhaal dit proces totdat alle kanten op zijn. Nu is er een aantal losse gesloten wandelingen die geen kanten, maar wel een aantal punten gemeen hebben. Plak nu op de manier van de algemene opmerking boven alle wandelingen aan elkaar, en de graaf waarmee begonnen was is terug met de erin gemaakte Eulercykel.

K3, K5displaystyle K_3, K_5 en de "zeven bruggen"

De grafen K3displaystyle K_3 en K5displaystyle 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 enkelvoudige samenhangende graaf bevat een eulerwandeling dan en slechts dan als de graad van alle knopen, eventueel op twee na, even is.

Bewijs

⇒displaystyle Rightarrow

Als de eulerwandeling begint en eindigt in dezelfde knoop is het een eulercykel en hebben alle knopen een even graad. Anders is een eulerwandeling in feite een eulercykel met een ontbrekende kant. Neem nu de eulerwandeling in de graaf en plaats een fictieve kant tussen de begin- en eindknoop, dan is er een eulercykel, waarvan de graad van alle knopen dus even is. Als nu de fictieve kant wordt weggehaald gaat er een af van de graad van de begin- en eindknoop. Hun graden worden dan oneven, de graad van de rest van de knopen blijft gelijk.

⇐displaystyle Leftarrow

Zoek de twee knopen met oneven graad, als die er zijn, trek er een fictieve zijde tussen. Nu zijn de graden van alle knopen even, dus is er een eulercykel. Haal de fictieve zijde weer weg, een eulercykel minus één zijde is een eulerwandeling.

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 Gdisplaystyle 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

De 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.

K3displaystyle K_3 is planair, K5displaystyle 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 K3,3displaystyle 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 Gdisplaystyle G een samenhangende, planaire graaf met vdisplaystyle v knopen, edisplaystyle e zijden en fdisplaystyle f gebieden. Dan geldt

v−e+f=2displaystyle v-e+f=2

Bewijs

Het bewijs gaat met inductie naar e−vdisplaystyle e-v. Omdat Gdisplaystyle G samenhangend is, geldt altijd e−v≥−1displaystyle e-vgeq -1.

Stel e−v=−1displaystyle e-v=-1, de graaf is dan een boom. Aangezien Gdisplaystyle G geen cykels bevat, is het aantal gebieden 1. Dus

v−e+f=1+1=2displaystyle v-e+f=1+1=2

Inductiestap: Neem aan dat voor alle vlakke grafen met −1≤v−e<ndisplaystyle -1leq v-e<n geldt dat v−e+f=2displaystyle v-e+f=2.

We moeten bewijzen dat voor een willekeurige vlakke graaf met v−e=ndisplaystyle v-e=n de eigenschap ook geldt.

De graaf bevat nu een cykel. Deze cykel scheidt een apart gebied af. Verwijderen we nu een zijde uit de cykel, dan hebben we een graaf met een kant en een gebied minder. Als we het aantal knopen, zijden en gebieden in deze graaf v′, e′displaystyle v', e' en f′displaystyle f' noemen, geldt

e′−v′=(e−1)−v=(e−v)−1=n−1displaystyle e'-v'=(e-1)-v=(e-v)-1=n-1,

en dus vanwege de inductiehypothese:

v′−e′+f′=2displaystyle v'-e'+f'=2

Hieruit kunnen we afleiden dat

v−e+f=v′−(e′+1)+(f′+1)=v′−e′+f′=2displaystyle v-e+f=v'-(e'+1)+(f'+1)=v'-e'+f'=2,

wat precies is wat we moesten bewijzen.

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 Gdisplaystyle G een samenhangende, planaire graaf met v≥3displaystyle vgeq 3 knopen en edisplaystyle e zijden. Dan geldt

e≤3v−6displaystyle eleq 3v-6

Bewijs

Het idee achter de stelling is dat er een relatie is tussen het aantal zijden in Kndisplaystyle K_n en het soort gebieden waarin Gdisplaystyle G het vlak verdeelt. In een planaire muur fungeert iedere zijde als "binnenmuur" en als "buitenmuur" van een (afgesloten) gebied – de "buitenkant" van de graaf telt als één groot gebied. Tellen we alle binnen- en buitenmuren, dan komen we aan 2edisplaystyle 2e (iedere zijde tel je zo twee keer). Verder is het zo dat ieder gebied afgezonderd door de graaf een bepaalde vorm heeft: driehoek, vierhoek, vijfhoek, etc. Iedere ndisplaystyle n-hoek heeft dan ndisplaystyle n binnenmuren. Noemen we het aantal driehoekige gebieden f3displaystyle f_3, het aantal vierhoekige f4displaystyle f_4, het aantal vijfhoekige f5displaystyle f_5, enz., dan kunnen we het aantal muren ook op een andere manier tellen:

∑i=3nn⋅fndisplaystyle sum _i=3^nncdot f_n,

zodat

2e=3f3+4f4+5f5+…displaystyle 2e=3f_3+4f_4+5f_5+ldots

Dus we weten ook dat

2e≥3f3+3f4+3f5+…=3fdisplaystyle 2egeq 3f_3+3f_4+3f_5+ldots =3f

Dat betekent

v−e+2e3≥2displaystyle v-e+frac 2e3geq 2

waaruit volgt:

3v−e≥6displaystyle 3v-egeq 6

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

Op een soortgelijke manier als hierboven, kunnen we ook bewijzen voor samenhangende planaire grafen zonder driehoeken (dus het "kleinste" gebied is een vierhoek) dat e≤2v−4displaystyle eleq 2v-4. Hiermee is ook het puzzeltje opgelost: K3,3displaystyle K_3,3 is niet planair.

Een opmerkelijke en nuttige stelling is die van Kuratowski: een graaf is planair dan en slechts dan als hij niet K5displaystyle K_5 of K3,3displaystyle K_3,3 bevat. Oftewel, alleen die twee grafen zijn in feite niet-planair.

De bipartiete graaf

Een voorbeeld van een bipartiete graaf

Een bipartiete graaf Gdisplaystyle G is een graaf waarvan de knopen verdeeld zijn over een partitie V1,V2displaystyle V_1,V_2 met de eigenschap dat een knoop in het ene deel alleen verbonden is met een knoop in het andere deel. Formeel:

VG=V1∪V2displaystyle V_G=V_1cup V_2

V1∩V2=∅displaystyle V_1cap V_2=varnothing

v1∈V1 en v1∼v2displaystyle v_1in V_1text en v_1sim v_2, dan v2∈V2displaystyle v_2in V_2

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

Eveneens is duidelijk dat C3displaystyle 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 C2n+1displaystyle C_2n+1 dat deze niet bipartiet zijn, sterker nog:

Een graaf Gdisplaystyle G is bipartiet ⇔displaystyle Leftrightarrow Gdisplaystyle G bevat geen oneven cykels

Bewijs

⇒displaystyle Rightarrow

Stel Gdisplaystyle G is een bipartiete graaf. Alle kanten van Gdisplaystyle G lopen dus over de partitiegrens heen. Is er nu een cykel van oneven lengte, dan ligt er één knoop van de cykel meer in de ene deelverzameling dan in de andere – zogezegd, de "eerste" en "laatste" knoop van de cykel liggen in dezelfde deelverzameling. Deze twee knopen kunnen echter niet verbonden zijn om de cykel te sluiten: zijn ze het wel, dan is de graaf niet bipartiet.

⇐displaystyle Leftarrow

Stel Gdisplaystyle G bevat geen oneven cykels. Dat wil zeggen, voor iedere cykel in Gdisplaystyle G die niet samenhangt met een andere kan ik een knoop kiezen, die in V1displaystyle V_1 plaatsen, de volgende in V2displaystyle V_2, de volgende weer in V1displaystyle V_1, enzovoorts, en de laatste in V2displaystyle V_2 en dan lopen alle kanten in de cykel over de partitiegrens. Voor alle andere knopen (cykels, anderzijds) geldt dan dat dat hun verdeling over de partities vastligt zodra de verdeling van bovengenoemde cykels gekozen is (en merk op: ook voor cykels in deze situatie geldt dat ze perfect verdeeld kunnen worden, omdat ze even lengte hebben). Daarmee is de graaf bipartiet.

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

De 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.

Overigens is de Petersengraaf ook een voorbeeld van een graaf die K5displaystyle K_5 bevat: als we de buitenste "ring" van knopen en de binnenste "ring" samentrekken, vinden we de K5displaystyle K_5-graaf. We kunnen dan ook duidelijk zien dat de Petersengraaf niet planair is.

Graafoperaties, de 2-graaf en geïnduceerde grafen

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

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

Om te beginnen is er de op Gdisplaystyle G geïnduceerde graaf G′.displaystyle G'. Deze graaf is gedefinieerd door:

G′=(V′,E′)displaystyle G'=(V',E')

met

V′⊆VGdisplaystyle V'subseteq V_G

en zo dat voor alle knopen v1,v2∈V′displaystyle v_1,v_2in V' geldt

v1,v2∈EG⇒v1,v2∈E′displaystyle v_1,v_2in E_GRightarrow v_1,v_2in E'

De door Gdisplaystyle G geïnduceerde graaf G′displaystyle G' is de graaf bestaande uit een aantal knopen van Gdisplaystyle G en de bijbehorende zijden van Gdisplaystyle G.

Graaf met zijn complementgraaf.

Daarnaast is er de complementgraaf (of complementaire graaf) G¯displaystyle overline G van G,displaystyle G, gedefinieerd door:

G¯=(VG¯,EG¯)displaystyle overline G=(V_overline G,E_overline G)

met

VG¯=VGdisplaystyle V_overline G=V_G

en zo dat voor alle knopen v1,v2∈V′, v1≠v2displaystyle v_1,v_2in V', v_1neq v_2 geldt

v1,v2∉EG⇒v1,v2∈EG¯displaystyle v_1,v_2not in E_GRightarrow v_1,v_2in E_overline G

De complementgraaf G¯displaystyle overline G van Gdisplaystyle G heeft dus dezelfde knopen als Gdisplaystyle G, maar alle mogelijke zijden die juist niet in Gdisplaystyle G zitten.

Graaf met bijbehorende lijngraaf.

Ook is er de lijngraaf L(G)=(VL,EL)displaystyle L(G)=(V_L,E_L) van Gdisplaystyle G, die de zijden van Gdisplaystyle G als knopen heeft en er een zijde is tussen twee knopen van L(G)displaystyle L(G) als de bijbehorende zijden van Gdisplaystyle G een knoop gemeen hebben. Deze graaf is gedefinieerd door:

VL=E(G)displaystyle V_L=E(G)

v1,v2,v1′,v2′∈ELdisplaystyle v_1,v_2,v_1',v_2'in E_L als

v1=v1′ of v1=v2′ of v2=v1′ of v2=v2′displaystyle v_1=v_1'text of v_1=v_2'text of v_2=v_1'text of v_2=v_2'

De vereniging van twee disjuncte grafen.

Voor twee grafen Gdisplaystyle G die geen knopen of kanten gemeen hebben, kan ook de vereniging en het cartesisch product gedefinieerd worden. De vereniging van Gdisplaystyle G en Hdisplaystyle H is de graaf G∪Hdisplaystyle Gcup H met

V(G∪H)=V(G)∪V(H)displaystyle V(Gcup H)=V(G)cup V(H)

E(G∪H)=E(G)∪E(H)displaystyle E(Gcup H)=E(G)cup E(H)

Het cartesisch product van twee grafen.

Het cartesisch product van Gdisplaystyle G en Hdisplaystyle H is de graaf G×Hdisplaystyle Gtimes H met als knopen de paren van knopen van Gdisplaystyle G en Hdisplaystyle 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×H)=V(G)×V(H)displaystyle V(Gtimes H)=V(G)times V(H)

(g,h),(g′,h′)∈E(G×H)displaystyle (g,h),(g',h')in E(Gtimes H) als

(g=g′ en h∼h′) of (g∼g′ en h=h′)displaystyle (g=g'text en hsim h')text of (gsim g'text en h=h')

V.l.n.r.: K20, K21, K22displaystyle K_2^0, K_2^1, K_2^2 en K23displaystyle K_2^3.

Een bekend voorbeeld van graaf-vermenigvuldiging is de rij van de "machten" van de 2-graaf (d.i. K2displaystyle K_2): dit zijn de ndisplaystyle n-dimensionale kubussen hier rechts.

Gerichte grafen

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

E⊆(v1,v2)∣v1,v2∈V,v1≠v2displaystyle Esubseteq (v_1,v_2)mid v_1,v_2in V,v_1not =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)displaystyle (a,b) niet dezelfde is als de zijde (b,a)displaystyle (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 kdisplaystyle k maar één pad is van de wortel naar kdisplaystyle 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. Bijvoorbeeld heeft de graad een andere betekenis. De graad van een knoop is in een enkelvoudige graaf het aantal kanten waarmee de knoop incident was, in een gerichte graaf is de definitie iets anders:

• ingraad van een knoop kdisplaystyle k: het aantal zijden (m,k)∈Edisplaystyle (m,k)in E
  


• uitgraad van een knoop kdisplaystyle k: het aantal zijden (k,n)∈Edisplaystyle (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=V1∪V2displaystyle V=V_1cup V_2 een zijde loopt van V1displaystyle V_1 naar V2displaystyle 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 Gdisplaystyle G uitgebreid met een of twee functies fdisplaystyle f en g:displaystyle g:

f:E(G)→Adisplaystyle f:E(G)to A

g:V(G)→Bdisplaystyle g:V(G)to B

De functies fdisplaystyle f voegt aan iedere zijde, en de functie gdisplaystyle 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 (N,Z,Q,R,Cdisplaystyle mathbb N ,mathbb Z ,mathbb Q ,mathbb R ,mathbb C , etc.), heet 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 vdisplaystyle v knopen is vv−2displaystyle v^v-2

Bewijs

Het bewijs volgt uit de codering van Prüfer van knoop-gelabelde bomen. Deze constructie werkt als volgt:

• Van knoopgelabelde boom met vdisplaystyle v knopen naar prüferrij ter lengte v−2:displaystyle v-2: kies het blad (knoop met graad 1) van de boom met het laagste label. Verwijder deze knoop en noteer het label van zijn buur. Ga zo door totdat er maar twee knopen over zijn en verwijder deze gewoon. Nu is er een prüferrij ter lengte v−2displaystyle v-2, door steeds bladeren te verwijderen naar volgorde van grootte.

• Van de prüferrij ter lengte v−2displaystyle v-2 naar knoopgelabelde boom met vdisplaystyle v' knopen: Merk om te beginnen op dat een element van de prüferrij een buur is van een andere knoop in de boom. Alleen labels van bladeren in de nog op te bouwen (deel)boom staan dus niet in de rij. Schrijf nu alle getallen 1,2,…,vdisplaystyle 1,2,ldots ,v op. Kies uit dit rijtje het laagste element dat niet in de prüferrij staat. Verbindt dit element met het eerste element van de prüferrij en streep beide weg. Herhaal dit totdat de Prüferrij leeg is. Er staan nu nog twee getallen in de rij – verbindt deze twee in de boom. Nu heb je een boom opgebouwd met vdisplaystyle v' knopen, door steeds bladeren toe te voegen naar volgorde van grootte.

• Iedere boom op vdisplaystyle v knopen kan dus eenduidig gecodeerd worden als een rij van lengte v−2displaystyle v-2. Ieder van deze elementen kan een van de getallen 1,2,…,vdisplaystyle 1,2,ldots ,v zijn. Dat zijn dus vv−2displaystyle v^v-2 mogelijke combinaties.

Hypergrafen

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

Problemen op grafen

• 
  Kleuren van grafen: de 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

Zie de categorie Graph theory van Wikimedia Commons voor mediabestanden over dit onderwerp.

Dit artikel is op 6 augustus 2003 in deze versie opgenomen in de etalage.