Grafos

REFERENCIAS: http://gpd.sip.ucm.es/rafa/docencia/md/apuntes/Tema5.ppt
http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal
http://www.cimat.mx/~jbhayet/CLASES/PROGRAMACIONII/clase15.pdf
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
http://www.lsi.upc.edu/~mabad/ADA/curso0506/grafos.pdf
http://www.monografias.com/trabajos16/grafos/grafos.shtml



México, DFJunio 2011

Índice.

1. Grafos.
2. Conectividad.
3. Algoritmos Unión-Pertenencia
4. Grafos ponderados o etiquetados.
5. Árbol de expansión mínimo.
6. Búsqueda en primera prioridad.
7. Método de Kruskal
8. Conclusiones

GRAFOS

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas,carreteras, el transporte colectivo metro o metrobus, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Desde un punto de vista práctico, losgrafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Conectividad

Se llama componente conexa de un grafo a todosubgrafo inducido por los vértices de una clase de equivalencia.

Un recorrido en un grafo G = (V,A) es una sucesión de vértices v0, v1, …, vn tal que {vi,vi+1}Î A para todo 0 ≤i < k
La longitud de un recorrido v0, v1, …, vk es k
Ejemplo:

Observación: Un recorrido puede repetir vértices, y puede comenzar y acabar en vértices diferentes Es decir en un camino todos los vértices son distintosentre sí, excepto quizás el primero y el último



Si existe un camino entre dos vértices se dice que están conectados.
Si para todo par de vértices de un grafo están conectados se dice que el grafo es conexo.
Las componentes conexas de un grafo son los mayores subgrafos conexos del mismo.

Biconectividad

Un grafo es biconexo si es conexo y no tiene puntos de articulación. es un grafoen el que todo punto de articulación está unido mediante al menos dos aristas con cada una de las componentes del grafo que quedarían al eliminar el vértice punto de articulación.

Una red con estas características sigue funcionando aunque falle una línea de la
red (una arista).

Grafo biconexo

Algoritmos de Unión-Pertenencia

En algunas aplicaciones se desea simplemente conocer si unvértice x esta o no conectado a un vértice y de un grafo, sin que sea importante el camino que los conecta de hecho, los eficaces algoritmos que se han desarrollado son interesantes por sí mismos dado que también pueden utilizarse para el procesamiento de conjuntos.

Dado un conjunto de aristas, se puede construir una representación por listas de adyacencias que corresponda al grafo y utilizar labúsqueda en profundidad para asignar a cada vértice el indice de su componente conexa, y así preguntas tales como «¿está x conectada a y?» pueden responderse con 2 accesos a arrays y una comparación

Grafos ponderados o etiquetados

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste
según el contexto, y se obtiene así un grafovaluado.

Formalmente, es un grafo con una función v: A → R+.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia...