UNIDAD Nº 3.GRAFOS

        La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelizar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.

 HISTORIA DE LA TEORIA DE GRAFOS


El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.

 

   En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.

 En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges  en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

 

 

Estructuras de datos en la representación de grafos
    Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
 
Estructura de lista
  • Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.
  • Lista de adyacencia- Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
   

     En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta. 
                                   
 

Vértice (teoría de grafos)
En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigidoestá compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.
Los dos vértices que conforman una arista se llaman puntos finales y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.
Vértices y grados
El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna arista. Unvértice hoja es un vértice con grafo uno. En un grafo dirigido, se puede distinguir entre grado de salida (”outdegree”, número de aristas que salen del vértice) y grado de entrada (”indegree”, número de aristas que llegan al vértice); un vértice fuente es un vértice con grado de entrada cero, mientras que un vértice hundido es un vértice con grado de salida cero.
Conexiones de vértices

 

Un vértice de corte es un vértice que al removerlo desconecta al grafo restante. Un conjunto independiente es un conjunto de vértices tal que ninguno es adyacente a otro, y una cobertura de vértices es un conjunto de vértices que incluye los puntos finales de cada arista en un grafo. 
 
  • Reglas básicas: se refieren a aspectos elementales como el solapamiento entre aristas vertices o ambos.
Reglas Básicas
   
KO OK   KO OK   KO OK
No solapar vértices   No solapar aristas    No solapar vértices con aristas
  • Reglas semánticas: son reglas de posicionamiento de vértices y de dibujo de arcos o aristas (enrutado) derivadas del significado de vértices y aristas. Por ejemplo dibujar el tamaño de un vértice o el grosor de una arista en función de su importancia. Suelen venir dadas por el usuario o son deducidas de la información de sus etiquetas asociadas.
Reglas Semánticas
   
Alinear vértices específicos   Disponer vértices específicos en curva   Dibujar vértices específicos con distinto tamaño
   
Emplazar vértices específicos en la frontera   Agrupar vértices específicos   Centrar vértices específicos
  • Reglas estructurales: son reglas de posicionamiento y enrutado relacionadas sólo con las propiedades de la teoría de grafos. Por ejemplo colocar los vértices de mayor orden en el centro del dibujo o minimizar la longitud total de aristas, minimizar el numero de cruces entre vértices, etc.
Reglas estructurales
   
KO OK   OK KO                     OK   KO OK
Centrar los vértices con orden alto   Colocar los grafos isomorfos 
(igual forma) de idéntica manera.		   Emplazar en forma jerárquica
   
KO OK   KO OK   KO OK
Minimizar los cruces de aristas   Buscar equilibrio en las dimensiones del dibujo   Organizar simétricamente
   
KO OK   KO OK   KO OK
Minimizar las esquinas en aristas   Dibujar caras como polígons convexos   Colocar los hijos simétricamente
   
KO OK   KO OK   KO OK
Evitar cruces de ramas diferentes   Emplazamiento uniforme   Minimizar el área de dibujo
   
KO OK   KO OK   KO OK
Minimizar la longitud total de aristas   Minimizar la diferencia de tamaño de los vértices   Minimizar la longitud media de las aristas
 
 

Esta pagina fue creada con la finalidad de  elaboracion de trabajos y aplicacion de nuestros conocimientos sobre la Teoría de grafos