Duale samenhang

Welnee, het flexibele Data Model is helemaal niet uniek voor de "Visualization Data Explorer" van IBM. Wanneer desbetreffende theorie deel zou uitmaken van het reguliere wiskunde onderwijs, dan zouden om te beginnen belachelijke claims van dit soort snel de wereld uitgeholpen worden. Voorzover de aanmatiging van IBM serieus genomen moet worden, gaat het om een veel ernstiger zaak. Voorkomen zou moeten worden dat bedrijven gedwongen zijn om iedere keer opnieuw het wiel uit te vinden. Maar misschien heb ik het wel helemaal bij het verkeerde eind, en is de Theorie van de Samenhang (Engels: "connectivity") een conventioneel onderdeel van de wiskunde, "diskrete topologie" genaamd. Dan hebben we te maken met een heel ander probleem: waarom dringen sommige stukken doodgewone wiskunde blijkbaar dan toch niet door in de toepassingsgebieden waar ze broodnodig zijn?

Neem als eerste voorbeeld een willekeurige landkaart. Concentreer alle aandacht op de zogenaamde drielandenpunten. Voor West Europa kan van de drielandenpunten een lijst worden gemaakt. Hier volgt een klein stukje van deze lijst:

Spanje              Portugal        zee           : 1
Spanje              Portugal        zee           : 2
Frankrijk           Spanje          zee           : 3
Frankrijk           Spanje          zee           : 4
Frankrijk           Belgie          zee           : 5
Frankrijk           Belgie          Luxemburg     : 6
Frankrijk           Duitsland       Luxemburg     : 7
Nederland           Belgie          Duitsland     : 8
Luxemburg           Belgie          Duitsland     : 9
Nederland           Duitsland       zee           : 10

Merk op dat ook het omringende water, de zee, als een "land" wordt opgevat. Verbind nu opeenvolgende nummers aan deze drielandenpunten, zoals we hierboven hebben laten zien. Dan kunnen we ze voor elk van de landen bij elkaar zetten:

1 = Duitsland   :  7  8  9 10
2 = zee         :  1  2  3  4  5 10
3 = Frankrijk   :  3  4  5  6  7
4 = Belgie      :  5  6  8  9
5 = Spanje      :  1  2  3  4
6 = Luxemburg   :  6  7  9
7 = Nederland   :  8 10
8 = Portugal    :  1  2

We kunnen nog verder abstaheren, en (ook) de namen van de landen vervangen door opeenvolgende nummers: Duitsland = 1, zee = 2, ... . Dit geeft een opeenvolging van nummers, in plaats van namen, bij elk drielandenpunt:

Bovenstaande is een voorbeeld van wat in de ingenieurswetenschappen "topologie" of "samenhang" wordt genoemd [OC]. Bijvoorbeeld een stuk van een landkaart kan door middel van een dergelijke samenhang worden gekarakteriseerd. Er zijn bovendien twee manieren om dit te doen: verzamel bij elk drielandenpunt de drie omringende landen, of: verzamel bij elk land alle drielandenpunten die op de grens van dat land liggen. De ene samenhang wordt wel de duale of inverse of omgekeerde samenhang van de andere genoemd.

Het tweede voorbeeld is afkomstig uit de Strukturele Mechanika. Het volgende is onderdeel van een figuur, die is afgekeken uit [OC]:

Wat we hier zien is een samenstel van zogenaamde elementen. De (eindige) elementen (Engels: Finite Elements) zitten aan elkaar vast met hun zogenaamde knooppunten. Zowel de elementen als de knooppunten zijn genummerd. We kunnen twee lijsten maken. De eerste lijst associeert ieder element met de knooppunten die eraan vastzitten:

element  knooppunten
-------  -----------
   1     1  3  4
   2     1  2  4
   3     2  5
   4     3  4  6  7
   5     4  5  7  8

De tweede lijst verbindt ieder knooppunt met de elementen die eraan vastzitten, dat is de duale samenhang:

knooppunt  elementen
---------  ---------
    1      1  2
    2      2  3
    3      1  4
    4      1  2  4  5
    5      3  5
    6      4
    7      4  5
    8      5

Gegeven de eerste lijst, kunnen we altijd de tweede lijst maken, en omgekeerd. Hieronder is opgenomen een Basic programma dat juist deze taak vervult. De naam van het ding is INVERSE.BAS, om redenen die snel duidelijk zullen worden. Een invoer voor dit programma is het bestand TOPOL.DAT, dat in ons geval als volgt is gedefinieerd:

  1  3  4  0
  1  2  4  0
  2  5  0
  3  4  6  7  0
  4  5  7  8  0

De nullen ("0") zijn "sentinel" waarden, dat wil zeggen eind-van-de-regel (EOL) aanduidingen voor het programma. Dit omdat bepaalde eigenschappen van Basic de duisternis tot standaard verheffen. Hier komt het eerste programma-gedeelte:

10 PRINT "Invoer file: ": INPUT I$
20 OPEN I$+".DAT" FOR INPUT AS #1
30 OPEN "EFFE.DAT" FOR OUTPUT AS #2
40 NEL=1
50 INPUT #1,NO : IF EOF(1)<0 THEN 80
60 IF NO=0 THEN NEL=NEL+1 : GOTO 50
70 PRINT #2,NO,NEL : GOTO 50
80 CLOSE #1 : CLOSE #2

De klad-file EFFE bevat de volgende data, hieronder georganiseerd in twee rijen in plaats van twee kolommen (teneinde witruimte te sparen):

   elementen:  1 1 1  2 2 2  3 3  4 4 4 4  5 5 5 5
 knooppunten:  1 2 3  1 2 4  2 5  3 4 6 7  4 5 7 8

Volgt het tweede gedeelte van het programma, niets anders dan een 'system call' naar de standaard SORT procedure in DOS (niet omdat zulks efficiënt is, maar ik wil niet opnieuw het wiel uitvinden):

90 REM
100 SHELL "SORT < EFFE.DAT > EVEN.DAT"
110 SHELL "DEL EFFE.DAT"
120 REM

Dit resulteert in een klad-file EVEN, die de volgende gegevens bevat, geordend wederom in rijen:

knooppunten:  1 1  2 2  3 3  4 4 4 4  5 5  6  7 7  8
  elementen:  1 2  2 3  1 4  1 2 4 5  3 5  4  4 5  5

Tenslotte worden de data in EVEN gekonverteerd naar hun uiteindelijke formaat: de file DUAL. Dit wordt gerealiseerd door het volgende programma-fragment:

130 OPEN "EVEN.DAT" FOR INPUT AS #1
140 PRINT "Uitvoer file: ": INPUT O$
150 OPEN O$+".DAT" FOR OUTPUT AS #2
160 NOW=1
170 INPUT #1,NO,NEL
180 IF NOW<>NO THEN PRINT #2,"0" : NOW=NO
190 PRINT #2,NEL; : IF EOF(1)=0 THEN 170
200 PRINT #2,"0" : CLOSE #1 : CLOSE #2
210 SHELL "DEL EVEN.DAT" : END

De inhoud van de file DUAL.DAT wordt hieronder gegeven. De nullen ("0") dienen weer als eind-van-de-regel markering.

  1  2  0
  2  3  0
  1  4  0
  1  2  4  5  0
  3  5  0
  4  0
  4  5  0
  5  0

De procedure als geheel suggereert een aantal dingen:

Misschien kan wel ieder paar rijen van natuurlijke getallen (Engels: integer arrays) worden opgevat als de definitie van een diskrete topologie.
Het bepalen van de duale samenhang is een SORTeer probleem, met de andere rij als sleutel.
De etiketten "knooppunt" en "element" zijn, bezien vanuit wiskundig oogpunt, onderling volkomen verwisselbaar.

De TOPOL file komt overeen met "welke knooppunten bij een element behoren", terwijl de "DUAL" file overeenkomt met "welke elementen bij een knooppunt behoren". Wanneer we het programma draaien met DUAL in plaats van TOPOL als invoer file, dan zal TOPOL resulteren als uitvoer file. We kunnen dit gedrag symbolisch samenvatten als:

    INVERSE(TOPOL) = DUAL   ;   INVERSE(DUAL) = TOPOL

Dus, het INVERSE programma is in feite de daad van het omgekeerde bepalen op zich zelf: $ INVERSE() \equiv ()^{-1} $. We kunnen daarom ook schrijven: $$ (\mbox{TOPOL})^{-1}=\mbox{DUAL} \qquad ; \qquad (\mbox{DUAL})^{-1}=\mbox{TOPOL} $$ $$ (( \mbox{samenhang} )^{-1} )^{-1} = \mbox{samenhang} $$