Saltar para o conteúdo

Diagrama de Hasse

Origem: Wikipédia, a enciclopédia livre.
Elementos de P( P( P(P({})))) em 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 em um conjunto X é a relação mínima em X tal que o fecho transitivo de é o mesmo que o fecho transitivo de .

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.[1]

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.

Dois membros x e y de um conjunto parcialmente ordenado (S, ≤) são tais que «y cobre x» se xy e não há z tal que xzy. 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.

  • 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

[editar | editar código-fonte]

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.

O exemplo seguinte mostra o problema. Considere o conjunto das partes do conjunto S = {a, b, c, d}, i.e. o conjunto de todos os subconjuntos de S, ordenado pela relação de inclusão . 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.

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

[editar | editar código-fonte]
Este diagrama de Hasse reticulado de subgrupos de um Grupo diedral Dih4 não possui arestas que se cruzam.

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.[2] 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.[3]
  • 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.[4] 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.[5]
  • 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.

Notas

Ligações externas

[editar | editar código-fonte]
O Commons possui uma categoria com imagens e outros ficheiros sobre Diagrama de Hasse