investigacion de operaciones grafos

TIPOS DE GRAFOS

Los grafos se pueden clasificar en dos grupos:
Dirigidos: cada arco está representado por una par ordenado de vértices, de forma que representan dos arcos diferentes.

No dirigidos: el par de vértices que representa un arco no está ordenado.

Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
Grafo bipartito: Esaquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.
Un grafo bipartito regular: se denota K m,n donde m, n es el grado de cada conjunto disjunto de vértices.
Grafo nulo: Se dice que un grafo esnulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia uno a uno, entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
Grafos Platónicos: Son los grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos),como, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

Grafos eulerianos.
Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Un grafo euleriano es aquel grafo que contiene un camino Euleriano.
Grafos conexos.
Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y esalcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
Árboles.
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo.
Bosques de árboles.
Los bosques de árboles son un caso similar alos árboles, son acíclicos, pero no son conexos.
REPRESENTACIÓN DE GRAFOS
Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.
Representación mediante matrices:   La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos sepueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
Representación mediante listas:    En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodosse puede guardar en un vector, al igual que antes, o en otra lista dinámica.
Representación mediante matrices dispersas:    Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tantamemoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
Dígrafo (grafo dirigido).
A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.


Recorrido de grafos
Búsqueda por profundidad (DFS)
Consiste en buscar los caminos que parten desde el nodo desalida hasta que ya no es posible avanzar más. Cuando ya no puede avanzar más sobre el camino elegido se regresa por el camino elegido y busca un nuevo camino que no haya visitado.
La búsqueda en profundidad empieza por un vértice V. del grafo G; V no visitado; así hasta que no haya más vértices por visitar.
Algoritmo de recorrido por profundidad
1. Punto de partida v ϵ V, lo marcamos como...