• Author / Uploaded
• Joel Pacheco

Citation preview

UNIVERSIDAD TÉCNICA ESTATAL DE QUEVEDO FACULTAD DE CIENCIAS DE LA INGENIERÍA CARRERA EN INGENIERÍA INDUSTRIAL

TEMA TEORÍA DE GRAFOS

INTEGRANTES HOLLY ESTEFANIA GAIBOR VARGAS RUBEN DARIO MACIAS CORO REMIGIO FERNANDO PACHECO MENA CYNTHIA ELIZABETH REYNA INTRIAGO JOEL TOMAS OLVERA COELLO

CURSO MÓDULO VII A

MATERIA DISEÑO DE REDES

DOCENTE ING. ROGELIO NAVARRETE GÓMEZ 2019-2020

Teoría de Grafos La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos que no se debe confundir con las gráficas que tienen una acepción muy amplia) 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 guiados o no. [1] La teoría de grafos es una parte de la matemática discreta y de las aplicadas, y es un trato que usa diferentes conceptos de diversas áreas como análisis combinatorio, Álgebra abstracta, probabilidad, geometría de polígonos, aritmética y topología. Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones. [1] Que es un grafo: Un grafo es el principal objeto de estudio de la teoría de grafos. De esta forma, un grafo se representa gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (aristas) que pueden ser orientados o no. Los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción. El objetivo es encontrar un camino que pase por todos los nodos una y solo una vez y que tengamos el costo menor en distancia. Dicho de otro modo, se deben buscar las permutaciones de los nodos de forma que la distancia recorrida total sea mínima. [1] Grafos Conexos Un grafo es conexo si cada par de vértices está unido por un camino. Por ejemplo: para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. [1]

Aplicaciones: 

La grafos se pueden resolver muchos problemas como la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se usa para diferentes áreas, como, Dibujo computacional, en todas las áreas de Ingeniería. [2]



Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto, así como brindar rutas alternas en caso de presentar problemas de tránsito de la vía. [2]



Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos. [2]



La teoría de grafos desarrolla un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes. [2]



Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos). [2]



Los grafos pueden ser de usos en la optimización de redes, provee soporte en casos de averías de estos, brindándoles rutas alternas a los servidores. [2]

Puntos de articulación Un punto de articulación de un grafo no dirigido G es un nodo v tal que cuando es eliminado de G (junto con las aristas incidentes en el) se divide en componentes conexo del grafo original en dos o más componentes conexos. [3] Ejemplo: Si el grafo presenta una red de ordenadores, un punto de articulación será un nodo que, si funciona, hará que otros ordenadores de red queden incomunicados.

Problema del camino más corto En la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. [3]

Algoritmo de Dijkstra El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. [3] Algoritmo de Flujo Máximo El problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.v El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria. [3]

Tipos de grafo 

Grafo simple. o simplemente grafo es aquel que acepta una sola 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. [4]



Multigrafo. son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido. [4]



Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha



Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. [4]



Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.



Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.



Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito. [4] Componentes del grafo: 

Nodo (Vértice): un nodo es un punto de intersección, conexión o unión de varios elementos que confluyen en el mismo lugar. [2]



Estado: Es representación de los elementos que describen el problema en un momento dado. [2]

Aristas: Una arista es una relación entre dos vértices de un grafo.



Aristas Adyacentes: estas son dos aristas que se dirigen en al mismo vértice y se juntan en él. [2]



Aristas Paralelas: estas son dos aristas si el vértice inicial y el final son uno mismo. [2]



Cruce: Son dos aristas que cruzan en un punto. [2]

Bibliografía [1] G. A. REYES, «INVESTIGACION DEOPERACIONES II,» Systems Engineer, 11 05 2012. [En línea]. Available: https://ingreyesb.wordpress.com/investigacion-de-operaciones-ii/. [Último acceso: 23 10 2019]. [2] UNMSM, «Conociendo la Investigación de Operaciones,» blog , 1 Junio 2014. [En línea]. Available: http://cio200.blogspot.com/2014/06/quienes-somos.html. [Último acceso: 23 10 2019]. [3] F. S. Caparrini, «Problemas Búsqueda y Planificación,» blog, 7 Octubre 2019. [En línea]. Available: http://www.cs.us.es/~fsancho/?e=33. [Último acceso: 23 10 2019]. [4] M. F. Á. NUÑEZ, «Teoria de grafos,» FACULTAD DE EDUCACIÓN Y HUMANIDADES, Chile, 2005.