Matemáticas discretas- Teoría de Grafos

Integrantes :
Citlalic Becerril
Angela Janeth Jimenez
Cesar Mendoza

1. MATEMÁTICAS DISCRETAS TEORÍA DE GRAFOS PROFESORA: ANGELA YANINA ROMERO CESAR MENDOZA CRUZ CITLALIC BECERRIL LÓPEZ ANGELA JANETH JIMENEZ CHAVEZ 07/04/14 2AM

2. Menú Grafos (Teoría) Partes de un grafo Grafo orientado Grafo isomorfo Subgrafo Grafo simple Grafo conexo Los siete puentes de Kueiphof Identificar elementos de un grafo ejercicios Matríz de Adyacencia Ejercicios Matríz de Incidencia Ejercicios Isomorfismo de grafos Ejercicios Ciclo de Euler Ejercicios Ciclo de Hamilton Ejercicios

3. Grafos Teoría de grafos La  teoría de grafos   es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos  estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados que pueden ser orientados o no.

4. un  grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.  Grafos ¿QUÉ ES UN GRAFO?

5. Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas ). Grafos ¿CÓMO SE CONFORMA UN GRAFO? V értice Arista

6. Complementos del Grafo Aristas paralelas: Dos o más aristas que son incidentes (que se conectan) al menos dos vértices iguales. Lazos: es un arista cuyos extremos inciden sobre el mismo vértice. Vértices adyacentes: los vértices son adyacentes cuando comparten el mismo arista. Aristas adyacentes: dos aristas son adyacentes si tienen un vértice en común.

7. Grafo orientado Un grafo dirigido o  grafo orientado,  es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no. V1 V2 V3

8. Grafo simple Grafo simple  o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo. No contiene aristas paralelas, lazos ni aristas dirigidos. v1 v2 v4 v3

9. U n  grafo  se dice conexo si, para cualquier par de vértices  a  y  b  en  G , existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de  a  a  b . Grafo conexo Grafo Conexo Grafo No Conexo

10. subgrafo Un subgrafo es un grafo que esta contenido dentro de otro grafo y que se obtiene eliminando algunas aristas y vértices del grafo principal. Grafo principal Subgrafo

11. Grafo isomorfo Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común. ¿Cómo probarlo? Buscando una función biyectiva que convierta los vértices de uno en otro, preservando la estructura de las aristas.

12. El problema de los puentes de Königsberg, es un célebre problema matemático, resuelto por  Leonard Euler en  1736 y cuya resolución dio origen a la teoría de grafos. Su nombre se debe a  Königsberg , el antiguo nombre que recibía la ciudad rusa  de Kaliningrado. Los 7 puentes de königsberg

13. El problema El problema fue formulado originalmente de manera informal, consistía en responder a la siguiente pregunta : Dado el mapa de Königsberg, con el río Pregolya dividiendo el plano en cuatro regiones distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, de modo de recorrerlas todas pasando sólo una vez por cada puente, y regresando al mismo punto de origen?

14. La solución Nombremos cada porción de tierra firme con una letra mayúscula en rojo y cada uno de los puentes con una letra minúscula en azul. Podemos considerar cada porción de tierra firme como un punto y cada uno de los puentes como una línea. De esta manera, el mapa es equivalente a este diagrama: La resolución del problema de los puentes de Königsberg equivale a poder trazar la red dibujada más arriba sin levantar tu lápiz del papel y sin volver a trazar ningún arco. A este trayecto lo denominamos la red. Euler demostró que no se puede recorrer una red si posee más de dos vértices con grados que sean números impares. La red que representa el problema de los puentes de Königsberg tiene cuatro vértices impares. La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes.

15. Identificar los elementos del grafo Aristas paralelas Lazos Vértices aislados Vértices adyacentes Aristas adyacentes Grado del vértice ejercicios

16. Identificar: aristas paralelas, lazos, vértices aislados, vértices adyacentes, aristas adyacentes y grados de los vértices. v5 v3 v4 v2 v1 e3 v5 e1 e4 e 5 e 6 e2 Aristas paralelas : L azos: Vértices aislados: V értices adyacentes: Aristas adyacentes: G rados de los vértices:

17. Identificar: aristas paralelas, lazos, vértices aislados, vértices adyacentes, aristas adyacentes y grados de los vértices. v3 v2 v1 v4 v5 e2 e1 e3 e4 e5 e6 e8 e7 Aristas paralelas : L azos: Vértices aislados: V értices adyacentes: Aristas adyacentes: G rados de los vértices:

18. Identificar: aristas paralelas, lazos, vértices aislados, vértices adyacentes, aristas adyacentes y grados de los vértices. Aristas paralelas : L azos: Vértices aislados: V értices adyacentes: Aristas adyacentes: G rados de los vértices: v2 v1 v5 v4 v5 e3 e2 e5 e8 e6 e7 e4 v3 e1

19. Matriz de Adyacencia Definición y ejemplos.

20. Matriz de adyacencia Construcción de la matriz a partir de un grafo: Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo. Por cada arista que une a dos nodos, se suma  1 al valor que hay actualmente en la ubicación correspondiente de la matriz. Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1. Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos ). La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias. Grafos

21. Matriz de Incidencia Definición y ejemplos.

22. Grafos La  matriz de incidencia  es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representar relaciones binarias. Matriz de adyacencia Construcción de la matriz a partir de un grafo: Las columnas de la matriz representan las   aristas  del grafo. Las filas representan a los distintos nodos. Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente , y llenamos el resto de las ubicaciones con ceros (0).

23. Identificar: Matriz de adyacencia e incidencia de los siguientes grafos. v5 v3 v4 v2 v1 e3 v5 e1 e4 e 5 e 6 e2

24. Identificar: Matriz de adyacencia e incidencia de los siguientes grafos. v3 v2 v1 v4 v5 e2 e1 e3 e4 e5 e6 e8 e7

25. Identificar: Matriz de adyacencia e incidencia de los siguientes grafos. v2 v1 v5 v4 v5 e3 e2 e5 e8 e6 e7 e4 e1

26. Isomorfismo de grafos Ejercicios

27. Identificar: Cuales de los siguientes grafos son isomorfos (mediante la matriz de adyacencia). e b c d a a b c d e

28. Identificar: Cuales de los siguientes grafos son isomorfos (mediante la matriz de adyacencia). a b c d a b c d

29. Identificar: Cuales de los siguientes grafos son isomorfos (mediante la matriz de adyacencia). b c d b d e a a c f e f

30. Definición y ejemplos Ciclo de Euler

31. Un  ciclo  o circuito euleriano es aquel camino que recorre todas las aristas de un  grafo tan solo una única vez, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez". Se debe tener en cuenta que no importa la repetición de vértices mientras no se repitan aristas. Ciclo de Euler Grafos

32. Ciclo de Hamilton Definición y ejemplos

33. Grafos Ciclo que contiene todos los vértices de un grafo G. Es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una vez. Es un ciclo de Hamilton si m >= ½ ( n 2 – 3n + 6) Donde m = Aristas y n = Vértices Ciclo de Hamilton

34. Identificar: Cuales grafos admiten ciclo de Hamilton o ciclo de Euler b a c d e v1 v5 v2 v4 v3

35. Identificar: Cuales grafos admiten ciclo de Hamilton o ciclo de Euler b c e b a c e f d g a f d

36. bibliografía www.aulamatematicas.org www.commons.wikimedia.org www.derivadas.es www.taringa.net www.planetseed.com www.es.scribd.com www.mate.cucei.udg.mx www.buenastareas.com www.matediscreta.8k.com www.compdiscretas.wordpress.com www. help.sap.com www. teoriadegrafos.blogspot.mx www.ecured.cu Gracias por su atención  Angela Janeth Jiménez Chávez Citlalic Becerril López Mendoza Cruz Cesar Antonio 07/04/14