TEORA DE GRAFOS Ingeniera de Sistemas

Cdigo: MAT-31114

AUTORES Ing. Daniel Zambrano Ing. Viviana Semprn

UNIDADES DE LA ASIGNATURA

UNIDAD I. Relaciones UNIDAD II. Estructuras Algebraicas

UNIDAD III. Grafos

UNIDAD IV. Coloracin UNIDAD V. Redes de Flujos

UNIDAD I RELACIONES

Qu es un Conjunto?

Producto Cartesiano

Producto Cartesiano
Entonces: Sean A y B conjuntos una relacin de A a B es cualquier subconjunto R del producto cartesiano A * B donde A se conoce como dominio y B como rango de R.

Ejemplos: Sea A = {2, 3, 4}

B = {4, 5}

quedara:

A * B = {(2,4) , (2, 5) , (3, 4) , (3, 5) , (4, 4) , (4, 5) }

B = {(4, 4) , (4, 5) , (5, 4) , (5, 5) }

Relaciones y sus Propiedades

Relaciones y sus Propiedades

Relacin reflexiva: es cuando el elemento a mismo. esta relacionado consigo

Ejemplo: Tenemos la manzana la cual tiene relacin reflexiva con los siguientes elementos: Concha Pulpa
Semillas

Estos 3 elementos conforman lo que es la manzana y todos tienen relacion con la misma.

Relaciones y sus Propiedades

Relaciones y sus Propiedades

Relacin simtrica: es cuando un elemento est relacionado con un segundo elemento, el segundo tambin se relaciona con el primero.

Ejemplo: En un matrimonio el hombre esta relacionado con la mujer y viceversa.

Relaciones y sus Propiedades

Relaciones y sus Propiedades

Relacin transitiva: siempre que un elemento se relaciona con otro y ste ltimo con un tercero, entonces el primero se relaciona con el tercero.

Ejemplo: Si a es mayor que b, y b es mayor que c, entonces, a es mayor que c.

Relaciones y sus Propiedades

RELACION DE EQUIVALENCIA Se conforma una relacin de equivalencia, cuando se presentan las siguientes propiedades: reflexiva, transitiva y simtrica en una misma relacin.
Ejemplo: A = {a, b, c} R = {(a, a), (b, b), (c, c), (b, c), (c, b)} Reflexiva Simtrica Transitiva a R a, b R b, c R c bRc y cRb b R c, c R b, b R b

Clases de Equivalencia
CLASES DE EQUIVALENCIA Sea R una relacin de equivalencia sobre un conjunto A. Para cada a A, llamaremos clase de equivalencia de a, al conjunto formado por todos los elementos de A que estn relacionados con el. La notaremos; [a] = {x A = x R a}

Clases de Equivalencia

Particiones

Particiones

Particiones

Funciones
FUNCIONES

Funciones

Funciones

Funciones

Permutaciones

Permutaciones

n Pr

n! ( n r )!

Permutaciones

n Pr

n! ( n r )!

UNIDAD II Estructuras Algebraicas

Operaciones Binarias

Operaciones Binarias

Operaciones Binarias
Que es un Grupo?
En lgebra abstracta, un grupo es un conjunto en el que se define una operacin binaria, que satisface ciertos axiomas.

Se dice que la estructura (A, *) es un grupo con respecto a la operacin (*) si satisface las siguientes propiedades:

- Es cerrada - Es asociativa - Posee elemento neutro - Posee elemento simtrico - Es Conmutativo

Por ejemplo: La suma define estructura de grupo conmutativo en el conjunto de los nmeros enteros (Z), en el de los nmeros racionales (Q), en los nmeros reales (R) y en los nmeros complejos (C).

Operaciones Binarias
Que es un Monoide?
Un monoide es una estructura algebraica de la forma (A, *) donde A es un conjunto donde se ha definido una ley de composicin interna binaria (*).

Un monoide cumple las siguientes propiedades:

- Es cerrada - Es asociativa - Posee elemento neutro - Es Conmutativo

Por ejemplo: La suma multiplicacin de los nmeros naturales, (N, x) es un Monoide.

Operaciones Binarias
Que es un Semigrupo?
Un semigrupo es una estructura algebraica de la forma (A, *) donde A es un conjunto donde se ha definido una ley de composicin interna binaria (*).

Un semigrupo cumple las siguientes propiedades:

- Es cerrada - Es asociativa - Es Conmutativo

Por ejemplo: El conjunto de los nmeros naturales: N con la operacin suma: +. Que se representa: (N, +)

Operaciones Binarias

Operaciones Binarias

UNIDAD III Grafos

Grafos

Tipos de Grafos

Tipos de Grafos

Tipos de Grafos

Tipos de Grafos

Tipos de Grafos

Grafos Planos
Grafos Planares
En teora de grafos, un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se interseque. Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen.

Representacin de un Grafo
Representacin de grafos 1. La representacin grfica, adecuada para la interpretacin y resolucin de problemas en grafos pequeos o medianos. 2. La representacin mediante matriz asociada o de adyacentes, especialmente til para el tratamiento de problemas de grafos con programas informticos. 3. Otras representaciones, como el diccionario de grafo, buscan definir el grafo de forma ms compacta, en trminos de posiciones de memoria. Pueden ser tiles para representar grafos de gran tamao. }

Vrtices y Aristas
Representacin de grafos Existen mltiples maneras de representar un grafo. Tomemos un grafo orientado G(x, E) definido como con un conjunto de vrtices y arcos:
X = (1,2,3,4,5) E = {(1,5), (1,2), (2,5), (5,4), (3,4), (3,2), (2,3), (4,5)}

Esta representacin, pese a cumplir con los requerimientos de la definicin, resulta poco prctica para la interpretacin del grafo y la comprobacin de propiedades relevantes de ste. Por este motivo, existen diferentes representaciones de los grafos:

Representacin Grfica

Representacin Matricial

Representacin Matricial

Representacin Matricial

Representacin Matricial

Grado de un vrtice

Isomorfismo

Camino de un Grafo

Grafo de Euler

Grafo de Hamilton

UNIDAD IV COLORACIN

Coloracin de vrtices

Coloracin de vrtices

Coloracin de aristas

rboles
Arboles
En teora de grafos, un rbol es un grafo en el que cualesquiera dos vrtices estn conectados por exactamente un camino.

rboles

rboles

rboles

Otras definiciones de rboles

Grado de un rbol

Niveles de un rbol

rboles Completos

Otras definiciones de rboles

Nodos Padres e Hijos

rbol Ordenado

rbol Binario

rbol Binario

rbol Binario. Caractersticas

Recorrido de los rboles Binarios

Recorrido en Preorden

Recorrido en Preorden

Recorrido en Inorden

Recorrido en Inorden

Recorrido en Postorden

Recorrido en Postorden

UNIDAD V REDES DE FLUJO

Redes de Flujo

Redes de Flujo

Redes de Flujo

Redes de Flujo

Algoritmo de Ford-Fulkerson
El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo mximo.

La idea es encontrar una ruta de penetracin con un flujo positivo neto que una los nodos origen y destino.

Iteracin 1

Iteracin 6

Bibliografa
1. STANAT Y MCALLISTER, D.: Discrete Mathematics in Computer Science, PrenticeHall. 1977. 2. BIRKNOFF, G. Y BARTEE, T.: Modern Applied Algebra, McGraw-Hill. 1970. 3. CASTERAN, P.: Gua de Diseo Lgico, Universidad Simn Bolvar 1981. 4. FRALEIGH, J.: A first course in Abstract Algebra, Segunda edicin, Addison-Wesley. 1976. 5. KOLMAN, B. Y BUSBY, R.: Estructuras de Matemticas Discretas para la Computacin, Prentice-Hall. Hispanoamericana. 1986. 6. LIU, C.: Introduction to Combinatorial Mathematics. McGraw Hill. 1968. 7. MCLANE, S. Y BIRKNOFF, G.: Algebra, The McMillan Company 1968. 8. PRATHER, R.: Discrete Mathematical Structures for Computer Science, HoughtonMifflin Company. 1976. 9. PREPARATA, F. Y YEH, R.: Introduction to Discrete Structures for Computer Science and Engineering, Addison-Wesley. 1973. 10. STRANG: lgebra Lineal y sus Aplicaciones, Fondo Educativo Interamericano. 1982. 11. STANAT Y MCALLISTER, D.: Discrete Mathematics in Computer Science, PrenticeHall. 1977.

TEORA DE GRAFOS Ingeniera de Sistemas

Cdigo: MAT-31114

AUTORES Ing. Daniel Zambrano Ing. Viviana Semprn