Un grafo es un conjunto de objetos llamados vértices (o nodos) y una selección de

segmentos que unen pares de vértices, llamados aristas que pueden ser dirigidos o no
dirigidos. Típicamente, un grafo se representa mediante una serie de puntos (los vértices)
conectados por líneas (las aristas).

Los grafos son unas representaciones gráficas de problemas que se plantean en la vida real
y que con una serie de fórmulas y algoritmos que nos llevan a encontrar soluciones óptimas
más rápidamente.
Para resolver este tipo de problemas se utilizan diferentes algoritmos que veremos más
adelante.

NOTA: Podemos decir que un algoritmo es como una receta: son unos pasos a seguir para
conseguir un objetivo.

También debemos saber lo que es el grado de un vértice.

El grado es el número de aristas que llegan a un vértice concreto.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del

grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del
grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos
vértices.
Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de
carreteras, vías férreas, circuitos eléctricos, etc.
La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los elementos de un grafo son: Aristas, vértices y Caminos.

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen
también caminos.
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los
vértices que une.
Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo
vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el
mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.
Son los puntos o nodos con los que está conformado un grafo.
Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un
vértice es "par" o "impar" según lo sea su grado.

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos una

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.

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía
de aristas {x, v1}, {v1, v2}, ..., {vn, y}. En este caso

x e y se llaman los extremos del camino

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.
Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino
cerrado.
Llamaremos ciclo a un circuito simple
Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo
vértice es accesible respecto a si mismo.

Grafo simple. o simplemente grafo es aquel que acepta una sola una arista uniendo dos
vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que
une dos vértices específicos. Es la definición estándar de un grafo.

Multígrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices.
Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una
subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas,
representada gráficamente por una flecha

Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero
generalmente) o un etiquetado a los vértices.

Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.

Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las
aristas son incidentes a 3 o más vértices.

Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Matriz de adyacencia

La matriz de adyacencia de un grafo es simétrica. Si un vértice es

aislado entonces la correspondiente fila (columna) está compuesta sólo
por ceros. Si el grafo es simple entonces la matriz de adyacencia
contiene solo ceros y unos (matriz binaria) y la diagonal está compuesta
sólo por ceros.

Matriz de incidencia

La matriz de incidencia sólo contiene ceros y unos (matriz binaria).

Como cada arista incide exactamente en dos vértices, cada columna
tiene exactamente dos unos. El número de unos que aparece en cada
fila es igual al grado del vértice correspondiente. Una fila compuesta
sólo por ceros corresponde a un vértice aislado.

En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de

loas graficas estudia las propiedades de los grafos (también llamados graficas) Un grafo es
un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de
vértices llamados aristas.

COMPUTACIONAL

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos,

usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre
las estructuras más sencillas y usadas se encuentran las listas y las matrices y aunque
frecuentemente se usa una combinación de ambos.
algoritmos de recorrido:

En ciencias de la computación, A* es un algoritmo informático que se utiliza ampliamente en

la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable
de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y
precisión, que goza de amplio uso.
Peter Hart, Nils Nilsson y Bertrám Raphael del Instituto de Investigación de Stanford (ahora
SRI International) describieron por primera vez el algoritmo en 1968.Se trata de una
extensión de la Edsger Dijkstra algoritmo de 1959. A* consigue un mejor rendimiento tiempo
usando heurística.

En la teoría de grafos, el problema del camino más corto es el problema de encontrar un

camino entre dos vértices (o nodos) en un gráfico de tal manera que la suma de los pesos
de sus bordes constituyentes se reduce al mínimo.

Esto es análogo al problema de encontrar el camino más corto entre dos intersecciones en
un mapa de carreteras: vértices del gráfico corresponden a las intersecciones y los bordes
corresponden a los segmentos de carretera, cada uno ponderado por la longitud de su
segmento de carretera.

Los algoritmos más importantes para la solución de este problema son:

El algoritmo de Dijkstra: Resuelve las cortas de origen único problemas de ruta.

Algoritmo de Bellman-Ford: Resuelve el problema de una sola fuente, si borde pesos
pueden ser negativos.
Un algoritmo de búsqueda *: Resuelve para el par de ruta más corta única utilizando la
heurística para tratar de acelerar la búsqueda.
Algoritmo de Floyd-Warshall: Resuelve todos los pares caminos más cortos.
Algoritmo de Johnson: Resuelve todos los pares de trayectorias más cortas, y puede ser
más rápido que Floyd-Warshall en grafos dispersos.

Ahora bien, podemos emplear el algoritmo de Dijkstra para estos casos, los pasos o
procedimientos a seguir para éste algoritmo son los siguientes: Teniendo un grafo dirigido
ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará
al final del algoritmo las distancias desde x al resto de los nodos.
Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al
principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x
sería 0.
Sea a = x (tomamos a como nodo actual).
Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a
estos vi
Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a,
sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
Marcamos como completo el nodo a.
Tomamos como próximo nodo actual el de menor valor en D (puede hacerse
almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan
nodos no marcados.
es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el
recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los
puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso.
(Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente
superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor
rendimiento.)

Ejemplo
Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades
conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino:

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visitado.

Nota: En este ejemplo se utiliza una coma como separador decimal.

Ilustración de la búsqueda A * para la búsqueda de ruta desde un nodo de inicio a un nodo

objetivo en un robot de planificación de movimientos problema.

La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los

vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización,
en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la
búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice
activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo
que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v
(que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por
lo que se construye un grafo sin ciclos, que será un árbol.