Estructura de Datos Sesion 14 Docente

Estructura de Datos - Sesion 14
Teoría de grafos

Diagrama de un grafo con 6 vértices y 7 aristas.
En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son
colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden
tener orientación (dirección asignada). Típicamente, un grafo está diseñadopor una serie de puntos (los vértices)
conectados por líneas (las aristas).

Historia

Puentes de Königsberg.
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno
de los primeros resultados 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 ejemploilustra 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 vecinosnunca 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.
Estructuras de datos en la representación de grafos
Existen diferentes formas de almacenar grafos en unacomputadora. La estructura de datos usada depende de las
características del grafo y el algoritmo usado para manipularlo. Teóricamente se pueden distinguir la estructuras
de listas y las de matrices, pero usualmente, lo mejor es una combinación de ambas. Las listas son preferidas en
grafos 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) de
vértices que conecta esa arista.
• 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 deadyacencia de B y viceversa), pero las
búsquedas son más rápidas, al costo de almacenamiento extra.
ED Page 1

búsquedas son más rápidas, al costo de almacenamiento extra.
Estructuras matriciales
• Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista,
vértice] contiene la información de la arista (1 - conectado, 0 - no conectado)
• Matriz deadyacencia - El grafo está representado por una una matriz cuadrada M de tamaño n, donde n es el
número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo
contrario, es 0.
Definiciones
Vértice
Un vértice es la unidad fundamental de la que están formados los grafos. Los vértices son tratados como un
objeto indivisible y sin propiedades, aunquepuedan 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.
Grafo

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.
Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto dearistas,
este último es un conjunto de subconjuntos de la forma (u,v) tal que
, tal que
. Para simplificar, notaremos la arista {a,b} como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué
vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más
claro. Generalmente, se considera...