Cayley-graaf
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.

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. Tegenwoordig zijn Cayley-grafen een belangrijk hulpmiddel in de meetkundige groepentheorie.

Definitie 
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 

 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 

Grafentheorie
Groepentheorie