Wendy

REPUBLICA BOLIVARIANA DE VENEZUELA.

MINISTERIO DEL PODER POPULAR PARA LA DEFENSA.

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITECNICA

DE LA FUERZA ARMADA.

NÙCLEO – MIRANDA

EXTENSIÒN SANTA TERESA DEL TUY.







ORDENAMIENTO DE LOS ELEMENTOS.







MATERIA: TEORIA DE GRAFOS INTEGRANTES:

ING:SANTA TERESA DEL TUY, 15/06/2012

Introducción.















































Ordenamiento de loselementos.



Ordenación parcial.

Un orden es una relación binaria especial. Por lo que tenemos algún conjunto P y una relación binaria ≤ en P. Entonces ≤ es un orden parcial si es reflexiva, antisimétrica, y transitiva, es decir, para todo a, b y c en P, tenemos que:

a ≤ a (reflexividad)

si a ≤ b y b ≤ c entonces a ≤ c (transitividad)

si a ≤ b y b ≤ a entonces a = b, (antisimetría).Conjunto parcialmente ordenado

Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado o poset, un conjunto parcialmente ordenado (c.p.o.) es un par (X,≤) donde ≤ es un orden parcial en X.

Comúnmente se usa la notación de "≤" en lugar de "R" para el orden parcial.

Si (X, ≤) es un c.p.o., dos elementos x, y X son comparables si x≤y o y≤x. ∈

Si todos lospares de elementos de X son comparables entonces se dice que ≤ es un orden lineal (o total) y que (X, ≤) es un conjunto linealmente ordenado.

to linealmente ordenado.

Ejemplos:

• El conjunto de los naturales con su orden usual (la relación menor o igual). Este

orden es además un orden total.

• El conjunto de los enteros con su orden usual. Este orden es también total.

• Unsubconjunto finito {1, 2,..., n} de los naturales. Este orden es también total.

• El conjunto de naturales ordenado por la relación de divisibilidad.



Diagrama de Hasse

El diagrama de Hasse de un conjunto ordenado finito es una representación del mismo en la que cada elemento se representa por un punto del plano. Esto se consigue eliminando información redundante. Para ello se dibuja unaarista 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 de la relación.





Por ejemplo, sea el conjunto A = {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:

[pic]

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úmero1 estaría en el fondo, y losdivisores más pequeños (primos) seguirían al elemento inferior.

Tipos especiales de orden



Muchas de las estructuras estudiadas en teoría de orden emplean relaciones con propiedades adicionales, algunas relaciones que no son de orden parcial son de especial interés. Principalmente, el concepto de preorden

Un preorden es una relación que es reflexiva y transitiva, pero no necesariamenteantisimétrica. Cada preorden induce una relación de equivalencia entre elementos, donde a es equivalente a b, si a ≤ b y a ≥ b. Los preórdenes pueden ser convertidos en órdenes identificando todo elemento equivalente con respecto a esta relación.

Tipos básicos de órdenes especiales ya se dieron en forma de orden total. Una simple pero útil propiedad adicional conduce al, así llamado, buen...