© h.hofstede (h.hofstede@hogeland.nl)

De positie van een schijf.
       
Stel we hebben in één of ander meetsysteem een draaiende schijf waarvan het belangrijk is dat we de stand kunnen aflezen. De rand van de schijf is gecodeerd, er zijn een aantal vakjes (in dit voorbeeld 16) die met geleidend materiaal zijn bedekt of met isolatiemateriaal. Op 4 contactpunten wordt gemeten of het vakje van de schijf geleidend is of niet. Laten we geleidend `1`  noemen en niet/geleidend `0`, zoals je rechtsonder ziet. We lezen in deze stand de code  1-0-0-1  (met de klok mee) af.
       

       
Maar nou komt het probleem:  de positie van de hier getekende schijf is niet eenduidig bepaald als bekend is wat de vier contacten opleveren. Kijk maar hiernaast:  beide rode posities bij de contacten geven de serie 1-0-1-0 dus daar zien we geen verschil tussen. Ofwel:  deze indeling van geleidende en isolerende vlakjes is niet zo handig.

Je snapt de vraag waarschijnlijk al wel:

Is er een nummering te maken die alle verschillende posities eenduidig herkent?

Laten we de vraag even nauwkeuriger formuleren:

Stel dat we 2n  standen van de schijf willen herkennen. Hoe kunnen we dat doen met zo min mogelijk contactpunten?

       
Stel dat we c  contactpunten hebben, dan geven die een binair getal, waarvoor er 2c  mogelijkheden zijn.
Maar de schijf heeft  2n  standen, dus als al die standen een verschillend "contactgetal" moeten opleveren, dan moet gelden  2c  ≥  2n  dus  cn
Het zal zo meteen blijken dat  c = n  lukt!!
 
We maken een digraaf D met als knooppunten de binaire getallen met n - 1 cijfers.
Verder maken we een verbindingslijn vanaf knoop K door van de cijfers van K het meest linkercijfer weg te laten, en aan de rechterkant een 1 of een 0 toe te voegen. De verbindingslijnen lopen dan van knoop K naar de twee knooppunten die bij de twee nieuwe getallen horen.

Bijvoorbeeld:  als n = 5 zijn er 25 = 32 posities.  Graaf D bestaat dan uit de binaire getallen van 4 cijfers (dat zijn dus 16 knooppunten). 
Er loopt vanaf knooppunt  10111 een verbindingslijn naar  01110 en naar 01111.  De voorste 1 gaat weg, en achteraan voegen we een 1 of een 0 toe.

Voor n = 4  (16 posities op de schijf, 8 knooppunten in D)  geeft dat de graaf hiernaast.
Die is duidelijk verbonden en je ziet dat elk punt ingraad 2 en uitgraad 2 heeft.

Maar dan kun je een Eulerroute in de graaf aanleggen!

Voordat we dat gaan doen gaan we eerst alle verbindingslijnen een naam geven. Elke lijn krijgt de naam van het beginknooppunt (eerste drie cijfers) met een 1 of een 0 erachter (vierde cijfer), afhankelijk of er een 1 of een 0 was toegevoegd om het volgende knooppunt te krijgen.
Dat zijn de groene namen in de figuur linksonder.

       
In de figuur ernaast is een blauwe Eulerroute in de graaf getekend (begonnen bij 111), en de groene getallenkolom daar weer naast geeft de namen van de achtereenvolgende verbindingslijnen op die route (van boven naar beneden).  Als je nou de eerste cijfers van die namen van die verbindingslijnen achter elkaar zet, dan krijg je een goede nummering voor de schijf!  In dit geval 1111000011010010. 
Helemaal rechts staat het eindresultaat.
Deze coole toepassing van gerichte Eulerroutes komt overigens van Good (1946).
       
De Bruijn Rijen.
       
De rij op de schijf die we hierboven vonden is een voorbeeld van een "De-Bruijn-Rij"  (genoemd naar de Nederlandse wiskundige Nicolaas Govert de Bruijn). De algemene definitie is:
       

Een de-Bruijn-rij  B(k, n) is een cyclische rij waarin, gegeven een groep van k objecten,
alle mogelijke rijtjes van lengte n precies één keer voorkomen.  

       
Hierboven vonden we dus de rij  B(2, 4)  want we hadden twee objecten (een 1 en een 0) en we bekeken rijtjes van lengte 4. We noemen n ook wel de orde van de rij. En rijen met k = 2 heten heel toepasselijk wel  binaire rijen.
Hierboven zagen we al hoe je zo'n rij uit een graaf kunt maken.
 
Het kan ook met een simpel algoritme:  Het "prefer-one algoritme".

Hoe dat werkt zie je hiernaast.

Voor n = 3 zou dat de volgende serie geven:
     

START
000
0001
00011
000111
0001110
00011101
000111010
0001110100
STOP

Mooi toch?
Ionica Smeets wijdde er toen de Bruijn in 2012 overleed  in de Volkskrant zelfs een column aan....

https://www.volkskrant.nl/archief/wat-er-zo-bijzonder-is-aan-0000111101100101000~a3226643/
       
       

© h.hofstede (h.hofstede@hogeland.nl)