TEORIA DE GRAFOS

un grafo G, es un par ordenado de V y A, vértices y aristas.

un vértice puede tener 0 o mas aristas 

una arista debe unir a dos vertices

aristas

son las lineas que se unen y con la que construye caminos.

• Aristas Adyacentes: Dos aristas son adyacentes si convergen en el mismo vértice.

• Aristas Paralelas: Son paralelas cuando el vértice inicial y el final son el mismo.

• Aristas Cíclicas: Es cuando una arista parte de un vértice para entrar en el mismo.
• Cruce: Son dos aristas que cruzan en un punto.

vertices

son los puntos o nodos con los que esta conformado un grafo.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

• Vértice Aislado: Es un vértice de grado cero.

• Vértice Terminal: Es un vértice de grado 1.

caminos

El número de aristas del camino se llama la longitud del camino.

Si los vértices no se repiten el camino se dice propio o simple.

Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.

Llamaremos ciclo a un circuito simple 

clasificación de grafos

se pueden clasificar en dos grupos: dirigidos y no dirigidos

• Grafo regular: Aquel con el mismo grado en todos los vértices
• Grafo bipartito: Es aquel 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.
• Grafo nulo: Se dice que un grafo es nulo 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 biunívoca (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), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

grafos conexos

un grafo se puede definir como conexo si cualquier vertice pertenece al conjunto de vertices y es alcanzable por algun otro

recorrido de un grafo

recorrer un grafo es tratar de alcanzar todos los nodos que esten relacionados con uno que llamaremos nodo de salida.

grafo dirigido

se le define a un grafo que contiene aristas dirigidas

los siete puentes de konigsberg

fue lo que dio origen a la teoría de grafos.
En la ciudad de Königsberg hay una isla y el río Pregel que la rodea se divide en dos brazos. La distintas zonas de tierra están unidos mediante siete puentes (color rojo). ¿Es posible dar un paseo por la ciudad, empezando por cualquiera de las cuatro partes de tierra firme, cruzando cada puente una y sólo una vez y volver nuevamente al punto de partida?.
Después de un tiempo, en 1736, Leonhard Euler dio respuesta a este problema, dando origen a la teoría de grafos. 
Euler se dio cuenta que la cantidad de líneas de cada punto tendría que ser par, para así poder entrar y salir de dicho punto, ocupando tan solo una vez cada puente.
En el problema de Königsberg, Euler demostró que era imposible recorrer la ciudad de la forma pedida, ya que el número de líneas que llegan a cada punto es impar y ésto implica que no es posible recorrerlos pasando una sola vez por cada uno de los puentes, es decir, no había solución para ese problema.

formas de representación

matriz adyacente: se asocia cada fila y cada columna a cada nodo del grafo, siendo la relación entre los mismo tomando 1 si existe la arista y 0 si no existe

Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.