Grafen

Overzicht  ][  Matrices


0. Overzicht

  1. Definities, het Probleem van Königsberg
  2. Verbindingsmatrix, directe-wegenmatrix
  3. Meerstapsverbindingen

1. Definities, het Probleem van Königsberg

Definities
Een graaf is een figuur bestaande uit een eindig aantal punten (knopen) en een eindig aantal verbindingslijnen (takken - tussen die knopen).
Indien voor elk tweetal knopen geldt, dat het aantal takken daartussen ten hoogste 1 is, dan spreken we van een enkelvoudige graaf.
Indien er in een graaf (ten minste) een tweetal knopen verbonden is door meerdere takken, dan spreken we van een meervoudige graaf.
Indien ieder tweetal knopen verbonden is door precies één tak, dan spreken we van een volledige of maximaal verbonden graaf.
Twee knopen die verbonden zijn door ten minste een tak noemen we buren (of verbonden knopen).
Een tak die dezelfde knoop als begin- en eindpunt heeft, heet een lus.

Bovenstaande definitie is zeker niet afkomstig van de Zwitserse wiskundige Leonard Euler (1707-1783). Maar hij was wel de eerste die een grafentheoretisch probleem oploste.
Het probleem
In het 18e eeuwse Königsberg (Koningsbergen) liggend aan de rivier de Oost-Pruisen, tegenwoordig heet het Kaliningrad en de rivier de Pregola, vroegen de bewoners zich af of het mogelijk zou zijn een wandeling te maken over de vier delen van de stad (waaronder Kneiphoff), die verbonden zijn door zeven bruggen, en wel zo, dat iedere brug receis eenmaal werd gebruikt (zie figuur 1, links).
Omdat hun pogingen steeds faalden, geloofden zij, dat een dergelijke wandeling niet mogelijk was.

figuur 1  graf0.gif (2463 bytes)         graf1.gif (1211 bytes)

Oplossing:
Euler was de eerst die het probleem oploste (publicatie in 1736, "Solutio problematis ad geometriam situs pertinentis").
Via abstractie kan het probleem helder worden gemaakt als in figuur 1, rechts.
Indien een punt, niet zijnde het begin of einde van een wandeling wordt bereikt, dan dient dat punt ook weer te worden verlaten. De "valentie" van de punten (valentie=aantal takken van dat punt, aangegeven met de letter v) met uitzondering van ten hoogste 2 punten, moet dus even zijn.
   v(A) = 5
   v(B) = 3
   v(C) = 3
   v(D) = 3
Hieruit volgt dus dat het probleem niet oplosbaar is.
[einde Oplossing]

2. Verbindingsmatrix, directe-wegenmatrix
We kunnen het al of niet verbonden zijn van de knopen in een graaf vastleggen in een matrix (een rechthoekig schema met getallen), verbindingsmatrix.
Ook het aantal wegen tussen de knopen kunnen we in een matrix vastleggen, directe-wegenmatrix.

2.1. Verbindingsmatrix

Definitie
Bestaat een graaf K uit n knopen A1, A2, ... An, dan heet de bij K behorende nxn-matrix M de verbindingsmatrix van K als
in M geldt
   mij = 0 als Ai en Aj niet verbonden zijn
   mij = 1 als Ai verbonden is met Aj (door tenminste 1 tak).

Opmerkingen
[1]
In het algemeen is Ai niet verbonden met zichzelf. Is dit wel het geval, dan is dus mii = 1. De tak heet in dit geval een lus.
[2]
Indien Ai wel verbonden is met Aj, maar Aj niet met Ai, dan spreken we van een gerichte tak van Ai naar Aj (de tak bestaat in dit geval uit een lijn met een pijl).
In dit geval is dus mij = 1 en mji = 0.
[3]
In sommige leerboeken (voor het voortgezet onderwijs) wordt de richting van de verbinding aangegeven "van kolom naar rij" in plaats van "van rij naar kolom" (zoals in bovenstaande definitie en zoals bedoeld is in Opmerking 2.).
[einde Opmerkingen]

Voorbeeld
We gaan uit van de in figuur 2 staande graaf K. De bijbehorende verbindingsmatrix M staat ernaast. In M zijn, als referentie, de namen van de knopen eveneens opgenomen.

figuur 2
graf2.gif (797 bytes)           graf2b.gif (1425 bytes)

[einde Voorbeeld]

2.2. Directe-wegenmatrix

Definitie
Bestaat een graaf K uit n knopen A1, A2, ... An, dan heet de bij K behorende nxn-matrix M de directe-wegenmatrix van K als.
in M geldt
   mij = aantal takken van Aj naar Aj waarbij ook i = j (voor de lussen) is toegestaan.

Voorbeeld
We gaan uit van de in figuur 3 staande graaf K. De bijbehorende directe-wegenmatrix M staat ernaast. In M zijn, als referentie, de namen van de knopen eveneens opgenomen.

figuur 3
graf3.gif (857 bytes)

[einde Voorbeeld]

3. Meerstapsverbindingen
Via matrixvermenigvuldiging kunnen we het aantal meerstapsverbindingen in een graaf berekenen.

Voorbeeld
We gaan uit van de graaf in figuur 4a. In figuur 4b staan de takken (die alle moeten worden opgevat als eenrichtingsverbindingen) van A,B,C via A,B,C naar A,B,C.

figuur 4a figuur 4b
graf3.gif (857 bytes) graf4.gif (1920 bytes)

We kunnen nu de matrix M2 uit figuur 4b aflezen
   

Stelling
Bij een graaf met n knopen A1, ..., An geeft in de nxn-matrix M n   het element mij het aantal n-stapsverbindingen aan tussen Ai en Aj. Hierin is M de directe-wegenmatrix die bij de graaf K behoort.

begin pagina

[grafen.htm] laatste wijziging op: 26-09-1999