In de wiskunde is een Cayley-graaf een gerichte graaf die de structuur van een groep, meestal een eindige, in beeld brengt. De Cayley-graaf hangt af van een, meestal eindig, aantal voortbrengers van de groep.

Cayley-graaf van de vrije groep met twee voortbrengers en

De Engelse wiskundige Arthur Cayley maakte in 1878 als eerste gebruik van grafen om groepen aanschouwelijk voor te stellen. Dit idee werd door Max Dehn (1911), Otto Schreier (1927) en anderen verder ontwikkeld. Vanwege de grote bijdrage van Dehn wordt een Cayley-graaf ook wel met de door Dehn bedachte naam (Dehnse) groependiagram aangeduid.[1] Tegenwoordig zijn Cayley-grafen een belangrijk hulpmiddel in de meetkundige groepentheorie.

Definitie bewerken

Gegeven zijn een groep   en een systeem   van voortbrengers van  . De Cayley-graaf   van het paar   is een gekleurde en gerichte graaf die als volgt is opgebouwd:

  • Aan elk element   wordt een knoop toegewezen. De verzameling knopen   van   wordt met   geïdentificeerd.
  • Aan elke voortbrenger   wordt een kleur   toegekend.
  • Voor elke   en   worden de knopen die bij de elementen   en   behoren, verbonden door een gerichte kant met de kleur   van de voortbrenger. De verzameling kanten   bestaat dus uit de paren van de vorm  , waarin de voortbrenger   de kleur van de kant bepaalt.

In de meetkundige groepentheorie wordt gewoonlijk verondersteld dat de verzameling voortbrengers   eindig is, 'symmetrisch' is, wat inhoudt dat  , en niet het neutrale element van de groep bevat. In dat geval is de Cayley-graaf, op de kleuren na, een gewone graaf: de kanten zijn niet georiënteerd, en de graaf bevat geen cykels.

Voorbeelden bewerken

 
Een Cayley-graaf van de dihedrale groep  
 
Een andere Cayley-graaf van  
  • Van de oneindige cyclische groep   met de standaard voortbrenger 1 en zijn inverse −1 (in additieve notatie) is de bijbehorende Cayley-graaf een oneindige keten.
  • Het geval met  , de eindige cyclische groep van orde  , is vergelijkbaar met het vorige. Ook nu zijn de standaard voortbrengers 1 en zijn inverse −1 en heeft   twee elementen. De Cayley-graaf is dan de cyclische graaf  .
  • De Cayley-graaf van het directe product van een aantal groepen is het cartesisch product van de respectievelijke Cayley-grafen. De Cayley-graaf van de vrije abelse groep   met de 4 voortbrengers   is een oneindig rooster in het vlak  , terwijl de Cayley-graaf voor de directe producten   is een eindig  -rooster op de torus.
  • De bovenste figuur toont de Cayley-graaf van de dihedrale groep   met twee voortbrengers   (draaiing over 90° met de klok mee) en   (horizontale spiegeling). Aangezien   zijn eigen inverse is, zijn de blauwe kanten, die staan voor het uitvoeren van  , ongericht getekend. Deze keuze van   en   komt overeen met de presentatie
 .
Het verband tussen de groep en de keuze van de voortbrengers ziet men terug in de Cayley-graaf als cykels. Zo levert bijvoorbeeld   een gesloten pad in de graaf.
  • Van de vrije groep met twee voortbrengers   en   staat de Cayley-graaf met de verzameling voortbrengers   eerder in het artikel, waarbij   staat voor hetneutrale element. Op een kant naar rechts gaan komt overeen met rechtsvermenigvuldiging met  , terwijl omhoog gaan vermenigvuldiging met   voorstelt. Omdat de vrije groep geen relaties heeft, zijn er geen cycli in de graaf.

Referenties bewerken

  1. Jonathan L. Gross, Thomas W. Tucker : Topological graph theory. Courier Dover Publications, 2001. ISBN 978-0-486-41741-7. S. 10–14.