Hasse-diagram

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een Hasse-diagram is in de wiskunde een grafische voorstelling van een eindige, partieel geordende verzameling. Het diagram is genoemd naar de Duitse wiskundige Helmut Hasse (1898–1979). In het diagram worden de elementen van de verzameling getekend als punten en de ordeningsrelatie weergegeven door twee elementen die elkaars directe opvolger en voorganger zijn, te verbinden door een lijn en de grotere van de twee hoger te tekenen dan de kleinere. Dus als x < y en er is geen element tussen deze twee, zodat x een directe voorganger is van y, wordt y hoger dan x geplaatst en beide door een lijn verbonden. Op deze manier ontstaat een overzichtelijke voorstelling van de ordening. Zouden we alle vergelijkbare elementen verbinden, dan zou door de veelheid van lijnen vaak een onoverzichtelijke wirwar ontstaan.

Voorbeelden[bewerken]

De verzameling V = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } van alle delers van het getal 60, is partieel geordend door de relatie "deelbaar door". Het Hasse-diagram staat hieronder.

Hasse-diagram van de delers van 60

De verzameling van alle partities van de verzameling { 1, 2, 3, 4 } is partieel geordend door de relatie "verfijning", dat wil zeggen een partitie is "fijner" als minstens een van de deelverzamelingen uit de partitie verder opgedeeld is. Het Hasse-diagram staat hieronder.

Hasse-diagram van de partities van {1,2,3,4}

Wat is een goed Hasse-diagram?[bewerken]

Op het eerste gezicht lijkt het niet ingewikkeld een Hasse-diagram te tekenen. Het blijkt echter tamelijk moeilijk een goed diagram te maken. Er zijn voor een gegeven partieel geordende verzameling namelijk (oneindig) veel mogelijkheden voor een Hasse-diagram. Sommige daarvan belichten het ene aspect, zoals interne symmetrieën, andere tonen beter een bepaalde structuur. Het volgende voorbeeld laat het probleem duidelijk zien.

Van de verzameling {a,b,c,d} is de machtsverzameling, die bestaat uit de 16 deelverzamelingen, een partieel geordende verzameling door de relatie "deelverzameling". Hieronder staan drie belangrijke manieren om daavan een Hasse-diagram te tekenen.

Hypercubeorder binary.svg     Hypercubecubes binary.svg     Hypercubestar binary.svg

De deelverzamelingen zijn niet met name genoemd, maar zijn eenvoudig te herkennen. Het linker diagram is waarschijnlijk de meest voor de hand liggende voorstelling. De vijf lagen in het diagram vertegenwoordigen de aantallen elementen in de deelverzamelingen. Het middelste diagram toont twee kubussen waarin een bepaalde interne structuur benadrukt wordt. Het rechter diagram toont beter de interne symmetrie.

Er zijn verschillende algoritmen bedacht om betere diagrammen te tekenen, maar tot nu toe is menselijke hulp daarbij onontbeerlijk en ook dan is praktische ervaring beslist nodig.

Zie ook[bewerken]

Externe links[bewerken]