Taller

Solo disponible en BuenasTareas
  • Páginas : 6 (1491 palabras )
  • Descarga(s) : 0
  • Publicado : 4 de septiembre de 2012
Leer documento completo
Vista previa del texto
Grafos: ordenamiento
topológico y
conectividad
Diseño y Análisis de Algoritmos
Cátedra de Programación
Carrera de Ingeniería de Sistemas
Prof. Isabel Besembel Carrera

Orden parcial
Un orden parcial es una relación reflexiva, antisimétrica y
transitiva.
Dominio: es un conjunto de valores
Ejm: D1 = {‘rojo’, ‘verde’, ‘negro’, ‘azul’}
D2 = {‘ford’, ‘chevrolet’, ‘fiat`, ‘toyota’,‘renault’}

Relación: es un subconjunto del producto cartesiano de
una lista de dominios, no necesariamente disjuntos.
Ejm: R1 = {(‘rojo’, ’ford’), (‘verde’, ’ford’), (‘negro’, ‘chevrolet’), (‘azul’,
‘toyota’)}
R2 = {(‘fiat’, ‘verde’)}
R3 = { }
Abril, 2005

Prof. Isabel Besembel. Cátedra de Programación. Diseño y Análisis de Algoritmos.

2

Propiedades de las
relaciones
Reflexividad: Unarelación R es reflexiva si X R X
para todo X en S.
X

Simetría: Una relación R es simétrica si X R Y
implica Y R X para todo X y Y.
X

Y

Antisimetría: Una relación R es antisimétrica, si X R
Y y Y R X implica X = Y, para todo X y Y.
La relación ≤ es antisimétrica, x ≤ p y p ≤ x implica que x=p
Abril, 2005

Prof. Isabel Besembel. Cátedra de Programación. Diseño y Análisis deAlgoritmos.

3

Propiedades de las
relaciones
Transitividad: Una relación R es transitiva si X R Y
y Y R Z implica que X R Z, para todo X, Y, Z.
a

b

c

d

La importancia de la teoría de las relaciones es que
está relacionada con cualquier tipo de grafo.
Un orden parcial (toda relación antisimétrica y
transitiva) tiene un digrafo acíclico
Abril, 2005

Prof. Isabel Besembel.Cátedra de Programación. Diseño y Análisis de Algoritmos.

4

Ordenamiento topológico
Para un digrafo acíclico (dag) G = (N, A) el orden
lineal de todos los nodos tal que si G contiene el
arco (u, v), entonces u aparece antes de v en el
orden dado.
Si G tiene ciclos el orden lineal no es posible.
Ordenamiento topológico de todos los nodos de un
digrafo es una manera de visitar todos susnodos,
uno por uno, en una secuencia que satisface una
restricción dada.
Abril, 2005

Prof. Isabel Besembel. Cátedra de Programación. Diseño y Análisis de Algoritmos.

5

Ejemplo
PR1

PR2

AC

PR3
DAA

CA10

CA20

CA30

CA40

FI11

FI21

MD

LFI21

Un orden topológico de los nodos de un digrafo
G={N, A} es una secuencia (n1, n2, …, nk) tal que
N= {n1, n2, …, nk} ypara todo (ni, nj) en N, ni
precede a nj en la secuencia.
Abril, 2005

Prof. Isabel Besembel. Cátedra de Programación. Diseño y Análisis de Algoritmos.

6

Aplicaciones
Modelado de actividades para resolver problemas de
planificación o programación de las mismas siguiendo un
criterio de minimización o maximización.
Evaluación de expresiones aritméticas
(- b + sqrt( b * b - 4 * a *c)) / 2 * a
( - b - sqrt(b * b - 4 * a * c)) / 2 * a
2
/

*
+

/
Abril, 2005

-

a

b

sqrt

b
*

b

*

Prof. Isabel Besembel. Cátedra de Programación. Diseño y Análisis de Algoritmos.

*
4

a
c
7

Teorema (Szpilrajn, 1930)
En cualquier grafo G con n≥1 nodos hay un nodo con
grado de incidencia negativo (gin) igual a cero
Demostración: por contradicción
Sitodos los nodos del digrafo G tienen un gin de al menos 1, entonces
G contiene ciclos
Asuma que todos los nodos tienen un gin de al menos 1
Se comienza con cualquier nodo n1, se traza hacia atrás a lo largo de
cualquier arista que incide en n2.
Desde n2 hasta n3 y así sucesivamente
Como todos los nodos tienen un gin de al menos 1, este proceso
nunca acaba, pero como G es finito, eventualmenteun nodo debe
ser alcanzado cuando ya se ha pasado por él, por lo que G tiene
ciclo
Abril, 2005

Prof. Isabel Besembel. Cátedra de Programación. Diseño y Análisis de Algoritmos.

8

Algoritmo genérico de
ordenamiento topológico
Abril/05
ordenTopologico( ): Lista
{pre: n > 0 }

{pos: n = 0 }

1 ( n > 0 ) [ v = nodo con gin = 0
elimine v y todas las aristas que salen de v...
tracking img