# Diagrama de Hasse

Em teoria da ordem, um ramo da matemática que estuda várias clases de relações binárias, um diagrama de Hasse (alemão: /ˈhasə/) é um tipo de diagrama matemático utilizado para representar um conjunto parcialmente ordenado finito, na forma de um grafo de sua redução transitiva. A redução transitiva de uma relação binária $R$ em um conjunto X é a relação mínima $R'$ em X tal que o fecho transitivo de $R'$ é o mesmo que o fecho transitivo de $R$.
Diagramas de Hasse foram assim denominados em referência a Helmut Hasse (1898–1979); de acordo com Birkhoff (1948), eles são assim chamados por causa do uso efetivo que Hasse fez deles. Entretanto, Hasse não foi o primeiro a utilizar estes diagramas; eles apareceram, e.g., em Vogt (1895). Embora os diagramas de Hasse tenham sido criados inicialmente para possibilitar o desenho à mão de conjuntos parcialmente ordenados, recentemente foram feitos automaticamente utilizando técnicas para desenho de grafos.
A expressão "Diagrama de Hasse" pode também se referir à redução transitiva como um grafo orientado acíclico abstrato, independentemente de qualquer desenho do grafo, mas este uso é evitado aqui.

## Definição

Dois membros x e y de um conjunto parcialmente ordenado (S, ≤) são tais que «y cobre x» se x ≤ y e não há z tal que x ≤ z ≤ y. Para um conjunto parcialmente ordenado (S, ≤), um diagrama de Hasse é um grafo onde:
* Cada vértice representa cada elemento de S;
* Cada aresta sobe de x até y sempre que «y cobre x»;
Estas curvas podem se cruzar, mas não devem tocar outros vértices além daqueles que está ligando. Tal diagrama, com vértices nomeados, determina unicamente esta ordem parcial.

## Exemplos

* O conjunto potência de { x, y, z } parcialmente ordenado por inclusão, tem o diagrama de Hasse:
* O conjunto A = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } de todos os divisores de 60, parcialmente ordenado por divisibilidade, tem o diagrama de Hasse:

## Um bom diagrama de Hasse

Embora diagramas de Hasse sejam ferramentas simples e intuitivas para lidar com posets finitos, desenhar bons diagramas de Hasse se mostra uma tarefa dificil. O motivo é que em geral existirão muitas maneiras possíveis para se desenhar um diagrama de Hasse para um dado poset. A simples técnica de começar com os elementos minimais de uma ordem e então adicionar elementos maiores incrementalmente frequentemente produz resultados pobres: simetrias e estruturas internas da ordenação são facilmente perdidas.

### Subconjuntos

O exemplo seguinte mostra o problema. Considere o conjunto das partes ${\mathcal {P}}(S)$ do conjunto S = {a, b, c, d}, i.e. o conjunto de todos os subconjuntos de S, ordenado pela relação de inclusão $\subseteq$. Abaixo estão três diagramas de Hasse diferentes para esta ordem parcial (Note que cada subconjunto S’ tem o vértice nomeado com uma codificação 1-0 de para cada um dos quatro elementos, sendo ('1') se está ou ('0') se não está presente em S’.):
O diagrama mais a esquerda deixa claro que o conjunto das partes é um poset graduado. O diagrama do meio tem a mesma estrutura graduada, mas ao fazer algumas arestas maiores do que outras ele dá enfase na construção do conjunto das partes como a união de dois cubos tridimensionais: os vértices do cubo abaixo (esquerda) representam subconjuntos que não contém um elemento particular (digamos d) de S, enquanto que o de cima (direita) representa os subconjuntos que contém d. O diagrama mais a direita mostra algumas das simetrias internas da estrutura.

### Partições

O diagrama de Hasse seguinte também mostra as partições de um conjunto com quatro elementos, ordenados pela relação de refinamento. O diagrama da esquerda enfatiza o fato dos elementos 0...4 formarem uma reticulado. Todo o reticulado não é simplesmente um semirreticulado dobrado como no exemplo do hipercubo acima. O segundo diagrama é simétrico refletido. As arestas no meio seriam todas verticais, mas para torná-las discrimináveis elas estão desenhadas levemente curvadas. O terceiro diagrama enfatiza a estrutura graduada do reticulado. Todos os elementos com o mesmo rank estão no mesmo nível do diagrama de Hasse, mas muito da simetria está perdida.

## Planaridade para cima

Se uma ordem parcial pode ser desenhada em um diagrama de Hasse sem que haja duas arestas que se cruzem, este grafo de cobertura é dita ser um grafo planar. Um número de resultados sobre um diagrama de Hasse planar para cima e livre de cruzamentos são conhecidos:
* Se a ordem parcial a ser desenhada é um reticulado, então ela pode ser desenhada sem cruzamentos de arestas se e somente se a dimensão da ordem for no máximo dois. Neste caso, um desenho sem cruzamentos pode ser encontrado derivando-se as Coordenadas Cartesianas dos elementos a partir de suas posições, e então rotacionando o desenho no sentido contrário ao do relógio um ângulo de 45 graus.
* Se a ordem parcial tem no máximo um elemento minimal, ou no máximo um elemento máximal, então pode ser verificado em tempo linear se ela tem um diagrama de Hasse sem cruzamentos.
* É um problema NP-completo determinar se uma ordem parcial com multiplos elementos minimais e maximais pode ser desenhado em um diagrama de Hasse sem cruzamento de arestas. Entretanto, achar um cruzamento em um diagrama de Hasse é tratável com parâmetro fixo quando parametrizado pelo número de pontos de articulaçãoe componentes triconectados da redução transitiva da ordem parcial.
* Se as coordenadas y dos elementos de uma ordem parcial são especificados, então um diagrama de Hasse livre de cruzamentos com respeito a estas atribuições pode ser encontrado em tempo linear, se tal diagrama existir. Em particular, se o poset é graduado, é possível determinar em tempo linear quando existe um diagrama de Hasse livre de cruzamentos no qual o peso de cada vértice é proporcional a seu rank.