Grafos

GRAFOS

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ñado por una serie de puntos (los vértices) conectados por líneas (las aristas).
[pic]HISTORIA

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 ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.
En 1845 Gustav Kirchhoffpublicó 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 KennethAppel 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 una computadora. La estructura de datos usada depende de las caracteristicas del grafo y elalgoritmo 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 deincidencia - Las aristas son representadas con un arreglo de pares (ordenados, si es 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 casua redundancia en un grafo dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las busquedas son más rápidas, al costo dealmacenamiento 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 de adyacencia - El grafo está representado por una una matriz de N por N, donde N es el número de vértices. Si hay una aristas entreun vértice x a un vértice y, entonces el elemento Mx,y es 1, de lo contrario, 0.
DEFINICIONES

GRAFOS
Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. 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 sonrelevantes, 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 que colocar los vértices en forma de polígono regular da grafos muy legibles.
Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.ARISTAS DIRIGIDAS Y NO DIRIGIDAS

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos...