¿Qué es un gráfico?
Formalmente, un gráfico es el siguiente:
- una colección de vértices V, y
- Una colección de aristas E que consiste en pares de vértices.
Piense en los vértices como “ubicaciones”. El conjunto de vértices es el conjunto de todas las ubicaciones posibles. En esta analogía, los bordes representan caminos entre pares de esos lugares; el conjunto E contiene todos los caminos entre las ubicaciones.
Representación
El gráfico normalmente se representa usando esa analogía. Los vértices son puntos o círculos; Los bordes son líneas entre ellos. 
En este gráfico de ejemplo, V = {1, 2, 3, 4, 5, 6} y E = {(1,3), (1,6), (2,5), (3,4), (3 , 6)}.
Cada vértice es un miembro del conjunto V. Un vértice a veces se denomina nodo .
Cada borde es un miembro del conjunto E. Tenga en cuenta que algunos vértices pueden no ser el punto final de ningún borde. Dichos vértices se denominan “aislados”.
A veces, los valores numéricos están asociados con bordes, especificando longitudes o costos; tales gráficos se llaman gráficos ponderados por el borde (o gráficos ponderados). El valor asociado con un borde se denomina peso del borde. Una definición similar es válida para los gráficos ponderados por nodo,
- ¿Cuál es el intercambio de espacio temporal en las estructuras de datos?
- ¿Cuáles son las diferencias entre Algorithmia y Amazon Lambda?
- Cómo resolver http://www.spoj.com/problems/SAMER08A/ usando el algoritmo de Dijkstra
- Programadores: ¿A menudo considera el promedio, el peor y el mejor caso en mente al escribir un algoritmo?
- Cómo aprender a escribir buenos algoritmos
Terminología
Veamos nuevamente el primer gráfico de ejemplo:
Un borde es un bucle automático si tiene la forma (u, u). El gráfico de muestra no contiene bucles automáticos.
Un gráfico es simple si no contiene bucles automáticos ni contiene un borde que se repite en E. Un gráfico se llama multigrafo si contiene un borde dado más de una vez o si contiene bucles automáticos. Para nuestras discusiones, se supone que los gráficos son simples. El gráfico de ejemplo es un gráfico simple.
Un borde (u, v) incide tanto en el vértice u como en el vértice v. Por ejemplo, el borde (1,3) incide en el vértice 3.
El grado de un vértice es el número de aristas que inciden en él. Por ejemplo, el vértice 3 tiene grado 3, mientras que el vértice 4 tiene grado 1.
El vértice u es adyacente al vértice v si hay algún borde en el que ambos son incidentes (es decir, hay un borde entre ellos). Por ejemplo, el vértice 2 es adyacente al vértice 5.
Se dice que un gráfico es escaso si el número total de aristas es pequeño en comparación con el número total posible (( N x (N-1)) / 2 ) y denso de lo contrario. Para un gráfico dado, si es denso o disperso no está bien definido.
Gráfico dirigido
Los gráficos descritos hasta ahora se denominan no dirigidos , ya que los bordes van “en ambos sentidos”. Hasta ahora, los gráficos han connotado que si uno puede viajar del vértice 1 al vértice 3, también puede viajar del vértice 3 al vértice 1. En otras palabras, (1,3) estar en el conjunto de bordes implica (3,1) está en el borde establecido.
A veces, sin embargo, se dirige un gráfico, en cuyo caso los bordes tienen una dirección. En este caso, los bordes se llaman arcos .
Los gráficos dirigidos se dibujan con flechas para mostrar la dirección. 
El grado de salida de un vértice es el número de arcos que comienzan en ese vértice. El grado de un vértice es el número de arcos que terminan en ese vértice. Por ejemplo, el vértice 6 tiene un grado de entrada 2 y un grado de salida 1.
Se supone que un gráfico no está dirigido a menos que se llame específicamente un gráfico dirigido.
Rutas
Una ruta desde el vértice u hasta el vértice x es una secuencia de vértices ( v 0 , v 1 , …, vk ) de modo que v0 = u y vk = x y ( v 0 , v 1 ) es un borde en el gráfico, como es ( v 1 , v 2 ), ( v 2 , v 3 ), etc. La longitud de dicha ruta es k .
Por ejemplo, en el gráfico no dirigido anterior, (4, 3, 1, 6) es una ruta. 
Se dice que esta ruta contiene los vértices v 0 , v 1 , etc., así como los bordes ( v 0 , v 1 ), ( v 1 , v 2 ), etc.
Se dice que el vértice x es accesible desde el vértice u si existe una ruta desde u hasta x .
Una ruta es simple si no contiene vértices más de una vez.
Una ruta es un ciclo si es una ruta desde algún vértice a ese mismo vértice. Un ciclo es simple si no contiene vértices más de una vez, excepto el vértice inicial (y final), que solo aparece como el primer y último vértice en la ruta.
Estas definiciones se extienden de manera similar a los gráficos dirigidos (por ejemplo, ( v 0 , v 1 ), ( v 1 , v 2 ), etc. deben ser arcos).
Representación Gráfica
La elección de la representación de un gráfico es importante, ya que las diferentes representaciones tienen costos de tiempo y espacio muy diferentes.
Los vértices generalmente se rastrean numerándolos, para que uno pueda indexarlos solo por su número. Por lo tanto, las representaciones se centran en cómo almacenar los bordes .
Lista de borde
La forma más obvia de realizar un seguimiento de los bordes es mantener una lista de los pares de vértices que representan los bordes en el gráfico.
Esta representación es fácil de codificar, bastante fácil de depurar y bastante eficiente en cuanto al espacio. Sin embargo, determinar los bordes que inciden en un vértice dado es costoso, al igual que determinar si dos vértices son adyacentes. Agregar un borde es rápido, pero eliminar uno es difícil si no se conoce su ubicación en la lista.
Para gráficos ponderados, esta representación también mantiene un número más para cada borde, el peso del borde. Ampliar esta estructura de datos para manejar gráficos dirigidos es sencillo. Representar multigrafos también es trivial.
Matriz de adyacencia
Una segunda forma de representar un gráfico utiliza una matriz de adyacencia . Esta es una matriz N por N (N es el número de vértices). La entrada i, j contiene un 1 si el borde (i, j) está en el gráfico; de lo contrario, contiene un 0. Para un gráfico no dirigido, esta matriz es simétrica.
Esta representación es fácil de codificar. Es mucho menos eficiente en espacio, especialmente para gráficos grandes y dispersos. La depuración es más difícil, ya que la matriz es grande. Encontrar todos los bordes incidentes en un vértice dado es bastante costoso (lineal en el número de vértices), pero verificar si dos vértices son adyacentes es muy rápido. Agregar y quitar bordes también son operaciones muy económicas.
Para gráficos ponderados, el valor de la entrada (i, j) se usa para almacenar el peso del borde. Para un multigrafo no ponderado, la entrada (i, j) puede mantener el número de aristas entre los vértices. Para un multigrafo ponderado, es más difícil extender esto.
Lista de adyacencia
La tercera representación del gráfico es hacer un seguimiento de todos los bordes incidentes en un vértice dado. Esto se puede hacer usando una matriz de longitud N, donde N es el número de vértices. La entrada i-ésima en esta matriz es una lista de los bordes incidentes con el vértice i (los bordes están representados por el índice del otro vértice incidente con ese borde).
Esta representación es mucho más difícil de codificar, especialmente si el número de bordes incidentes en cada vértice no está limitado, por lo que las listas deben ser listas vinculadas (o asignadas dinámicamente). Depurar esto es difícil, ya que seguir las listas vinculadas es más difícil. Sin embargo, esta representación usa casi tanta memoria como la lista de bordes. Encontrar los vértices adyacentes a cada nodo es muy barato en esta estructura, pero verificar si dos vértices son adyacentes requiere verificar todos los bordes adyacentes a uno de los vértices. Agregar un borde es fácil, pero eliminar un borde es difícil, si no se conocen las ubicaciones del borde en las listas apropiadas.
Extienda esta representación para manejar gráficos ponderados manteniendo tanto el peso como el otro vértice incidente para cada borde en lugar de solo el otro vértice incidente. Los multigrafos ya son representables. Los gráficos dirigidos también se manejan fácilmente con esta representación, de una de varias maneras: almacene solo los bordes en una dirección, mantenga una lista separada de arcos entrantes y salientes, o denote la dirección de cada arco en la lista.
Conectividad
Se dice que un gráfico no dirigido está conectado si hay una ruta desde cada vértice a cualquier otro vértice. El gráfico de ejemplo no está conectado, ya que no hay una ruta desde el vértice 2 al vértice 4.
Sin embargo, si agrega una arista entre el vértice 5 y el vértice 6, entonces el gráfico se conecta. 
Un componente de un gráfico es un subconjunto máximo de los vértices de tal manera que cada vértice es accesible desde cada vértice en el componente. El gráfico de ejemplo original tiene dos componentes: {1, 3, 4, 6} y {2, 5}. Tenga en cuenta que {1, 3, 4} no es un componente, ya que no es máximo.
Se dice que un gráfico dirigido está fuertemente conectado si hay una ruta desde cada vértice a cualquier otro vértice.
Un componente fuertemente conectado de un gráfico dirigido es un vértice u y la colección de todos los vértices v de tal manera que haya una ruta de u a v y una ruta de v a u.
Subgrafos
El gráfico G ‘= (V’, E ‘) es un subgrafo de G = (V, E) si V’ es un subconjunto de V y E ‘es un subconjunto de E.
El subgrafo de G inducido por V ‘es el gráfico (V’, E ‘), donde E’ consiste en todos los bordes de E que se encuentran entre los miembros de V ‘.
Por ejemplo, para V ‘= {1, 3, 4, 2}, el subgrafo inducido es: 
Gráficos especiales
Se dice que un gráfico no dirigido es un árbol si no contiene ciclos y está conectado. 
Muchos árboles son lo que se llama enraizado , donde existe una noción del nodo “superior”, que se llama raíz . Por lo tanto, cada nodo tiene un padre , que es el nodo adyacente que está más cerca de la raíz, y puede tener cualquier número de hijos , que son el resto de los nodos adyacentes. El árbol de arriba fue dibujado como un árbol enraizado.
Un gráfico no dirigido que no contiene ciclos se llama bosque . 
Un gráfico acíclico dirigido a menudo se denomina dag .
Se dice que un gráfico está completo si hay un borde entre cada par de vértices. 
Se dice que un gráfico es bipartito si los vértices se pueden dividir en dos conjuntos V 1 y V 2 , por lo que no hay bordes entre dos vértices de V 1 o dos vértices de V 2 . 
Fuente: Teoría de Gráficos (Capacitación de USACO)
