Grafentheorie

Van Wikipedia

De grafentheorie is een tak van wiskunde die de eigenschappen van grafen bestudeert.

Een graaf bestaat uit een verzameling punten, knopen genoemd, waarvan sommige verbonden zijn door lijnen, de zijden of kanten. 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 zijn alomtegenwoordig, en veel praktische problemen kunnen als een probleem op een graaf gemodelleerd worden. Grafen worden bijvoorbeeld gebruikt om eindige toestandsmachines te modelleren of om een schematische routekaart te maken tussen een aantal plaatsen met de afstanden daartussen. Over deze grafen kunnen algoritmes uitgevoerd worden om bepaalde eigenschappen van zo'n graaf te berekenen; binnen de informatica is dit een redelijk belangrijk onderwerp.

Complexe netwerken is een vrij recente stroming in het onderzoek rond grafen die minder focust op de studie van kleine grafen, en de eigenschappen van individuele knopen en bogen in deze grafen, maar eerder op de statistische eigenschappen van grootschalige netwerken.

[bewerk] Definities van grafen

Er zijn verschillende definities gangbaar om grafen te definiëren, hier volgen de definities zoals ze in deze encyclopedie gehanteerd worden.

Een graaf bestaat uit een verzameling knopen (Engels: vertices) en een verzameling zijden of kanten (Engels: edges) van paren knopen. Meer formeel:

Een graaf G = (V, E) is een geordend paar van een verzameling V en een verzameling E van paren elementen uit V. De elementen van V heten de knopen van de graaf G en de elementen van E de zijden of kanten van G. De knopen die een zijde vormen heten de eindpunten van de zijde.

Een ruimer begrip graaf laat toe dat twee knopen door meer dan een zijde verbonden zijn. Een graaf G = (V,E) is dan een geordend paar van een verzameling V en een multiset E van paren deelverzamelingen van V:

$E = \{(E_1, E_2) | E_1, E_2 \in \it \wp(V))\}$

Daarbij worden soms, ter verduidelijking, de volgende notaties gebruikt:

V(G) = de knopen van G

E(G) = de kanten van G

V G = V (G)

E G = E (G)

In een algemene graaf zoals boven gedefinieerd, zijn er geen beperkingen aan de verbindingen tussen knopen: meerdere kanten tussen twee knopen, lussen (kanten van één knoop naar dezelfde knoop), kanten van een knoop naar niets, kanten van meerdere knopen naar meerdere knopen, kanten zonder knopen, alles is mogelijk. Ook hebben kanten geen richting: een kant van knoop a naar knoop b is ook een kant van knoop b naar knoop a.

Meestal wordt niet met dergelijke, algemene grafen gewerkt, maar wordt gebruik gemaakt van grafen waarbij er beperkingen gesteld zijn aan de manier waarop kanten mogen voorkomen.

[bewerk] Terminologie

Voor een graaf G = (V,E) is incidentie of directe verbondenheid (aangegeven met de operator $\sim$ ) gedefinieerd als

$v_1 \sim v_2 \dot = (V_1, V_2) \in E \and (v_1 \in V_1 \and v_2 \in V_2)$

d.w.z. twee knopen zijn direct verbonden (of incident) als er een kant tussen loopt.

Twee knopen zijn verbonden als er een pad van kanten tussen loopt (d.w.z. als ze gerelateerd zijn in de transitieve sluiting van de relatie $\sim$ ):

$v_1 \sim^* v_2 \dot = v_1 \sim v_2 \vee (v_1 \sim v_3 \wedge v_3 \sim^* v_2)$

Een knoop k kan ook incident zijn met een kant: k heet incident met een kant e als k een begin- of eindpunt van e is

Een wandeling tussen twee verbonden knopen a en b is een rijtje knopen met kanten ertussen waardoor a en b verbonden zijn:

$\mathrm{walk}(a,b) \dot =(v_1,...,v_n): a \sim v_1 \sim v_2 \sim \ldots \sim v_n \sim b$

In een wandeling is het niet bedoeling een kant in twee verschillende richtingen te volgen (d.w.z., het is niet de bedoeling een wandeling te volgen en er dan weer een stuk van terug te nemen). De lengte van een wandeling is het aantal knopen in de wandeling.

Een pad tussen twee verbonden knopen a en b is de kortste wandeling tussen a en b (of een van de kortste wandelingen als er meer van dezelfde lengte zijn).

De afstand tussen twee knopen a en b (notatie: d(a,b)) is de lengte van het pad tussen a en b (of oneindig, als er geen pad is tussen a en b).

De diameter van een graaf G is de lengte van het langste pad (het maximum van de lengtes van alle paden) in G.

Een cykel in een graaf G is een wandeling van een knoop a naar a.

De taille van de graaf is de lengte van de korste cykel in de graaf, een acyclische graaf heeft taille $\infty$ .

De graad van een knoop k (notatie d(k) of deg(k)) is het aantal kanten waarmee k incident is.

Indien alle knopen dezelfde graad $g k$ hebben wordt de graaf $g k$ -regulier genoemd. Een graaf heet regulier als er een getal $g k$ bestaat zodat hij $g k$ -regulier is (d.w.z $\exists_{g_k} : (\forall_{v \in V} : (deg(v) = g_k))$ .

Twee grafen $G 1$ en $G 2$ zijn gelijk aan elkaar (isomorf) als $V(G_1) = V(G_2) \wedge E(G_1) = E(G_2)$ .

Een partitie van een graaf G is een verdeling van $V G$ in een aantal deelverzamelingen $V G, i$ zodanig dat $\bigcup_{i} V_{G,i} = V_G \wedge \forall_{i,j} j \not = i \Rightarrow V_{G,i} \cap V_{G,j} = \empty$

[bewerk] Simpele grafen

De simpele graaf (ook wel enkelvoudige graaf genoemd) is de meest gebruikte soort graaf. Het is een graaf met zijden die altijd tussen twee knopen lopen, niet meer dan een zijde tussen twee knopen en geen lussen. Een graaf $G s = (V s, E s)$ is een simpele graaf als:

$E_s \subseteq \{\{v_1, v_2\} | v_1, v_2 \in V_s \and v_1 \not = v_2\}$

Een simpele graaf is aanzienlijk eenvoudiger dan een algemene graaf. Zo kan er in een simpele graaf tussen twee knopen maximaal één kant lopen, zijn er geen kanten met maar één knoop (of zelfs geen) en ook geen lussen. De volgende graaf is een simpele graaf:

De simpele graaf vindt veel toepassing binnen de wiskunde en de informatica. Over simpele grafen is dan ook een groot lichaam aan wiskundige kennis (bewezen eigenschappen). Ook is er een flink aantal "speciale" soorten simpele grafen geïdentificeerd.

[bewerk] Graafcomponenten en de samenhangende graaf

Een graaf bestaande uit twee componenten.

Binnen een simpele graaf is een component een aantal knopen van de graaf die onderling alle verbonden zijn:

Een component C van graaf G is $V_C \subseteq V_G$ met

$\forall_{v_1, v_2 \in V_C} v_1 \sim^* v_2$

Een graaf waarin alle punten verbonden zijn en dus één component vormen, heet een samenhangende graaf.

[bewerk] De matrixvoorstelling van een graaf

We kunnen een graaf eenvoudig voorstellen in een matrix. De bogenmatrix zoals deze genoemd wordt is een vierkante matrix met dimentie n*n waarbij n het aantal knopen in de graaf is. Het element a_ij in de bogenmatrix A is '1' als er een boog bestaat die van i naar j gaat en '0' als dit niet het geval is.

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

[bewerk] De boom

Een boom met 6 knopen en 5 kanten.

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

Stelling: Een boom met verzameling knopen $V B$ heeft $| V B | - 1$ kanten
Bewijs

Het kunnen niet minder dan | V_B | - 1 kanten zijn:
Stel, ik heb een stel knopen. Daarvan kan op de volgende wijze een steeds grotere boom maken, totdat de knopen op zijn:
- Neem ik één knoop, dan is dat een boom (lussen mogen niet in simpele grafen!) met één kant minder dan er knopen zijn
- Doe ik er één knoop bij en trek ik een kant van die knoop naar een knoop die er al was, dan heb ik één knoop toegevoegd en één kant – zonder cykels te maken. Dus ik heb nog steeds een boom met één kant minder dan er knopen in zitten.
Heb ik meer dan $| V B | - 1$ kanten, dan heb ik een cykel in mijn graaf zitten:

Stel, ik heb een boom met $| V B | - 1$ kanten. Dan heb ik vanuit elke knoop een pad lopen naar de eerste knoop die ik in de boom gestopt heb (zie constructie van de boom in vorige stap). Voeg ik tussen enige twee knopen een kant toe, dan kan ik vanuit één van die knopen naar de eerste knoop naar de andere knoop en weer terug naar de knoop waar ik begonnen ben.

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.

Een niet-samenhangende graaf waarvan alle componenten op zich bomen zijn, heet een bos.

[bewerk] Toepassingsgebieden

Bomen behoren tot de meest 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. Als zodanig zijn bomen onder meer terug te vinden binnen 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 op bomen als zodanig vele algoritmen gedefinieerd zijn. Voorbeelden hiervan zijn

Breadth-first search
Depth-First search
Minimum Spanning Tree

[bewerk] De complete graaf

De complete graaf op N knopen (afgekort tot $K N$ ) is de graaf waarin alle punten onderling verbonden zijn.

$K_N = (V_{K_N}, E_{K_N})$ met

$V_{K_N}$ een verzameling knopen en

| V | = N

$E_{K_N} = \{\{v_1, v_2\} | v_1, v_2 \in V_{K_N} \wedge v_1 \not = v_2\}$

De volgende grafen zijn voorbeelden van complete grafen:


De complete grafen $K 1 ... K 8$ .

Stelling: Het aantal kanten van $K N$ is $\frac{N \cdot (N-1)}{2}$ .
Bewijs: Om een knoop met een andere knoop te verbinden, is één kant nodig. Om twee knopen met een andere knoop te verbinden, zijn twee kanten nodig. Om N-1 knopen met een andere te verbinden, zijn dus N-1 kanten nodig. Willen we van N knopen iedere twee knopen onderling met elkaar verbinden, dan hebben we dus N*(N-1) knopen nodig. Maar als we inderdaad zoveel kanten gebruiken, hebben we iedere knoop dubbel met iedere andere knoop verbonden: een kant van a naar b is in een simpele graaf tenslotte ook een kant van b naar a. Dus hebben we maar de helft nodig: $\frac{N \cdot (N-1)}{2}$ .

[bewerk] De Kliek

Een kliek is een deelverzameling punten uit een puntenverzameling V, zo dat elk punt in de deelverzameling verbonden is met alle andere punten in die verzameling, ze vormen samen met de lijnen waaraan ze incident zijn dus een volledige graaf.

[bewerk] De cykel-graaf

De cykel-graaf op N knopen ( $C N$ ) is de simpele, samenhangende graaf met N knopen waarbij iedere knoop verbonden is met twee andere. Een dergelijke graaf heeft altijd de vorm van een cirkel en bevat dus ook altijd een cykel ter grootte van de gehele graaf.

Stelling: Het aantal kanten van een cykel-graaf op N knopen is N.; Bewijs: Door constructie: Begin met het maken van een cykel-graaf; neem daartoe een punt. Voeg een volgend punt toe en verbind dit nieuwe punt met het laatste door een kant. Ga zo verder – je krijgt een keten van N knopen met N-1 kanten. Verbind nu de laatste knoop met de eerste om de cykel te sluiten: N kanten.
Uit definitie: Een samenhangende rij van N knopen is een boom en bevat dus N-1 kanten. De extra kant erbij maakt een cykel.

Er is ook een variant op de $C N$ -graaf, namelijk de $C k, l$ -graaf (k + l = N). Dit is de graaf met een cykel ter grootte l, waar ook nog een losse "sliert" van k knopen aan hangt.

[bewerk] Toepassingsgebieden

Cykel-grafen zijn binnen de informatica zeer bekend als netwerkmodel. Het token-ring netwerk is hierop gebaseerd.

Cykel-grafen dienen ook als vaak als model voor lokale zoekalgoritmen.

[bewerk] De Euler-graaf en de Hamilton-graaf

De Euler-graaf is een speciaal soort graaf die geïdentificeerd is door de wiskundige Leonhard Euler naar aanleiding van zijn oplossing van het probleem van de Zeven bruggen van Königsberg. 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 zogeheten Euler-wandeling) of zelfs een dergelijke wandeling te maken zodat deze begint en eindigt in dezelfde knoop (Euler-cykel).

In 1736 loste Euler dit probleem op en bewees dat de oplossing heel simpel is:

Stelling: een simpele, samenhangende graaf bevat een Euler-cykel dan en slechts dan als de graad van alle knopen even is.
Bewijs: " $\Rightarrow$ ": Als een graaf een Euler-cykel bevat, dan is er dus een wandeling van iedere knoop in de graaf naar diezelfde knoop waarin alle kanten van de graaf voorkomen. In een simpele graaf kan het niet anders dan dat in een dergelijke wandeling ook alle knopen voorkomen: een kant moet tussen twee knopen lopen. Verder is het ook nog zo, dat je in die wandeling bij iedere knoop waar je "aankomt" ook weer "weggaat" (in omgekeerde volgorde bij het beginpunt, uiteraard). Omdat je in een Euler-cykel iedere kant maar één keer mag gebruiken, betekent dat dat er bij iedere knoop, voor iedere "inkomende" kant ook een "uitgaande" kant moet zijn. Dus het aantal kanten waarmee een knoop incident is, is in een Euler-graaf altijd een veelvoud van twee, oftewel de graad van al de knopen is even.; " $\Leftarrow$ ":

Algemene opmerking: Stel, je hebt twee gesloten wandelingen (d.w.z. cykels), allebei zonder dubbel gebruikte kanten, die niet een kant maar wel een knoop k gemeen hebben. Die kunnen we aan elkaar plakken tot een nieuwe wandeling: start de eerste wandeling in k, maak hem af en ga dan verder met de volgende (die weer eindigt in k). Goed, stel nu dat in een simpele, samenhangende graaf alle knopen even graad hebben. In deze graaf kan ik een cykel maken zonder dubbele kanten: ik kies een knoop en begin over kanten te lopen totdat ik niet verder kan. Ik ben nu weer terug waar ik begonnen ben (alle knopen hebben even graad, dus de enige knoop die tijdens mijn wandeling een ongebruikte "ingang"-kant heeft en geen ongebruikte "uitgang"-kanten is die knoop waar ik begonnen ben). De kanten die ik in mijn cykel gebruikt heb, haal ik nu weg. Dan herhaal ik dit proces, totdat alle kanten op zijn. Nu heb ik een aantal losse, gesloten wandelingen die geen kanten, maar wel een aantal punten gemeen hebben. Op de manier van de algemene opmerking boven, plak ik nu al mijn wandelingen aan elkaar – ik heb nu de graaf terug waar ik mee begonnen was, en een Euler-cykel die ik erin gemaakt heb.


De $K 3$ - en $K 5$ -grafen bevatten beide Euler-cykels. De graaf die het probleem van de zeven bruggen voorstelt, bevat geen Euler-cykel.

Met de kennis van wat er nodig is om een Euler-cykel te hebben, is het volgende makkelijk in te zien:

Stelling: een simpele, samenhangende graaf bevat een Euler-wandeling dan en slechts dan als de graad van alle knopen behalve twee even is.
Bewijs: " $\Rightarrow$ ": Een Euler-wandeling is in feite een Euler-cykel met een ontbrekende kant. Neem ik nu de Euler-wandeling in mijn graaf en plaats ik een fictieve kant tussen de begin- en eindknoop, dan heb ik een Euler-cykel – waarin de graad van alle knopen dus even is. Haal ik nu mijn fictieve kant weg, dan trek ik één af van de graad van de begin- en eindknoop. Hun graden worden dan oneven, de graad van de rest van de knopen blijft gelijk.; " $\Leftarrow$ ": Zoek de twee knopen met oneven graad, trek er een fictieve kant tussen. Nu zijn de graden van alle knopen even, dus is er een Euler-cykel. Haal de fictieve kant weer weg – een Euler-cykel minus één kant is een Euler-wandeling.

Naast de Euler-cykel en -wandeling is er nog een variant: de cykel en wandeling waarin iedere knoop één keer voorkomt. Dit zijn de Hamilton-cykel en Hamilton-wandeling (in de Hamilton-graaf, uiteraard). Deze variant is bedacht door William Hamilton, maar ze is niet zo makkelijk te doorgronden als de Euler-graaf. De wiskundige Ore bewees wel de volgende stelling:

$\forall_{a,b \in V_G} : deg(a) + deg(b) \geq |V_G| \Rightarrow$ "G bevat een Hamilton-cykel"

(G bevat een Hamilton-cykel als de graad van alle knopen maar groot genoeg is).

Over het algemeen is het vinden van een Hamilton-cykel in een graaf echter een NP-compleet probleem.

Het probleem van de Hamilton-cykel wordt vaak verward met het handelsreizigersprobleem. Deze problemen lijken op elkaar – bij het Hamilton-probleem is het echter niet noodzakelijk zo dat de graaf compleet moet zijn.

[bewerk] De planaire graaf

Planaire of vlakke grafen zijn grafen die je op een plat vlak kunt tekenen, zonder daarbij de kanten van de graaf elkaar te laten snijden.


De $K 3$ -graaf is planair; de $K 5$ -graaf niet

Dergelijke grafen zijn van belang bij de modellering van zaken als pijpleidingen en printplaten voor elektronica (waar de verbindingen natuurlijk geen kortsluiting 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 bij planaire grafen heeft Leonhard Euler een flinke vinger in de pap en wel met zijn Stelling van Euler. Deze stelling is gebaseerd op het aantal knopen, kant en gebieden van een graaf – waarbij een gebied het stuk papier is waarop de graaf getekend is, of een stuk van dat papier dat geheel door kanten van de graaf omgeven wordt (als er een cykel in de graaf zit). Technisch gesproken hangt het aantal gebieden af van hoe je de graaf precies tekent, maar het blijkt dat je een bepaalde graaf altijd met een bepaald aantal gebieden kunt tekenen, dat niet verandert hoe je de graaf ook precies tekent – tenzij je vals speelt en de graaf niet-planair tekent.

Stelling van Euler: Zij G een samenhangende, planaire graaf met v knopen, e kanten en f gebieden. Dan geldt

v - e + f = 2

Bewijs: Dit bewijs gaat met inductie naar $e - v$ . Omdat G samenhangend is, geldt altijd $e - v \geq -1$ .

BASIS: $e - v = - 1$ (de graaf is een boom)
De graaf G bevat geen cykels; het aantal gebieden is dus 1. $e - v = -1 \equiv v - e = 1$ , dus $v - e + f = v - e + 1 = 1 + 1 = 2$ .

STAP: Neem aan dat voor $-1\leq k < n$ geldt dat voor alle vlakke grafen met $v - e = k$ v-e+f=2 hebben. We moeten bewijzen dat voor een willekeurige vlakke graaf met $v - e = n$ hetzelfde geldt.
De graaf bevat nu een cykel. Deze cykel scheidt een apart gebied af. Verwijderen we nu een kant uit de cykel, dan hebben we een graaf met een kant en een gebied minder. Als we het aantal knopen, kanten en gebieden in deze graaf v', e' en f' noemen, geldt $e' - v' = (e - 1) - v = (e - v) - 1 = n - 1$ , en dus $v' - e' + f' = 2$ vanwege de inductiehypothese. Hieruit kunnen we afleiden dat $v - e + f = v' - (e' + 1) + (f' + 1) = v' - e' + f' = 2$ , wat precies is wat we moesten bewijzen.

Met de Stelling van Euler kunnen we laten zien dat een samenhangende graaf alleen planair kan zijn als hij niet al te veel kanten heeft.

Stelling: Zij G een samenhangende, planaire graaf met v knopen en e kanten en $3 \leq v$ . Dan geldt $e \leq 3v - 6$ . Bewijs: Het idee achter de stelling is dat er een relatie is tussen het aantal kanten in G en het soort van gebieden waarin G het vlak verdeelt. In een planaire muur fungeert iedere kant 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 2e (iedere kant 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 n-hoek heeft dan n binnenmuren. Noemen we het aantal driehoekige gebieden $f 3$ , het aantal vierhoekige $f 4$ , het aantal vijfhoekige $f 5$ enzovoorts, dan kunnen we het aantal muren ook op een andere manier tellen: $\sum_{i = 3}^{n} n \cdot f_n$ . Oftewel

$2e = 3f_3 + 4f_4 + 5f_5 + \ldots$

Dus we weten ook $2e \geq 3f_3 + 3f_4 + 3f_5 + \ldots = 3f$ .
En dus ook $v - e + \frac {2e}{3} \geq 2$ En dus dat $3v - e \geq 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 het "kleinste" gebied is een vierhoek) dat $e \leq 2v - 4$ . Hiermee is ook het puzzeltje opgelost: $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 $K 5$ of $K 3,3$ bevat. Oftewel, alleen die twee grafen zijn in feite niet-planair.

[bewerk] De bipartiete graaf

Een bipartiete graaf G is een graaf zodanig dat

$V_G = V_{G,1} \cup V_{G,2} (V_{G,1} \cap V_{G,2}) = \empty \wedge$
$\forall_{\{v_1,v_2\} \in E_G}:v_1 \in V_{G,1} \wedge v_2 \in V_{G,2}$

oftewel: er is een partitie van V zodanig dat alle kanten van V tussen de twee deelverzamelingen van knopen lopen en er geen "interne" kanten zijn. Hierbij is het ook toegestaan dat één van beide verzamelingen leeg is, of zelfs allebei, zodat ook een graaf op 0 of 1 knoop bipartiet is.

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 2 * n + 1$ dat deze niet bipartiet zijn. Sterker nog:

Stelling: Een graaf G is bipartiet $\Leftrightarrow$ G bevat geen oneven cykels
Bewijs: " $\Rightarrow$ ": Stel, G is bipartiet. Alle kanten van G lopen dus over de partitie-grens heen. Heb ik 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. Maar deze twee knopen kunnen niet verbonden zijn om de cykel te sluiten: zijn ze het wel, dan is de graaf niet bipartiet.; " $\Leftarrow$ ": Stel, G bevat geen oneven cykels. Dat wil zeggen, voor iedere cykel in G die niet samenhangt met een andere kan ik een knoop kiezen, die in $V 1$ plaatsen, de volgende in $V 2$ , de volgende weer in $V 1$ , enzovoorts, en de laatste in $V 2$ en dan lopen alle kanten in de cykel over de partitie-grens. Voor alle andere knopen (cykels, anderzijds) geldt dan dat dat hun verdeling over de partities vastligt zodra ik de verdeling van bovengenoemde cykels gekozen heb (en merk op: ook voor cykels in deze situatie geldt dat ze perfect verdeelt kunnen worden omdat ze even lengte hebben). Daarmee is de graaf bipartiet.

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

[bewerk] De Petersen-graaf

Petersen-graaf.

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

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

Overigens is de Petersen-graaf ook een voorbeeld van een graaf die $K 5$ bevat: 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 Petersen-graaf niet planair is.

[bewerk] Graafoperaties, de 2-graaf en geïnduceerde grafen

De rechtse 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'. Deze graaf is als volgt gedefinieerd:

de op

G

geïnduceerde graaf

G'

is een paar

(V', E')

met

$V' \subset V_G$

$\forall_{\{v_1, v_2\} \in E_G} : v_1 \in V' \wedge v_2 \in V' \Rightarrow \{v_1, v_2\} \in E'$

oftewel, de graaf op een aantal knopen van G en de kanten van G die je nog tussen die twee knopen kunt trekken.

Graaf met zijn complementgraaf.

Daarnaast is er de complementgraaf van G. Dit is

de complementgraaf $\overline{G}$ van

G

is het paar ( $V(\overline{G})$ , $E(\overline{G})$ ) met

$V(\overline{G}) = V(G)$

$E(\overline{G})$ = $\{ \{v_1, v_2\} | v_1,v_2 \in V(G) \wedge v_1 \not = v_2\} \backslash E(G)$

oftewel de graaf met dezelfde knopen als G, maar alle kanten die juist niet in G zitten.

Graaf met bijbehorende lijngraaf.

Ook kennen we de lijngraaf L(G) van G. Deze graaf is

L(G) is een graaf

(V L, E L)

met

V L = E (G)

$E_L = \{ \{e_1, e_2\} | e_1 = \{v_{1,1}, v_{1,2}\} \wedge e_2 = \{v_{2,1}, v_{2,2}\} \wedge (v_{1,1} = v_{2,1} \vee v_{1,1} = v_{2,2} \vee v_{1,2} = v_{2,1} \vee v_{1,2} = v_{2,2})\}$

oftewel de graaf waarvan de knopen de kanten zijn van G en er een kant loopt tussen twee knopen van L(G) als de bijbehorende kanten van G een knoop gemeen hebben.

De vereniging van twee disjuncte grafen.

Voor twee grafen G en H die geen knopen of kanten gemeen hebben (disjunct zijn) kunnen we ook de vereniging en het cartesisch product definiëren. De vereniging van G en H is de graaf G ∪ H met

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

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

Het cartesisch product van twee grafen.

Het cartesisch product van G en H is de graaf $G \times H$ met

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

$E(G \times H) = \{ \{(g_1, h_1), (g_2,h_2)\} | (g_1 = g_2 \wedge h_1 \sim h_2) \vee (g_1 \sim g_2 \wedge h_1 = h_2)\}$

oftewel de knopen van $G \times H$ zijn de paren van knopen van G en H en deze knopen zijn verbonden door kanten als één van de knopen in de twee paren dezelfde zijn en de andere verbonden waren.

V.l.n.r.: $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 (d.i. $K 2$ ): dit zijn de n-dimensionale kubussen hier rechts.

[bewerk] Gerichte grafen

Een type graaf die naast de simpele graaf vaak voorkomt, is de gerichte graaf. Formeel is een gerichte graaf een graaf G met

G = (V, E) m e t

V een verzameling knopen ( $V = \{v_1, v_2, v_3, \ldots\}$ )

E een verzameling kanten: $E \subseteq \{ (v_1,v_2) | v_1, v_2 \in V \wedge v_1 \not = v_2 \}$

Het verschil met de simpele graaf is dat de kanten niet langer ongeordende paren zijn, maar juist geordende paren (intuïtief wil dat zeggen: de kanten hebben nu een richting). Merk op dat in de bovenstaande definitie een kant dan ook een geordend paar is en niet een verzameling. Dit wil dan ook zeggen dat een kant (a,b) niet hetzelfde is als de kant (b,a).

Vanwege het concept van "richting" is het normaal om bij een gerichte graaf de kanten als pijlen te tekenen in plaats van als lijnen.

Veel van de concepten zoals die gedefinieerd zijn voor simpele grafen, bestaan ook voor gerichte grafen. Bomen, complete grafen, somgrafen en productgrafen bestaan allemaal. Alleen is de uitwerking soms anders, omdat de richting nu meespeelt. Zo is het bij simpele grafen zo dat er voor iedere knoop 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.

[bewerk] Enige verschillen ten opzichte van simpele grafen

Er zijn een aantal typische dingen die anders zijn in gerichte grafen in vergelijking met simpele grafen. Bijvoorbeeld heeft het concept graad een heel andere betekenis. Was de graad van een knoop in een simpele graaf het aantal kanten waarmee de knoop incident was, in een gerichte graaf verliest deze definitie zijn betekenis. In plaats daarvan kennen we de

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

Een gerichte graaf bevat een Euler-wandeling dan en slechts dan als voor alle knopen in de graaf de in- en uitgraad glijk zijn. Het bewijs hiervoor is vrijwel hetzelfde als dat voor de simpele Eulergraaf.

Een gerichte graaf heet samenhangend als er voor iedere partitie $V = V_1 \cup V_2$ een kant loopt tussen $V 1$ en $V 2$ (of omgekeerd). Loopt er altijd een dergelijke kant in beide richtingen (d.w.z. als er tussen iedere twee knopen een wandeling is in beide richtingen), dan heet de graaf sterk samenhangend.

[bewerk] Gelabelde en gewogen grafen

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

$f : E(G) \rightarrow A$

$g : V(G) \rightarrow B$

Deze functies voegen aan iedere kant (of knoop, in het geval van g) een element toe uit een of andere verzameling van labels. De kant-labeling komt vaker voor dan de knoop-labeling.

Als de beeld-verzameling een verzameling van getallen is ( $\Bbb{N}, \Bbb{Z}, \Bbb{Q}, \Bbb{R}, \Bbb{C},$ etc.), dan noemen we de labeling ook wel een weging. De graaf heet dan een gewogen graaf. Een gewogen, gerichte graaf wordt ook wel een netwerk genoemd.

Labeling (en met name weging) wordt 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 geoptimaliseerd wordt.

Stelling : Het aantal gelabelde bomen op v knopen is $v v - 2$
Bewijs : Het bewijs volgt uit de codering van H. Prüfer van knoop-gelabelde bomen.
Deze constructie werkt als volgt:

Van knoopgelabelde boom met v knopen naar Prüferrij ter lengte 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 heb je een Prüferrij ter lengte v-2, door steeds bladeren te verwijderen naar volgorde van grootte.

Van Prüferrij ter lengte v-2 naar knoopgelabelde boom met 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, ..., 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 v knopen, door steeds bladeren toe te voegen naar volgorde van grootte.

Iedere boom op v knopen kan dus eenduidig gecodeerd worden als een rij van lengte v-2. Ieder van deze elementen kan ieder element zijn uit de verzameling $\{1, \ldots, v\}$ . Dat zijn dus $v v - 2$ mogelijke combinaties.

[bewerk] Problemen op Grafen

Kleuren van grafen: de vierkleurenstelling
Routeproblemen:
Stromen:
- Max-flow min-cut stelling

[bewerk] Belangrijke algoritmes op grafen

Dijkstra's algoritme
Kruskals algoritme
Prims algoritme
Hongaarse methode
Naaste-buuralgoritme

[bewerk] Populaire software voor graafvisualisatie

[bewerk] Gerelateerde wiskundige gebieden

[bewerk] Bronnen en referenties

Bronnen en referenties:

Grafentheorie — dictaat van dr. A. Blokhuis, docent aan de TU/e

___

Categorieën: Wikipedia:Etalage-artikelen | Theoretische informatica | Discrete wiskunde | Diagram

Grafentheorie

Van Wikipedia

Inhoud

[bewerk] Definities van grafen

[bewerk] Terminologie

[bewerk] Simpele grafen

[bewerk] Graafcomponenten en de samenhangende graaf

[bewerk] De matrixvoorstelling van een graaf

[bewerk] De boom

[bewerk] Toepassingsgebieden

[bewerk] De complete graaf

[bewerk] De Kliek

[bewerk] De cykel-graaf

[bewerk] Toepassingsgebieden

[bewerk] De Euler-graaf en de Hamilton-graaf

[bewerk] De planaire graaf

[bewerk] De bipartiete graaf

[bewerk] De Petersen-graaf

[bewerk] Graafoperaties, de 2-graaf en geïnduceerde grafen

[bewerk] Gerichte grafen

[bewerk] Enige verschillen ten opzichte van simpele grafen

[bewerk] Gelabelde en gewogen grafen

[bewerk] Problemen op Grafen

[bewerk] Belangrijke algoritmes op grafen

[bewerk] Populaire software voor graafvisualisatie

[bewerk] Gerelateerde wiskundige gebieden

[bewerk] Bronnen en referenties

Views

Navigatie

Informatie

Zoeken

in andere talen