Grafentheorie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
6n-graf.svg

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, kanten of takken. 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 worden gemodelleerd. 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 bogen in deze grafen, maar eerder op de statistische eigenschappen van grootschalige netwerken.

Definitie[bewerken]

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) 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, kanten of takken 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 één zijde zijn verbonden. Een graaf G = (V,E) is dan een geordend paar van een verzameling V en een multiset E van paren deelverzamelingen van V:

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

, de knopen van G
, de kanten van G

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

Terminologie[bewerken]

  • Noteer dat twee knopen met elkaar zijn verbonden met een tilde, bijvoorbeeld .
  • Een knoop k heet ook verbonden met een kant e als k een begin- of eindpunt van e is
  • Een wandeling tussen twee verbonden knopen a en b is een serie verbonden knopen, waarvan a het begin en b het einde is:
In een ongewogen graaf is de lengte van een wandeling het aantal knopen in de wandeling.
  • Een graaf heet samenhangend, wanneer er tussen alle punten in de graaf een wandeling mogelijk is.
  • Een pad tussen twee verbonden knopen a en b is een wandeling tussen a en b waarin geen punt meer dan eenmaal voorkomt.
  • De afstand tussen twee knopen a en b, notatie: d(a,b), is de lengte van het kortste pad tussen a en b. Wanneer er geen wandeling mogelijk is van a naar b heeft het geen zin over de afstand tussen a en b te spreken.
  • De diameter van een samenhangende graaf G is de maximale lengte van het kortste pad tussen twee knopen in G.
  • Een cykel in een graaf G is een pad van een knoop a naar a.
  • De taille van een samenhangende graaf is de lengte van de kortste cykel in de graaf.
  • De graad van een knoop k, notatie deg(k), is het aantal kanten waarmee k incident is.
  • Indien alle knopen dezelfde graad g hebben wordt de graaf g-regulier genoemd. Een graaf heet regulier als er een getal g bestaat, zodat hij g-regulier is.
  • Twee grafen en zijn isomorf als de ene graaf ontstaat uit de andere alleen door de namen van de knopen te veranderen. Meer formeel is er dan een bijectie zodanig dat dan en slechts dan als .
  • Een partitie van een graaf G is een verdeling van in een aantal deelverzamelingen zodanig dat

Enkelvoudige grafen[bewerken]

De enkelvoudige graaf is de meest gebruikte soort graaf. Het is een graaf waarin de zijden altijd tussen twee knopen lopen en waarin niet meer dan één zijde tussen twee knopen voorkomt.

6n-graf.svg

De enkelvoudige graaf vindt veel toepassing binnen de wiskunde en de informatica. Over deze grafen zijn een groot aantal verschillende stellingen bewezen.

Componenten en de samenhangende graaf[bewerken]

Een graaf, die bestaat uit twee componenten.

Binnen een enkelvoudige ongerichte graaf is een component een verzameling van knopen van de graaf die onderling zijn verbonden: een component C van graaf G is met

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

De matrixvoorstelling van een graaf[bewerken]

We kunnen een graaf eenvoudig voorstellen in een matrix, de bogenmatrix. Dit is een vierkante matrix met dimensie n*n, waarbij n het aantal knopen in de graaf is. Het element in de bogenmatrix A is 1 als er een zijde (boog) bestaat die van i naar j gaat en 0 als dit niet het geval is.

Gelabelde graaf Bogenmatrix
6n-graph2.svg

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

De boom[bewerken]

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 heeft kanten

Bewijs

Het bewijs gaat met de methode van de volledige inductie.

Met maar één knoop zijn er geen zijden en is de stelling waar,
Vorm nu een grotere graaf.
Een nieuwe knoop is via precies één zijde met de al gevormde graaf verbonden, wanneer de graaf met twee zijden met de gevormde graaf wordt verbonden, ontstaat een cykel.
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

De cykelgraaf[bewerken]

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

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[bewerken]

De volledige graaf met n knopen is de graaf waarin alle punten onderling verbonden zijn.

De volgende grafen zijn voorbeelden van volledige grafen:

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg
De volledige grafen .

Het aantal kanten van is , het n-1e driehoeksgetal.

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) kanten 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 enkelvoudige graaf tenslotte ook een kant van b naar a. Dus hebben we maar de helft nodig: .

Een clique of 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.

Euler en Hamilton[bewerken]

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 Euler-wandeling, 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

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

Stel, er zijn twee gesloten wandelingen, dus cykels, allebei zonder dubbel gebruikte kanten, die niet een kant maar wel een knoop k gemeen hebben. Die cykels kunnen aan elkaar geplakt 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. 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.
Complete graph K3.svg Complete graph K5.svg Königsberg graph.svg
De - en -grafen 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

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

Zoek de twee knopen met oneven graad, als die er zijn, trek er een fictieve kant tussen. Nu zijn de graden van alle knopen even, dus is er een Eulercykel. Haal de fictieve kant weer weg, een Eulercykel minus één kant is een Euler-wandeling.

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:

Als voor elk tweetal knopen met geldt dat dan bevat G een Hamiltoncykel.

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 de Eulercykel waar het probleem in polynomiale tijd kan worden opgelost dankzij de bovengenoemde regels. Een Hamiltoncykel is een simpel 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[bewerken]

De planaire graaf[bewerken]

Planaire of vlakke grafen zijn grafen die op een plat vlak kunnen worden getekend zonder daarbij de kanten van de graaf elkaar te laten snijden.

Complete graph K3.svg Complete graph K5.svg
De -graaf is planair; de -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 planair is.

Ook over planaire grafen heeft Leonhard Euler nagedacht, hij vond de stelling van Euler. Deze stelling is gebaseerd op het aantal knopen, kanten en gebieden van een graaf. Een gebied is het deel van het papier waarop de graaf is getekend, of anders het deel van de graaf dat geheel door kanten of door buitenste knopen van de graaf wordt omgeven. 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.

Graaf gebieden.png

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

Bewijs

Het bewijs gaat met inductie naar . Omdat G samenhangend is, geldt altijd .

nulhypothese: , de graaf is een boom
De graaf G bevat geen cykels; het aantal gebieden is dus 1. , dus .
inductiestap: Neem aan dat voor geldt dat voor alle vlakke grafen met v-e+f=2 hebben. We moeten bewijzen dat voor een willekeurige vlakke graaf met 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 , en dus vanwege de inductiehypothese. Hieruit kunnen we afleiden dat , 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.

Zij G een samenhangende, planaire graaf met v knopen en e kanten en . Dan geldt .

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 , het aantal vierhoekige , het aantal vijfhoekige enzovoorts, dan kunnen we het aantal muren ook op een andere manier tellen: . Oftewel
Dus we weten ook .
Dus

Met deze informatie in de hand, kunnen we zo narekenen dat bijvoorbeeld 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 . Hiermee is ook het puzzeltje opgelost: is niet planair.

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

De bipartiete graaf[bewerken]

Een voorbeeld van een bipartiete graaf

Een bipartiete graaf G is een graaf zodanig dat


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 een van beide verzamelingen leeg is, of zelfs allebei, zodat ook een graaf op 0 of 1 knoop bipartiet is.

Eveneens is duidelijk dat 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 dat deze niet bipartiet zijn, sterker nog:

Een graaf G is bipartiet G bevat geen oneven cykels

Bewijs

Stel, G is bipartiet. Alle kanten van 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.

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 plaatsen, de volgende in , de volgende weer in , enzovoorts, en de laatste in 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 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.

De Petersengraaf[bewerken]

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 bevat: als we de buitenste "ring" van knopen en de binnenste "ring" samentrekken, vinden we de -graaf. We kunnen dan ook duidelijk zien dat de Petersengraaf niet planair is.

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

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 geïnduceerde graaf is een paar met

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 van is het paar (, ) met
=

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 met

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 kunnen we ook de vereniging en het cartesisch product definiëren. De vereniging van G en H is de graaf G ∪ H met

Het cartesisch product van twee grafen.

Het cartesisch product van G en H is de graaf met

oftewel de knopen van zijn de paren van knopen van G en H en deze knopen zijn verbonden door kanten als een van de knopen in de twee paren dezelfde zijn en de andere verbonden waren.

V.l.n.r.: , , en .

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

Gerichte grafen[bewerken]

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

V een verzameling knopen ()
E een verzameling kanten:

Het verschil met de enkelvoudige 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 de richting is het normaal om bij een gerichte graaf de kanten 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 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[bewerken]

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 k: het aantal kanten
  • uitgraad van een knoop k: het aantal kanten

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

Een gerichte graaf heet samenhangend als er voor iedere partitie een kant loopt van naar of omgekeerd. Loopt er altijd een dergelijke kant 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[bewerken]

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

Deze functies voegen aan iedere kant ,of knoop, in het geval van g, een element toe uit een of andere verzameling symbolen. Kanten labelen komt meer voor dan de knopen labelen.

Als de beeld-verzameling een verzameling van getallen is ( 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 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

Bewijs

Het bewijs volgt uit de codering van 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 is er een Prüferrij ter lengte v-2, door steeds bladeren te verwijderen naar volgorde van grootte.

Tree graph Prufer code step 1.svg Tree graph Prufer code step 2.svg Tree graph Prufer code step 3.svg Tree graph Prufer code step 4.svg Tree graph Prufer code step 5.svg

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

Prufer graph construction step 1.svg Prufer graph construction step 2.svg Prufer graph construction step 3.svg Prufer graph construction step 4.svg Prufer graph construction.svg

  • 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 . Dat zijn dus mogelijke combinaties.

Hypergrafen[bewerken]

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[bewerken]

Belangrijke algoritmes op grafen[bewerken]

Gerelateerde wiskundige gebieden[bewerken]

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