Diagrama de Hasse

De Viquipèdia
Dreceres ràpides: navegació, cerca
Elements de P (P (P (P ({})))) en Diagrama de Hasse.

En matemàtiques, un diagrama de Hasse és una representació gràfica simplificada d'un conjunt parcialment ordenat finit. Això s'aconsegueix eliminant informació redundant. Per a això es dibuixa una aresta ascendent entre dos elements només si un segueix a un altre sense haver altres elements intermedis.

En un diagrama de Hasse s'elimina la necessitat de representar:

  • Cicles d'un element, ja que s'entén que una relació d'ordre parcial és reflexiva.
  • Arestes que es dedueixen de la transitivitat de la relació.

Definició[modifica | modifica el codi]

  • De dos membres x i i d'un conjunt parcialment ordenat S que « i segueix ax " si xi i no hi ha element de S entre x i i .

L'ordre parcial és llavors precisament la clausura transitiva de la relació de seguir .

  • L ' diagrama de Hasse de S es defineix com el conjunt de tots els parells ordenats ( x , i ) tals que i segueix x , és a dir, el diagrama de Hasse es pot identificar amb la relació de seguir .

Exemple[modifica | modifica el codi]

Concretament, un representa a cada membre de S com un punt negre a la pàgina i dibuixa una línia que vagi cap amunt de x a i si i segueix x .

Per exemple, sigui el conjunt A ={1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}(tots els divisors de 60). Aquest conjunt està ordenat parcialment per la relació de divisibilitat. El seu diagrama de Hasse pot ser representat de la manera següent:

Diagrama de Hasse

Per exemple, en el diagrama de Hasse del Poset de tots els divisors d'un nombre n , ordenats parcialment per divisibilitat, n mateix està en el límit del diagrama, el número 1 estaria en el fons, i els divisors més petits (cosins) seguirien a l'element inferior.

Relació amb els Grafs[modifica | modifica el codi]

Un diagrama de Hasse es pot veure també com un graf al qual se li lleven tots els seus bucles i els seus arestes que poden deduir amb la propietat transitiva i propietat reflexiva.

La dificultat de trobar un bon diagrama de Hasse[modifica | modifica el codi]

Les relacions «seguir» queda definida de manera única a partir de la relació d'ordre inicial. Això fa que les arestes del diagrama de Hasse i els punts que connecten quedin determinats també de forma única. Però hi ha un problema addicional: trobar una ubicació adequada per als vèrtexs que pugui reflectir alguna de les simetries subjacents. En aquest sentit, trobar un bon diagrama és difícil.

S'han proposat diversos algorismes per a dibuix de «bons» diagrames, però avui dia la seva construcció segueix basant-se en una forta intervenció humana. De fet, fins i tot un humà necessita bastant pràctica per elaborar-los.

Els següents exemples corresponen a diagrames de Hasse d'una mateixa relació d'ordre:

Hipercub 4-D, segons la distància des d'una cantonada Projecció de l'hipercub 4-D Projecció per arestes de l'hipercub

Nota[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Diagrama de Hasse Modifica l'enllaç a Wikidata