chapter11.tex

\chapter{Conceptos básicos de grafos}

Muchos problemas de programación pueden resolverse modelando el problema como un problema de grafo y utilizando un algoritmo de grafo apropiado.
Un ejemplo típico de un grafo es una red de carreteras y ciudades en un país.
A veces, sin embargo, el grafo está oculto en el problema y puede ser difícil detectarlo.

Esta parte del libro discute los algoritmos de grafos,
especialmente centrándose en temas que
son importantes en la programación competitiva.
En este capítulo, revisaremos conceptos
relacionados con los grafos,
y estudiaremos diferentes formas de representar grafos en algoritmos.

\section{Terminología de grafos}

\index{graph}
\index{node}
\index{edge}

Un \key{grafo} consiste en \key{nodos}
y \key{aristas}. En este libro,
la variable $n$ denota el número de nodos
en un grafo, y la variable $m$ denota
el número de aristas.
Los nodos están numerados
utilizando enteros $1,2,\ldots,n$.

Por ejemplo, el siguiente grafo consta de 5 nodos y 7 aristas:

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};

\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (1) -- (4);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (2) -- (5);
\path[draw,thick,-] (4) -- (5);
\end{tikzpicture}
\end{center}

\index{path}

Un \key{camino} va del nodo $a$ al nodo $b$
a través de aristas del grafo.
La \key{longitud} de un camino es el número de
aristas en él.
Por ejemplo, el grafo anterior contiene
un camino $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$
de longitud 3
desde el nodo 1 hasta el nodo 5:

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};

\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (1) -- (4);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (2) -- (5);
\path[draw,thick,-] (4) -- (5);

\path[draw=red,thick,->,line width=2pt] (1) -- (3);
\path[draw=red,thick,->,line width=2pt] (3) -- (4);
\path[draw=red,thick,->,line width=2pt] (4) -- (5);
\end{tikzpicture}
\end{center}

\index{cycle}

Un camino es un \key{ciclo} si el primer y último
nodo es el mismo.
Por ejemplo, el grafo anterior contiene
un ciclo $1 \rightarrow 3 \rightarrow 4 \rightarrow 1$.
Un camino es \key{simple} si cada nodo aparece
como máximo una vez en el camino.


% 
% \begin{itemize}
% \item $1 \rightarrow 2 \rightarrow 5$ (length 2)
% \item $1 \rightarrow 4 \rightarrow 5$ (length 2)
% \item $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ (length 3)
% \item $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ (length 3)
% \item $1 \rightarrow 4 \rightarrow 2 \rightarrow 5$ (length 3)
% \item $1 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 5$ (length 4)
% \end{itemize}

\subsubsection{Conectividad}

\index{connected graph}

Un grafo es \key{conectado} si hay un camino
entre dos nodos cualesquiera.
Por ejemplo, el siguiente grafo está conectado:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (2) -- (3);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\end{tikzpicture}
\end{center}

El siguiente grafo no está conectado,
porque no es posible llegar
desde el nodo 4 a ningún otro nodo:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (2) -- (3);
\end{tikzpicture}
\end{center}

\index{component}

Las partes conectadas de un grafo son
llamadas sus \key{componentes}.
Por ejemplo, el siguiente grafo
contiene tres componentes:
$\{1,\,2,\,3\}$,
$\{4,\,5,\,6,\,7\}$ y
$\{8\}$.
\begin{center}
\begin{tikzpicture}[scale=0.8]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};

\node[draw, circle] (6) at (6,1) {$6$};
\node[draw, circle] (7) at (9,1) {$7$};
\node[draw, circle] (4) at (6,3) {$4$};
\node[draw, circle] (5) at (9,3) {$5$};

\node[draw, circle] (8) at (11,2) {$8$};

\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (2) -- (3);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (4) -- (5);
\path[draw,thick,-] (5) -- (7);
\path[draw,thick,-] (6) -- (7);
\path[draw,thick,-] (6) -- (4);
\end{tikzpicture}
\end{center}

\index{tree}

Un \key{árbol} es un gráfico conectado
que consta de $n$ nodos y $n-1$ aristas.
Existe una ruta única
entre dos nodos cualesquiera de un árbol.
Por ejemplo, el siguiente gráfico es un árbol:

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};

\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
%\path[draw,thick,-] (1) -- (4);
\path[draw,thick,-] (2) -- (5);
\path[draw,thick,-] (2) -- (4);
%\path[draw,thick,-] (4) -- (5);
\end{tikzpicture}
\end{center}

\subsubsection{Direcciones de las aristas}

\index{gráfico dirigido}

Un gráfico es \key{dirigido}
si las aristas se pueden recorrer
en una sola dirección.
Por ejemplo, el siguiente gráfico está dirigido:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};
\path[draw,thick,->,>=latex] (1) -- (2);
\path[draw,thick,->,>=latex] (2) -- (4);
\path[draw,thick,->,>=latex] (2) -- (5);
\path[draw,thick,->,>=latex] (4) -- (5);
\path[draw,thick,->,>=latex] (4) -- (1);
\path[draw,thick,->,>=latex] (3) -- (1);
\end{tikzpicture}
\end{center}

El gráfico anterior contiene
una ruta $3 \rightarrow 1 \rightarrow 2 \rightarrow 5$
desde el nodo $3$ hasta el nodo $5$,
pero no hay una ruta desde el nodo $5$ hasta el nodo $3$.

\subsubsection{Pesos de las aristas}

\index{gráfico ponderado}

En un gráfico \key{ponderado}, cada arista se asigna
un \key{peso}.
Los pesos a menudo se interpretan como longitudes de las aristas.
Por ejemplo, el siguiente gráfico está ponderado:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};
\path[draw,thick,-] (1) -- node[font=\small,label=above:5] {} (2);
\path[draw,thick,-] (1) -- node[font=\small,label=left:1] {} (3);
\path[draw,thick,-] (3) -- node[font=\small,label=below:7] {} (4);
\path[draw,thick,-] (2) -- node[font=\small,label=left:6] {} (4);
\path[draw,thick,-] (2) -- node[font=\small,label=above:7] {} (5);
\path[draw,thick,-] (4) -- node[font=\small,label=below:3] {} (5);
\end{tikzpicture}
\end{center}

La longitud de una ruta en un gráfico ponderado
es la suma de los pesos de las aristas en la ruta.
Por ejemplo, en el gráfico anterior,
la longitud de la ruta
$1 \rightarrow 2 \rightarrow 5$ es $12$,
y la longitud de la ruta
$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ es $11$.
La última ruta es la ruta \key{más corta} desde el nodo $1$ hasta el nodo $5$.

\subsubsection{Vecinos y grados}

\index{vecino}
\index{grado}

Dos nodos son \key{vecinos} o \key{adyacentes}
si hay una arista entre ellos.
El \key{grado} de un nodo
es el número de sus vecinos.
Por ejemplo, en el siguiente gráfico,
los vecinos del nodo 2 son 1, 4 y 5,
por lo que su grado es 3.

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};

\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (1) -- (4);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (2) -- (5);
%\path[draw,thick,-] (4) -- (5);
\end{tikzpicture}
\end{center}

La suma de grados en un gráfico es siempre $2m$,
donde $m$ es el número de aristas,
porque cada arista
aumenta el grado de exactamente dos nodos en uno.
Por esta razón, la suma de grados es siempre par.

\index{gráfico regular}
\index{gráfico completo}

Un gráfico es \key{regular} si el
grado de cada nodo es una constante $d$.
Un gráfico es \key{completo} si el
grado de cada nodo es $n-1$, es decir,
el gráfico contiene todas las aristas posibles
entre los nodos.

\index{grado de entrada}
\index{grado de salida}

En un gráfico dirigido, el \key{grado de entrada}
de un nodo es el número de aristas
que terminan en el nodo,
y el \key{grado de salida} de un nodo
es el número de aristas que comienzan en el nodo.
Por ejemplo, en el siguiente gráfico,
el grado de entrada del nodo 2 es 2,
y el grado de salida del nodo 2 es 1.

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (4,3) {$2$};
\node[draw, circle] (3) at (1,1) {$3$};
\node[draw, circle] (4) at (4,1) {$4$};
\node[draw, circle] (5) at (6,2) {$5$};

\path[draw,thick,->,>=latex] (1) -- (2);
\path[draw,thick,->,>=latex] (1) -- (3);
\path[draw,thick,->,>=latex] (1) -- (4);
\path[draw,thick,->,>=latex] (3) -- (4);
\path[draw,thick,->,>=latex] (2) -- (4);
\path[draw,thick,<-,>=latex] (2) -- (5);
\end{tikzpicture}
\end{center}

\subsubsection{Coloraciones}

\index{coloración}
\index{gráfico bipartito}

En una \key{coloración} de un grafo,
cada nodo se asigna un color de modo que
ningún nodo adyacente tenga el mismo color.

Un grafo es \key{bipartito} si
es posible colorearlo utilizando dos colores.
Resulta que un grafo es bipartito
exactamente cuando no contiene un ciclo
con un número impar de aristas.
Por ejemplo, el grafo
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$2$};
\node[draw, circle] (2) at (4,3) {$3$};
\node[draw, circle] (3) at (1,1) {$5$};
\node[draw, circle] (4) at (4,1) {$6$};
\node[draw, circle] (5) at (-2,1) {$4$};
\node[draw, circle] (6) at (-2,3) {$1$};
\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (3) -- (6);
\path[draw,thick,-] (5) -- (6);
\end{tikzpicture}
\end{center}
es bipartito, porque puede colorearse de la siguiente manera:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle, fill=blue!40] (1) at (1,3) {$2$};
\node[draw, circle, fill=red!40] (2) at (4,3) {$3$};
\node[draw, circle, fill=red!40] (3) at (1,1) {$5$};
\node[draw, circle, fill=blue!40] (4) at (4,1) {$6$};
\node[draw, circle, fill=red!40] (5) at (-2,1) {$4$};
\node[draw, circle, fill=blue!40] (6) at (-2,3) {$1$};
\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (3) -- (6);
\path[draw,thick,-] (5) -- (6);
\end{tikzpicture}
\end{center}
Sin embargo, el grafo
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$2$};
\node[draw, circle] (2) at (4,3) {$3$};
\node[draw, circle] (3) at (1,1) {$5$};
\node[draw, circle] (4) at (4,1) {$6$};
\node[draw, circle] (5) at (-2,1) {$4$};
\node[draw, circle] (6) at (-2,3) {$1$};
\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (3) -- (6);
\path[draw,thick,-] (5) -- (6);
\path[draw,thick,-] (1) -- (6);
\end{tikzpicture}
\end{center}
no es bipartito, porque no es posible colorear
el siguiente ciclo de tres nodos usando dos colores:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$2$};
\node[draw, circle] (2) at (4,3) {$3$};
\node[draw, circle] (3) at (1,1) {$5$};
\node[draw, circle] (4) at (4,1) {$6$};
\node[draw, circle] (5) at (-2,1) {$4$};
\node[draw, circle] (6) at (-2,3) {$1$};
\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (3) -- (6);
\path[draw,thick,-] (5) -- (6);
\path[draw,thick,-] (1) -- (6);

\path[draw=red,thick,-,line width=2pt] (1) -- (3);
\path[draw=red,thick,-,line width=2pt] (3) -- (6);
\path[draw=red,thick,-,line width=2pt] (6) -- (1);
\end{tikzpicture}
\end{center}

\subsubsection{Simplicidad}

\index{grafo simple}

Un grafo es \key{simple}
si ninguna arista comienza y termina en el mismo nodo,
y no hay múltiples
aristas entre dos nodos.
A menudo asumimos que los grafos son simples.
Por ejemplo, el siguiente grafo \emph{no} es simple:
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$2$};
\node[draw, circle] (2) at (4,3) {$3$};
\node[draw, circle] (3) at (1,1) {$5$};
\node[draw, circle] (4) at (4,1) {$6$};
\node[draw, circle] (5) at (-2,1) {$4$};
\node[draw, circle] (6) at (-2,3) {$1$};

\path[draw,thick,-] (1) edge [bend right=20] (2);
\path[draw,thick,-] (2) edge [bend right=20] (1);
%\path[draw,thick,-] (1) -- (2);
\path[draw,thick,-] (1) -- (3);
\path[draw,thick,-] (3) -- (4);
\path[draw,thick,-] (2) -- (4);
\path[draw,thick,-] (3) -- (6);
\path[draw,thick,-] (5) -- (6);

\tikzset{every loop/.style={in=135,out=190}}
\path[draw,thick,-] (5) edge [loop left] (5);
\end{tikzpicture}
\end{center}

\section{Representación de grafos}

Hay varias formas de representar grafos
en algoritmos.
La elección de una estructura de datos
depende del tamaño del grafo y
de la forma en que el algoritmo lo procesa.
A continuación, veremos tres representaciones comunes.

\subsubsection{Representación de lista de adyacencia}

\index{lista de adyacencia}

En la representación de lista de adyacencia,
cada nodo $x$ en el grafo se asigna una \key{lista de adyacencia}
que consiste en los nodos
a los que hay una arista desde $x$.
Las listas de adyacencia son las más populares
formas de representar grafos, y la mayoría de los algoritmos se pueden
implementar de manera eficiente utilizando ellos.

Una forma conveniente de almacenar las listas de adyacencia es declarar
una matriz de vectores de la siguiente manera:
\begin{lstlisting}
vector<int> adj[N];
\end{lstlisting}

La constante $N$ se elige de modo que todas
las listas de adyacencia se puedan almacenar.
Por ejemplo, el grafo

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (3,3) {$2$};
\node[draw, circle] (3) at (5,3) {$3$};
\node[draw, circle] (4) at (3,1) {$4$};

\path[draw,thick,->,>=latex] (1) -- (2);
\path[draw,thick,->,>=latex] (2) -- (3);
\path[draw,thick,->,>=latex] (2) -- (4);
\path[draw,thick,->,>=latex] (3) -- (4);
\path[draw,thick,->,>=latex] (4) -- (1);
\end{tikzpicture}
\end{center}
se puede almacenar de la siguiente manera:
\begin{lstlisting}
adj[1].push_back(2);
adj[2].push_back(3);
adj[2].push_back(4);
adj[3].push_back(4);
adj[4].push_back(1);
\end{lstlisting}

Si el gráfico no está dirigido, se puede almacenar de manera similar,
pero cada borde se agrega en ambas direcciones.

Para un gráfico ponderado, la estructura se puede ampliar
de la siguiente manera:

\begin{lstlisting}
vector<pair<int,int>> adj[N];
\end{lstlisting}

En este caso, la lista de adyacencia del nodo $a$
contiene el par $(b,w)$
siempre que haya un borde del nodo $a$ al nodo $b$
con peso $w$. Por ejemplo, el gráfico

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (3,3) {$2$};
\node[draw, circle] (3) at (5,3) {$3$};
\node[draw, circle] (4) at (3,1) {$4$};

\path[draw,thick,->,>=latex] (1) -- node[font=\small,label=above:5] {} (2);
\path[draw,thick,->,>=latex] (2) -- node[font=\small,label=above:7] {} (3);
\path[draw,thick,->,>=latex] (2) -- node[font=\small,label=left:6] {} (4);
\path[draw,thick,->,>=latex] (3) -- node[font=\small,label=right:5] {} (4);
\path[draw,thick,->,>=latex] (4) -- node[font=\small,label=left:2] {} (1);
\end{tikzpicture}
\end{center}
se puede almacenar de la siguiente manera:
\begin{lstlisting}
adj[1].push_back({2,5});
adj[2].push_back({3,7});
adj[2].push_back({4,6});
adj[3].push_back({4,5});
adj[4].push_back({1,2});
\end{lstlisting}

La ventaja de usar listas de adyacencia es que
podemos encontrar de manera eficiente los nodos a los que
podemos movernos desde un nodo dado a través de un borde.
Por ejemplo, el siguiente bucle recorre todos los nodos
a los que podemos movernos desde el nodo $s$:

\begin{lstlisting}
for (auto u : adj[s]) {
    // procesar nodo u
}
\end{lstlisting}

\subsubsection{Representación de matriz de adyacencia}

\index{matriz de adyacencia}

Una \key{matriz de adyacencia} es una matriz bidimensional
que indica qué bordes contiene el gráfico.
Podemos verificar de manera eficiente desde una matriz de adyacencia
si hay un borde entre dos nodos.
La matriz se puede almacenar como una matriz
\begin{lstlisting}
int adj[N][N];
\end{lstlisting}
donde cada valor $\texttt{adj}[a][b]$ indica
si el gráfico contiene un borde de
nodo $a$ a nodo $b$.
Si el borde está incluido en el gráfico,
entonces $\texttt{adj}[a][b]=1$,
y de lo contrario $\texttt{adj}[a][b]=0$.
Por ejemplo, el gráfico
\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (3,3) {$2$};
\node[draw, circle] (3) at (5,3) {$3$};
\node[draw, circle] (4) at (3,1) {$4$};

\path[draw,thick,->,>=latex] (1) -- (2);
\path[draw,thick,->,>=latex] (2) -- (3);
\path[draw,thick,->,>=latex] (2) -- (4);
\path[draw,thick,->,>=latex] (3) -- (4);
\path[draw,thick,->,>=latex] (4) -- (1);
\end{tikzpicture}
\end{center}
se puede representar de la siguiente manera:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (4,4);
\node at (0.5,0.5) {1};
\node at (1.5,0.5) {0};
\node at (2.5,0.5) {0};
\node at (3.5,0.5) {0};
\node at (0.5,1.5) {0};
\node at (1.5,1.5) {0};
\node at (2.5,1.5) {0};
\node at (3.5,1.5) {1};
\node at (0.5,2.5) {0};
\node at (1.5,2.5) {0};
\node at (2.5,2.5) {1};
\node at (3.5,2.5) {1};
\node at (0.5,3.5) {0};
\node at (1.5,3.5) {1};
\node at (2.5,3.5) {0};
\node at (3.5,3.5) {0};
\node at (-0.5,0.5) {4};
\node at (-0.5,1.5) {3};
\node at (-0.5,2.5) {2};
\node at (-0.5,3.5) {1};
\node at (0.5,4.5) {1};
\node at (1.5,4.5) {2};
\node at (2.5,4.5) {3};
\node at (3.5,4.5) {4};
\end{tikzpicture}
\end{center}

Si el gráfico está ponderado, la representación de la matriz de adyacencia
se puede ampliar para que
la matriz contenga el peso del borde
si el borde existe.
Usando esta representación, el gráfico

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (3,3) {$2$};
\node[draw, circle] (3) at (5,3) {$3$};
\node[draw, circle] (4) at (3,1) {$4$};

\path[draw,thick,->,>=latex] (1) -- node[font=\small,label=above:5] {} (2);
\path[draw,thick,->,>=latex] (2) -- node[font=\small,label=above:7] {} (3);
\path[draw,thick,->,>=latex] (2) -- node[font=\small,label=left:6] {} (4);
\path[draw,thick,->,>=latex] (3) -- node[font=\small,label=right:5] {} (4);
\path[draw,thick,->,>=latex] (4) -- node[font=\small,label=left:2] {} (1);
\end{tikzpicture}
\end{center}
\begin{samepage}
corresponde a la siguiente matriz:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (4,4);
\node at (0.5,0.5) {2};
\node at (1.5,0.5) {0};
\node at (2.5,0.5) {0};
\node at (3.5,0.5) {0};
\node at (0.5,1.5) {0};
\node at (1.5,1.5) {0};
\node at (2.5,1.5) {0};
\node at (3.5,1.5) {5};
\node at (0.5,2.5) {0};
\node at (1.5,2.5) {0};
\node at (2.5,2.5) {7};
\node at (3.5,2.5) {6};
\node at (0.5,3.5) {0};
\node at (1.5,3.5) {5};
\node at (2.5,3.5) {0};
\node at (3.5,3.5) {0};
\node at (-0.5,0.5) {4};
\node at (-0.5,1.5) {3};
\node at (-0.5,2.5) {2};
\node at (-0.5,3.5) {1};
\node at (0.5,4.5) {1};
\node at (1.5,4.5) {2};
\node at (2.5,4.5) {3};
\node at (3.5,4.5) {4};
\end{tikzpicture}
\end{center}
\end{samepage}

El inconveniente de la representación de la matriz de adyacencia
es que la matriz contiene $n^2$ elementos,
y por lo general la mayoría de ellos son cero.
Por esta razón, la representación no se puede utilizar
si el gráfico es grande.

\subsubsection{Representación de la lista de aristas}

\index{lista de aristas}

Una \key{lista de aristas} contiene todas las aristas de un gráfico
en algún orden.
Esta es una forma conveniente de representar un gráfico
si el algoritmo procesa todas las aristas del gráfico
y no es necesario encontrar aristas que comiencen
en un nodo dado.

La lista de aristas se puede almacenar en un vector
\begin{lstlisting}
vector<pair<int,int>> edges;
\end{lstlisting}
donde cada par $(a,b)$ denota que
hay una arista del nodo $a$ al nodo $b$.
Por lo tanto, el gráfico

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (3,3) {$2$};
\node[draw, circle] (3) at (5,3) {$3$};
\node[draw, circle] (4) at (3,1) {$4$};

\path[draw,thick,->,>=latex] (1) -- (2);
\path[draw,thick,->,>=latex] (2) -- (3);
\path[draw,thick,->,>=latex] (2) -- (4);
\path[draw,thick,->,>=latex] (3) -- (4);
\path[draw,thick,->,>=latex] (4) -- (1);
\end{tikzpicture}
\end{center}
se puede representar de la siguiente manera:
\begin{lstlisting}
edges.push_back({1,2});
edges.push_back({2,3});
edges.push_back({2,4});
edges.push_back({3,4});
edges.push_back({4,1});
\end{lstlisting}

\noindent
Si el gráfico está ponderado, la estructura puede
extenderse de la siguiente manera:
\begin{lstlisting}
vector<tuple<int,int,int>> edges;
\end{lstlisting}
Cada elemento de esta lista es de la
forma $(a,b,w)$, lo que significa que hay
una arista del nodo $a$ al nodo $b$ con peso $w$.
Por ejemplo, el gráfico

\begin{center}
\begin{tikzpicture}[scale=0.9]
\node[draw, circle] (1) at (1,3) {$1$};
\node[draw, circle] (2) at (3,3) {$2$};
\node[draw, circle] (3) at (5,3) {$3$};
\node[draw, circle] (4) at (3,1) {$4$};

\path[draw,thick,->,>=latex] (1) -- node[font=\small,label=above:5] {} (2);
\path[draw,thick,->,>=latex] (2) -- node[font=\small,label=above:7] {} (3);
\path[draw,thick,->,>=latex] (2) -- node[font=\small,label=left:6] {} (4);
\path[draw,thick,->,>=latex] (3) -- node[font=\small,label=right:5] {} (4);
\path[draw,thick,->,>=latex] (4) -- node[font=\small,label=left:2] {} (1);
\end{tikzpicture}
\end{center}
\begin{samepage}
se puede representar de la siguiente manera\footnote{En algunos compiladores antiguos, la función
\texttt{make\_tuple} debe utilizarse en lugar de las llaves (por ejemplo,
\texttt{make\_tuple(1,2,5)} en lugar de \texttt{\{1,2,5\}}).}:
\begin{lstlisting}
edges.push_back({1,2,5});
edges.push_back({2,3,7});
edges.push_back({2,4,6});
edges.push_back({3,4,5});
edges.push_back({4,1,2});
\end{lstlisting}
\end{samepage}