<aside> ☝🏻 Grafo dirigido es un par $G(V, A)$ donde $V$ es un conjunto de elementos (objetos, puntos) que llamaremos vértices o nodos. $A$ es un subconjunto de pares ordenados de $V$

$$ A\subseteq\{(i, j)\colon i, j\in V\} $$

que llamamos arcos.

</aside>

En este tema seguiremos el convenio de que los pares dados entre $()$ siguen un orden, mientras que los pares dados $\{\}$ no tienen orden.

<aside> ☝🏻 Grafo no dirigido es un par $G(V, E)$ donde $V$ son los vértices o nodos, y $E$ es un subconjunto de pares nos ordenados de

$$ E\subseteq \{\{i, j\}\colon i,j\in V\} $$

que llamamos aristas.

</aside>

Observación: un grafo no dirigido puede verse como un grafo dirigido que contiene para cada arista $\{i, j\}$ los dos arcos $(i, j)$ y $(j,i)$.

A efectos de notación $\#A = m$ y $\#V=n$

<aside> ☝🏻 Dado $S\subseteq V$ definimos como $\Gamma(S)$ a los sucesores de $S$ al conjunto

$$ \Gamma(S) = \{j\in S\colon i\in S, (i, j)\in A\} $$

donde $\Gamma(i) = \Gamma(\{i\})$.

</aside>

<aside> ☝🏻 Dado $S\subseteq V$ definimos los predecesores de $S$ al conjunto

$$ \Gamma^{-1}(S)=\{j\in V\colon i\in S, (j,i)\in A\} $$

</aside>

Si el grafo $G(V, E)$ es no dirigido podemos definir de forma similar las funciones $\Gamma$ y $\Gamma^{-1}$:

$$ \Gamma(S)= \{j\in V\colon i\in S, \{i,j\}\in E\} $$

<aside> 📝 $\Gamma(S)\equiv$ los vértices a los que se puede ir desde $S$ $\Gamma^{-1}(S)\equiv$ los vértices que llegan a $S$

</aside>

Caminos y cadenas

Para grafos dirigidos

<aside> ☝🏻 Un camino es una secuencia de arcos donde el vértice final de un arco coincide con el vértice de inicio del siguiente arco. Los escribimos con los arcos uno a continuación del otro (importando el orden).

• Diremos que un camino es simple si no repite ningún arco.
• Diremos que un camino es elemental si no repite ningún vértice. </aside>

En rojo el camino $(1,2)(2,3)(3,4)$

Si un camino es elemental entonces es simple.

Para grafos no dirigidos

<aside> ☝🏻 Una cadena es una secuencia de aristas donde el vértice final de una arista coincide con el vértice de inicio de la siguiente arista. Las escribimos con las aristas una a continuación de otra (importando el orden).

• Diremos que una cadena es simple si no repite ninguna arista.
• Diremos que un cadena es elemental si no repite ningún vértice. </aside>

En rojo la cadena $[1,2][2,3][3,4]$

A efectos de notación serán equivalentes $G(V,A)$ y $G=(V, A)$. Además, cuando hablemos de aristas las indicamos entre llaves o corchetes.

En ocasiones los caminos o cadenas se suelen dar como la sucesión de los vértices recorridos, por tanto el camino y la cadena de los ejemplos anteriores sería $1,2,3,4$

Pesos, costos, distancias…

Es usual asociar a cada arco (arista) un cierto peso, costo o distancia, esta será una función de la forma