Grafos

Historia [editar]
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 GustavKirchhoff 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 porKenneth 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 [editar]

Artículo principal: Grafo (estructura de datos)
Existen diferentes formas de almacenar grafos en una computadora. Laestructura 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 consumirgrandes cantidades de memoria.

Estructura de lista [editar]

• 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.

Estructuras matriciales [editar]

• 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 unauna 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 [editar]


Vértice [editar]

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, aunque puedan tener unaestructura 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 [editar]

Artículo principal: Grafo
[pic]
[pic]
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 devértices, y A es el conjunto de aristas, este último es un conjunto de subconjuntos de la forma (u,v) tal que [pic], tal que [pic]. 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 obtenerun 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..

Subgrafo [editar]

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de...