Grafos

TALLER GRAFOS

PRESENTADO POR:

JUAN CARLOS RUEDA BERMUDEZ

OSCAR GONZALEZ

FABER NAVEROS

JUAN DAVID CAYCEDO

JAIME CHAYAN OCHOA

DOCENTE:

JAMES PEREZ

UNIVERSIDAD DEL TOLIMA IDEAD

INGENIERIA DE SISTEMAS

MATEMATICAS DISCRETAS

IBAGUE – TOLIMA

OCTUBRE 4 2014

1. Para cada una de estas relaciones en el conjunto A={1,2,3,4}, decide si es no reflexiva, si es o no simétrica, si es o no antisimetrica, y si es o no transitiva, y en caso de no cumplir alguna propiedad explica porque.

a) R={(1,1),(2,2),(3,3),(1,2),(3,2),(2,3)}

La relación es:

- No reflexiva. (por que los pares (1,2),(3,2) y (2,3) no la cumplen

- Es antisimetrica. (por que el par (1,2)no cumple la condición).

- Si es transitiva por que se cumple la condición AB Y BC = AC

- No es de equivalencia debido a que no se cumplen todas las condiciones anteriores.

b) R={(1,1),(1,2),(1,4),(2,3),(4,3)}

La relación es:

- No es reflexiva debido a que no todos los pares cumplen la condición (A=A).

- Es antisimetrica. (por que solo el par (1,1) cumple la condición (A,B)=(B,A).

- No es reflexiva por que no se cumple la condición AB Y BC = AC.

- No es de equivalencia debido a que no se cumplen todas las condiciones anteriores.

2. Representa cada una de estas relaciones en el conjunto {1, 2,3} mediante una matriz (con los elementos de este conjunto listados en orden creciente.

a) {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}

1 2 3

1 1 1 1

2 0 1 1

3 0 0 1

b) {(1,3),(3,1)}

1 2 3

1 0 0 1

2 0 0 0

3 1 0 0

3. Enumera los pares ordenados de las relaciones en el conjunto {1,2,3,4} que corresponden a la siguiente matriz (las filas y las columnas de la matriz corresponde a los enteros escritos en orden creciente).

1 1 1 0

0 1 0 0

0 0 1 1

1 0 0 1

4. Dibuja el grafo dirigido que representa a la relación:

{(a,b), (a,c), (a,d), (b,b), (c,a), (c,c), (d,b), (d,c)}

5. En el siguiente problema, determina el número de vértices y de aristas y halla los grados de entrada y de salida de cada uno de los vértices del multigrado dirigido.

6. Representa el grafo dirigido cuya matriz de incidencia es:

7. Construye la matriz de incidencia del siguiente grafo.

...