Programacion

Solo disponible en BuenasTareas
  • Páginas : 5 (1226 palabras )
  • Descarga(s) : 0
  • Publicado : 8 de noviembre de 2010
Leer documento completo
Vista previa del texto
Diagrama de Hasse
En matemáticas, un diagrama de Hasse es una representación gráfica simplificada de un conjunto parcialmente ordenado finito. Esto se consigue eliminando información redundante. Para ello se dibuja una arista ascendente entre dos elementos solo si uno sigue a otro sin haber otros elementos intermedios.
En un diagrama de Hasse se elimina la necesidad de representar:
*ciclos de un elemento, puesto que se entiende que una relación de orden parcial es reflexiva.
* aristas que se deducen de la transitividad (matemática) de la relación.
Definición
* De dos miembros x e y de un conjunto parcialmente ordenado S que «y sigue a x» si x ≤ y y no hay elemento de S entre x e y.
El orden parcial es entonces precisamente la clausura transitiva de la relación deseguir.
* El diagrama de Hasse de S se define como el conjunto de todos los pares ordenados (x, y) tales que y sigue a x, es decir, el diagrama de Hasse se puede identificar con la relación de seguir.
[editar] Ejemplo
Concretamente, uno representa a cada miembro de S como un punto negro en la página y dibuja una línea que vaya hacia arriba de x a y si y sigue a x.
Por ejemplo, sea el conjuntoA = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (todos los divisores de 60). Este conjunto está ordenado parcialmente por la relación de divisibilidad. Su diagrama de Hasse puede ser representado como sigue:

Por ejemplo, en el diagrama de Hasse del poset de todos los divisores de un número n, ordenados parcialmente por divisibilidad, n mismo está en el tope del diagrama, el número 1 estaríaen el fondo, y los divisores más pequeños (primos) seguirían al elemento inferior.
[editar] Relación con los Grafos
Un diagrama de Hasse puede verse también como un grafo al que se le quitan todos sus bucles y sus aristas que pueden deducirse con la propiedad transitiva y propiedad reflexiva.
[editar] La dificultad de encontrar un buen diagrama de Hasse
Las relaciones "seguir a" quedadefinida de modo único a partir de la relación de orden inicial. Esto hace que las aristas del diagrama de Hasse y los puntos que conectan queden determinados también de forma única. Pero existe un problema adicional: encontrar una ubicación adecuada para los vértices que pueda reflejar alguna de las simetrías subyacentes. En este sentido, encontrar un buen diagrama es difícil.
Se han propuesto variosalgoritmos para dibujo de "buenos" diagramas, pero hoy en día su construcción sigue basándose en una fuerte intervención humana. De hecho, incluso un humano necesita bastante práctica para elaborarlos.
Los siguientes ejemplos corresponden a diagramas de Hasse de una misma relación de orden:
|     | |     | |
En matemáticas, un diagrama de Hasse es un represenación de un conjuntoparcialmente ordenado finito. La represenación se hace mediante un grafo, o sea un diagrama que consta de nodos y aristas, ver la siguiente sección 3
Supongamos que tenemos una relación R en A que es relación de orden. Primeramente sabemos que es reflexiva, antisimétrica y transitiva. Formamos el grafo con los elementos de A, estos son los nodos, y las aristas son conexiones entre nodos relacionados,en este caso es un grafo dirigido. La primera condición es que si dos elementos están relacionados, digamos (a,b) ∈ R entonces dibujamos %blue&b a un nivel superior de a.
Un diagrama de Hasse elimina la necesidad de representar lazos, puesto que se tiene que la relación parcialmente ordenada es reflexiva.
Puesto que la transitividad también está implicada, se puede prescindir de mostrarlíneas entre elementos que tengan un elemento intermedio relacionado, pues se sobrentienden.
Con estos diagramas las relaciones de orden son muy fácil de representar y sobretodo de entender.
Ejemplo1. Consideremos el ejemplo de la sección anterior de los divisores del 40.
A={1,2,4,5,8,10,20,40}, R = D40 la relación divide a.
Si consideramos todas las parejas en la relación tenemos:
D40 =...
tracking img