Diagrama de Hasse

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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 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.[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.

Definição[editar | editar código-fonte]

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.

Exemplos[editar | editar código-fonte]

Hasse diagram of powerset of 3.svg
  • 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:
Lattice of the divisibility of 60.svg

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.

Subconjuntos[editar | editar código-fonte]

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’.):

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

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[editar | editar código-fonte]

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.

Set partitions 4; Hasse sub; numbers.svg     Set partitions 4; Hasse; numbers.svg     Set partitions 4; Hasse flat; numbers.svg

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 hajam 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

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

O Commons possui uma categoria contendo imagens e outros ficheiros sobre Diagrama de Hasse