] >
Het kan wenselijk zijn dat de ribben van een graaf een richting hebben. In het puzzeltje met het schuiven van blokjes op een veld van bij is dat niet nodig, omdat je steeds terug kunt schuiven. Hetzelfde is het geval bij de Toren van Hanoi. Bij het bekende spel solitair is het niet zo: bij iedere zet verdwijnt er een stuk en het doel van het spel is om er uiteindelijk slechts één over te houden. Wil je daar een graaf van maken, dan zou je als hoekpunten de mogelijke toestanden van het spel kunnen nemen en door ribben aangeven hoe men in één zet van toestand verandert. Het abstracte begrip is heel eenvoudig:
5.51 Definitie. Een gerichte graaf is een eindige verzameling tezamen met een deelverzameling van . De elementen van heten de hoekpunten en de elementen van de ribben van de gerichte graaf.
Eigenlijk is een gerichte graaf dus niets anders dan een relatie in een eindige verzameling. Het gebruik van het woord graaf is dus in feite niet meer dan een aanbeveling om je er iets meetkundigs bij voor te stellen. Het is een uitnodiging om op een speciale manier naar de relatie te kijken.
5.52 Voorbeeld. Figuur 5.6 is een plaatje van een gerichte graaf die gemaakt is bij een sterk vereenvoudigd solitair spel, nl. het spel dat wordt gespeeld op het bord en waarbij de beginstand is . Er zijn standen mogelijk; alleen de standen die bereikt kunnen worden vanuit de beginstand zijn aangegeven.
5.53 Voorbeeld. In de verzameling zijn er relaties. Elk van die relaties kun je zien als een gerichte graaf met de hoekpunten en . Het aantal ribben van zo’n graaf is hooguit . In Figuur 5.7 zijn alle relaties aangegeven (als deelverzamelingen van ) tezamen met de bijbehorende gerichte graaf.
Voor iedere hebben we een gerichte graaf . Is bovendien de grafiek van een transformatie van , dan is het plaatje van deze transformatie ook het plaatje van de gerichte graaf. Het is het bijzondere geval, waarbij er bij iedere precies één ribbe van de vorm is.
Is een ordening, dan maken we liever een ander plaatje, namelijk het Hassediagram: omdat de richting van de pijlen van beneden naar boven gaat, laten we de pijlpunt weg en verder laten we ribben weg op grond van de transitiviteit van de ordening.
Is een equivalentierelatie, dan laten we in een plaatje alle ribben weg en geven alleen de equivalentieklassen aan. Binnen een equivalentieklasse zijn alle geordende paren ook ribben.