Grafos Dirigidos

República Bolivariana de Venezuela

Universidad Bicentenaria de Aragua

Facultad de Ingeniería

Escuela de Ingeniería de Sistemas

Estado Aragua

GRAFOS DIRIGIDOS

Profesora:                                                                                       Alumna:

Deyanira Noguera                                                                           Valeria Ruiz

Materia:                                                                                           C.I. 26.830.930

Sistemas Expertos y Lógica Difusa

San Joaquín-Turmero. Junio 2019.

¿Qué es un grafo dirigido?

     Castillo, Gutiérrez y Hadi (s.f.) afirman “Los grafos son herramientas muy útiles para definir sistemas expertos y otros modelos utilizados en el área de la inteligencia artificial” (p.115).

     Puede permitirse que dos nodos estén conectados por más de una arista, o incluso que un nodo esté conectado consigo mismo. Sin embargo, en el campo de los sistemas expertos, los grafos se utilizan para representar un conjunto de variables proposicionales (nodos), y unas relaciones de dependencia entre ellas (aristas). Por tanto, no es necesario que dos nodos estén unidos por más de una arista, o que una arista una un nodo consigo mismo.

      “Las aristas de un grafo pueden ser dirigidas o no dirigidas, dependiendo si se considera o no, el orden de los nodos” (Castillo, Gutiérrez y Hadi, s.f., p.117).

     Un grafo en el cual todas las aristas son dirigidas se denomina grafo dirigido. Por tanto, en un grafo dirigido es importante el orden del par de nodos que definen cada arista.

Representación

     Existen varias estructuras de datos que pueden utilizarse para representar grafos y dígrafos. La elección de la estructura de datos adecuada depende del tipo de operaciones que se quieran aplicar al conjunto de vértices y aristas (arcos) del grafo (dígrafo) en cuestión. Las representaciones más comunes son las matrices de adyacencia y las listas de adyacencia (Brown, 2007, p.2).

     Un grafo puede ser representado de varias formas equivalentes que pongan en manifiesto en mayor o menor medida determinadas características. Según Castillo, Gutiérrez y Hadi (s.f.) las formas de representación más comunes son:

• Simbólicamente, como un par (X, L), donde X es un conjunto de variables y L es un conjunto de aristas entre pares de variables. Una representación simbólica equivalente a esta viene dada por (X, Ady), donde Ady es la clase de los conjuntos de adyacencia de los nodos.
• Gráficamente, por medio de un diagrama formado por un conjunto de nodos (uno para cada variable) y un conjunto de líneas o flechas (una para cada arista del conjunto L).
• Numéricamente, utilizando ciertos tipos de matrices.

     Cada una de estas representaciones presenta ventajas e inconvenientes. Por ejemplo, la representación simbólica es conceptualmente simple (cada grafo puede ser representado por un par de conjuntos), pero no proporciona información directa sobre la topología del grafo. La representación gráfica permite observar globalmente las distintas relaciones que existen entre las variables, pero tiene la desventaja de volverse extremadamente compleja cuando el número de aristas entre los nodos es muy elevado. Por último, la representación numérica permite obtener características de los grafos por simples manipulaciones algebraicas, pero tiene la desventaja de ser muy abstracta.

Representación Gráfica de un Grafo

     Castillo, Gutiérrez y Hadi (s.f.) refieren que un grafo está formado por un conjunto de nodos y un conjunto de aristas. El principal obstáculo es que un grafo puede ser representado de muchas formas distintas, por ejemplo, en una hoja de papel o en la pantalla de un ordenador. Sin embargo, algunas de estas representaciones son mejores que otras en términos de sencillez, capacidad para mostrar las principales características del grafo, etc. Estas representaciones permiten analizar visualmente ciertas propiedades topológicas del grafo de forma sencilla. Se presentan dos formas sistemáticas de representación gráfica: Circular y Multinivel.

...