%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC328 Algoritmos em Grafos                          %
% 1o. semestre de 2005                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 17 May 2007 09:54:15am BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref} 

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}
\usepackage{multicol}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cT{\mathcal T}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\comp{^{\text{\rm c}}}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC328 Algoritmos em Grafos]{Exercícios de Algoritmos em
  Grafos\\1{\tiny o.} semestre de 2005}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\begin{enumerate}
\item Desenhe todos os grafos não-isomorfos com~$n$ vértices para todo~$0\leq
  n\leq4$.  (Por exemplo, para~$n=2$, você deve desenhar~$2$ grafos.)
  
\item Uma \textit{floresta} é um grafo acíclico (isto é, que não contém
  circuitos).  Uma \textit{árvore} é uma floresta conexa.  Desenhe todas as
  árvores com conjunto de vértices~$[n]=\{1,\dots,n\}$ para todo~$0\leq
  n\leq4$.  (Por exemplo, para~$n=3$, você deve desenhar~$3$ árvores.)
  
\item Seja~$g_n$ ($n\geq0$) o número total de grafos não-isomorfos com~$n$
  vértices (por exemplo, $g_2=2$).  Mostre que
  \begin{equation}
    \label{eq:g_n_ineq}
    2^{n\choose2}/n!\leq g_n\leq2^{n\choose2}.
  \end{equation}
  \datedue{12/4/2005}
  
\item{}[Desafio] Desenvolva um sistema computacional para determinar ou
  estimar~$g_n$ para valores grandes de~$n$. \datedue{em aberto}
  
\item (Exemplo~1.15 de ISTG) Duas arestas de um grafo~$G$ são
  \textit{adjacentes} se têm uma ponta comum.  Essa relação de adjacência
  define o \textit{grafo das arestas} de~$G$.  Se~$G'$ denota o grafo das
  arestas de~$G$, então~$V(G)=A(G)$ e cada aresta de~$G'$ é um par~$ab$ em
  que~$a$ e~$b$ são arestas adjacentes de~$G$.  Faça uma figura do grafo das
  arestas de um~$K_3$ e de um~$K_{1,3}$ (o grafo completo com~$3$ vértices e o
  grafo bipartido completo com classes de vértices de cardinalidades~$1$
  e~$3$).
  
  Faça uma figura do grafo das arestas de um~$K_4$.  Quantos vértices e
  quantas arestas tem o grafo das arestas de um~$K_n$?  Seja~$G$ o grafo das
  arestas de um~$K_5$.  Desenhe o \textit{complemento}~$G\comp=\overline G$
  de~$G$ (o grafo com conjunto de vértices~$V(G)$, com dois vértices
  distintos~$x$ e~$y$ de~$V(G)$ adjacentes neste grafo se e só se~$x$ e~$y$
  não são adjacentes em~$G$).
  
\item (E~1.17 de ISTG) Mostre que o grafo das arestas de um~$K_5$
  é isomorfo ao complemento do grafo de Petersen.

\item (Proposição~1.1 de ISTG) Prove que, em todo grafo, a soma dos graus dos
  vértices é igual ao dobro do número de arestas.  Ou seja, mostre que todo
  grafo~$(V,A)$ satisfaz a identidade~$\sum_{v\in V}g(v)=2|A|$.
  
\item (E~1.20 de ISTG) Mostre que todo grafo tem um número par de vértices de
  grau ímpar.
  
\item (E~1.21 de ISTG) Mostre que todo grafo com dois ou mais vértices tem
  pelo menos dois vértices de mesmo grau.
  
\item Mostre que todo grafo~$G$ com pelo menos um vértice contém um caminho de
  comprimento~$\delta(G)$.  Mostre que todo grafo~$G$ contém um circuito de
  comprimento pelo menos~$\delta(G)+1$, desde que~$\delta(G)\geq2$.

\item Seja~$G$ um grafo conexo.  Considere a família~$\cF$ dos caminhos de
  comprimento máximo em~$G$.
  \begin{itemize}
  \item[(\textit{i})] Prove que quaisquer dois caminhos em~$\cF$ têm um
    vértice em comum.
  \item[(\textit{ii})] Suponha agora que os caminhos em~$\cF$ têm comprimento
    ímpar.  Prove que quaisquer dois caminhos em~$\cF$ têm pelo menos dois
    vértices em comum. 
  \end{itemize}
  \datedue{12/4/2005}
  
\item (Proposição~1.2 de ISTG) Prove que um grafo~$G$ é conexo se e somente
  se~$\nabla(X)\neq\emptyset$ para todo subconjunto próprio e não-vazio~$X$
  de~$V(G)$. 
  
\item (E~1.39 de ISTG) Seja~$G$ um grafo com~$\delta(G)>(|V(G)|-2)/2$.  Mostre
  que~$G$ é conexo.
  
\item (E~1.40 de ISTG) Seja~$G$ um grafo com~$\delta(G)\geq3$.  Mostre que~$G$
  tem um circuito par.
  
\item Seja~$G$ um grafo conexo com pelo menos dois vértices.  Mostre que há
  dois vértices distintos~$x$ e~$y$ em~$G$ tais que ambos~$G-x$ e~$G-y$ são
  conexos. 
  
\item (E~1.41 de ISTG) Mostre que todo grafo~$G$ satisfaz a desigualdade
  $|E(G)|\geq|V(G)|-c(G)$, onde~$c(G)$ é o número de componentes de~$G$.
  \datedue{12/4/2005}
  
% \item Estude as implementações para o tipo abstrato de dados \texttt{Graph}
%   dadas nos programas~17.3 e~17.6.  Implemente a função \texttt{GRAPHremoveE}
%   para a implementação com listas ligadas.
  
\item Seja~$G$ um grafo conexo e~$T$ uma árvore geradora de~$G$ obtida pela
  execução de uma busca de profundidade em~$G$.  Dê um argumento preciso para
  provar que toda arestas em~$A(G)\setminus A(T)$ é da forma~$\{x,y\}$ com~$x$
  um ancestral de~$y$ em~$T$.  (Lembre que~$T$ tem uma raiz natural, a saber,
  o vértice~$r$ a partir do qual a busca em profundidade foi disparada.
  Dizemos que~$x$ é um ancestral de~$y$ em~$T$ se o único caminho de~$r$ a~$y$
  em~$T$ passa por~$x$.)  \datedue{12/4/2005}
  
\item Sejam~$G$ um grafo e~$v$ e~$w$ dois vértices de~$G$.  Mostre que se
  existe em~$G$ um passeio com extremos~$v$ e~$w$, então existe uma caminho
  com extremos~$v$ e~$w$ em~$G$.  

\item Desenhe o grafo com~$8$ vértices e~$10$ arestas dado por
%  \begin{multicols}{2}
  \begin{verbatim}
 0:  7  5  2
 1:  7
 2:  6  0
 3:  5  4
 4:  5  7  3  6
 5:  0  4  3
 6:  4  2
 7:  0  1  4
\end{verbatim}
    \noindent Simule a execução de \verb|dfsR(G, {0,0})| (busca em
    profundidade a partir do vértice~\verb|0|).  Determine os
    vetores~\verb|pre[]| e~\verb|st[]| após a execução desta chamada.
    Classifique todas os pares ordenados~$(a,b)$ com~$ab\in A(G)$ nos quatro
    tipos (\textit{i})~tipo árvore, (\textit{ii})~tipo pai,
    (\textit{iii})~tipo ascendente, (\textit{iv})~tipo descendente.
%  \end{multicols}

\item Para cada inteiro~$n>0$, seja~$P_n$ a probabilidade de o grafo
    aleatório com~$n$ vértices e~$m$ arestas ser conexo, onde
  \begin{equation}
    \label{eq:conn_thresh}
    m=\llfloor{1\over2}n\log n\rrfloor
  \end{equation}
  ($\log n$ acima é na base~$\e=2.718\dots$).  Naturalmente, aqui consideramos
  todos os~${{n\choose2}\choose m}$ grafos $n$~vértices e $m$~arestas
  equiprováveis.  Estime~$P_n$ para~$n$ grande através de experimentos
  computacionais.  \observacao{Sabe-se que~$L=\lim_{n\to\infty}P_n$ existe
    e~$0<L<1$.  Neste exercício, queremos estimar este limite.}
  \datedue{15/4/2005 (O Panda estará de pé em breve para você entregar sua
    solução, que deve consistir de seu(s) programa(s) e um pequeno relatório
    com suas conclusões.)}

\item Seja~$G$ um grafo $2$-aresta-conexo.  Prove que para quaisquer dois
  vértices distintos~$x$ e~$y$ de~$G$, existem dois caminhos~$P_1$ e~$P_2$
  de~$x$ a~$y$ que são disjuntos nas arestas (isto é, $E(P_1)\cap
  E(P_2)=\emptyset$).  \datedue{19/4/2005}
  
\item Escreva um programa que, dado um grafo~$G$ como entrada, determina os
  componentes conexos de~$G$, os vértices de corte de~$G$, e os
  \textit{blocos} de~$G$ (os \textit{blocos} de~$G$ são os subgrafos de~$G$
  gerados pelas classes de equivalência da relação~$e\sim f$ se e só se as
  arestas~$e$ e~$f$ são iguais ou pertencem a um mesmo circuito).  Para
  descrever os componentes e os blocos de~$G$, o seu programa pode
  simplesmente imprimir o conjunto de vértices presentes nestes componentes e
  blocos.  O seu programa deve ter complexidade de tempo~$O(n+m)$, onde, como
  de usual, $n$~é o número de vértices em~$G$ e~$m$ é o número de arestas
  em~$G$.  Experimente executar \textit{o seu programa} nestes grafos:
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g1.gr},
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g2.gr},
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g3.gr}, e
  nos grafos \verb|book("anna",10,0,15,20,1,1,0)| e
  \verb|book("homer",561,0,1,24,1,1,0)| do Stanford GraphBase.  (Note que os
  grafos
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g2.gr} e
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g3.gr} são
  um tanto grandes.)  (Entregue pelo Panda) \datedue{3/5/2005}
  
\item Familiarize-se com a plataforma \textsl{Stanford GraphBase} de Knuth.
  Para tanto, leia, pelo menos em algum detalhe, os Capítulos~1 a~4 do livro
  \href{http://www-cs-staff.stanford.edu/~knuth/sgb.html}{\textsl{Stanford
      GraphBase}}.  Uma ótima fonte local é uma
  \href{http://www.ime.usp.br/~coelho/grafos/}{página de uma edição de mac328}
  mantida pelo \href{http://www.ime.usp.br/~coelho/}{professor Coelho}.
  Finalmente, você deve entregar o seguinte: escreva um programa baseado no
  \texttt{queen.w} que gera \textit{três} grafos interessantes.  Você deve
  descrever os seus grafos em um pequeno texto, explicando a razão de sua
  escolha.  Seu programa deve imprimir uma descrição de seus grafos,
  possivelmente salientando as suas características que você achou
  interessantes.  (Entregue pelo Panda.) \datedue{3/5/2005}
  
\item Neste exercício, trataremos de árvores aleatórias.  O objetivo é
  determinar experimentalmente a \textit{altura esperada} de certas árvores
  aleatórias.  Você deve executar seus experimentos para valores de~$n$
  razoavelmente grandes, onde~$n$ é o número de vértices nas árvores
  aleatórias em questão.  As árvores aleatórias que consideraremos são
  definidas assim:
  \begin{itemize}
  \item[$\vartriangleright$] Considere o grafo completo~$K_n$ sobre o conjunto
    de vértices $\{0,\dots,n-1\}$.  Podemos gerar uma árvore aleatória com
    raiz~$0$ sobre~$\{0,\dots,n-1\}$ executando uma busca aleatória em~$K_n$ a
    partir de~$0$ (considere a busca aleatória discutida em sala).  Seja~$R_n$
    uma tal árvore aleatória.  Estime experimentalmente o valor esperado da
    altura~$h(R_n)$ de~$R_n$.  \textbf{Use a seguinte versão do Programa
      18.10}:{\small
\begin{verbatim}

void rfs(Graph G, Edge e)
  { link t; int v, w;
    RQput(e); 
    while (!RQempty())
      if (pre[(e = RQget()).w] == -1)
        { link t;
          pre[e.w] = cnt++; st[e.w] = e.v;
          for (t = G->adj[e.w]; t != NULL; t = t->next)
            if (pre[v = t->v] == -1)
                RQput(EDGE(e.w, v)); 
        }
  }

\end{verbatim}}
    O programa acima é como o Programa 18.8 do Sedgewick (apenas troquei os
    \verb|QUEUE| por \verb|RQ| (\textit{random queue})).  Note que,
    basicamente, o Programa 18.9 está para o Programa 18.8, como o Programa
    18.10 está para o programa acima.
  \end{itemize}
  \datedue{6/5/2005}
  
\item Seja~$G=(V,E)$ um grafo.  Podemos definir um grafo dirigido~$\vec
  G=(V,\vec E)$ a partir de~$G$, atribuindo para cada aresta~$e=\{x,y\}$
  de~$G$ uma de suas duas possíveis orientações (formalmente,
  temos~$(x,y)\in\vec E$ ou~$(y,x)\in\vec E$, mas não ambos).  Podemos chamar
  um tal~$\vec G$ de uma \textit{orientação} de~$G$.  Prove que existe uma
  orientação fortemente conexa de~$G$ se e só se~$G$ é conexo e não tem
  arestas de corte.  \datedue{10/5/2005}
  
\item Escreva um algoritmo que, dado um DAG~$D$, determina o comprimento
  máximo de um caminho dirigido em~$D$ (basta entregar um pseudocódigo em
  papel).  \datedue{17/5/2005}

\item 
  \begin{enumerate}
  \item[(\textit{i})]Descreva o que ocorre quando executamos o algoritmo de
    Kosaraju em um DAG; mais precisamente, descreva como o algoritmo evolui ao
    processar o DAG (não descreva apenas a saída).
  
  \item[(\textit{ii})]Descreva o que ocorre quando executamos o algoritmo de
    Tarjan em um DAG.

  \end{enumerate}\datedue{20/5/2005}
  
\item O algoritmo de Kosaraju para a determinação dos componentes fortemente
  conexos de um grafo dirigido envolve o cômputo do reverso de~$\vec G$;
  depois usamos o \textit{reverso} da ordem dada por \verb|post[]|.  Uma
  sugestão natural é usar o grafo original~$\vec G$ (\textit{sem}
  revertê-lo) e usar então a ordem dada por \verb|post[]| \textit{sem}
  revertê-la.  Esta idéia funciona?  Prove ou dê um contra-exemplo.
  \datedue{31/5/2005}

\item\label{ex:optim1} Seja~$G$ um grafo e~$c\:E(G)\to\RR$ uma função custo
  definida nas arestas de~$G$.  Seja~$T$ uma árvore geradora de~$G$.
  Para~$e\in E(T)$, sejam~$T_1^e$ e~$T_2^e$ os dois componentes de~$T-e$.
  Prove que são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})] $T$~é uma árvore geradora de custo mínimo em~$G$.
  \item[(\textit{ii})] Toda aresta~$e\in E(T)$ tem peso mínimo dentre as
    arestas em $E(V(T_1^e),V(T_2^e))$.
  \end{enumerate}\datedue{exercício recomendado, sem data de entrega}
  
\item Sejam~$G$ e~$c$ como no Exercício~\ref{ex:optim1}.  Seja~$T$ uma árvore
  geradora de~$G$.  Lembre que se~$e\in E(G)\setminus E(T)$, então o
  grafo~$T+e$ contém um único circuito, chamado de \textit{circuito
    fundamental de~$e$ em relação a~$T$}, freqüentemente denotado
  por~$C(e,T)$.  Prove que são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})] $T$~é uma árvore geradora de custo mínimo em~$G$.
  \item[(\textit{ii})] Toda~$e\in E(G)\setminus E(T)$ tem peso máximo dentre
    as arestas em $C(e,T)$.
  \end{enumerate}\datedue{exercício recomendado, sem data de entrega}
  
\item Seja~$G=(V,E)$ um grafo.  Podemos definir um grafo
  dirigido~$\vec G=(V,\vec E)$ a partir de~$G$, atribuindo para cada
  aresta~$e=\{x,y\}$ de~$G$ uma de suas duas possíveis orientações
  (formalmente, temos~$(x,y)\in\vec E$ ou~$(y,x)\in\vec E$, mas não ambos).
  Podemos chamar um tal~$\vec G$ de uma \textit{orientação} de~$G$.  Suponha
  que~$G$ tem duas árvores geradoras~$T_1$ e~$T_2$ disjuntas nas arestas, isto
  é, $T_1$~e~$T_2$ são subárvores de~$G$ com~$V(T_1)=V(T_2)=V(G)$ e
  $E(T_1)\cap E(T_2)=\emptyset$.  Mostre que~$G$ admite uma orientação~$\vec
  G$ fortemente conexa, isto é, uma orientação~$\vec G$ tal que, para
  quaisquer~$x$ e~$y\in V(\vec G)$, há um caminho dirigido de~$x$ para~$y$.
  \datedue{exercício recomendado, sem data de entrega}

\item\label{q:pot} Seja~$G$ um grafo dirigido e~$c\:E(G)\to\RR$ um
  função custo definida nos arcos de~$G$.  Por simplicidade, suponha que o
  custo de todo arco é não-negativo.  Fixe~$s\in V(G)$, e suponha que todo
  vértice de~$G$ é acessível a partir de~$s$.  Para todo~$x\in V(G)$,
  escrevemos~$d_c(s,x)$ para o custo mínimo dos caminhos dirigidos de~$s$
  a~$x$.  Um \textit{potencial~$p$ para~$(G,c)$} é uma função $p\:V(G)\to\RR$
  tal que
  \begin{equation}
    \label{eq:pot_prop}
    p(v)\leq p(u)+c(u,v)\text{ para todo~$(u,v)\in E(G)$}.
  \end{equation}
  Ademais, dizemos que um arco~$(u,v)$ é \textit{justo} se vale a
  \textit{igualdade} em~\eqref{eq:pot_prop}.  Suponha que um potencial~$p$
  satisfaz as seguintes duas propriedades:
  \begin{enumerate}
  \item[(\textit{a})]$p(s)=0$,
  \item[(\textit{b})]todo vértice~$x\in V(G)$ é acessível a partir de~$s$
    por um caminho que só contém arcos justos.
  \end{enumerate}
  Prove os seguintes fatos:
  \begin{enumerate}
  \item[(\textit{i})]Para todo~$x\in V(G)$, vale que $p(x)\leq d_c(s,x)$.
    \observacao{Para este item, a única hipótese necessária sobre o
      potencial~$p$ é que~$p(s)\leq0$.}
  \item[(\textit{ii})]Para todo~$x\in V(G)$, vale que $d_c(s,x)\leq p(x)$.
    \sugestao{Seja~$(P_k)$ a seguinte asserção: \textsl{se~$x$ é acessível a
        partir de~$s$ através de um caminho com~$k$ arcos, todos eles justos,
        então~$d_c(s,x)\leq p(x)$}.  Prove que~$(P_k)$ vale para todo~$k$ por
      indução em~$k$.}
  \end{enumerate}
  Conclua que~$d_c(s,x)=p(x)$ para todo vértice~$x$ de~$G$.
  \datedue{exercício recomendado, sem data de entrega} 
  
\item Considere a implementação do algoritmo de Dijkstra visto em
  sala (Programa~21.1): {\small
\begin{verbatim}
#define GRAPHpfs GRAPHspt
#define P (wt[v] + t->wt)
void GRAPHpfs(Graph G, int s, int st[], double wt[])
  { int v, w;  link t;
    PQinit(); priority = wt;
    for (v = 0; v < G->V; v++)
      { st[v] = -1; wt[v] = maxWT; PQinsert(v); }
    wt[s] = 0.0; PQdec(s);
    while (!PQempty())
      if (wt[v = PQdelmin()] != maxWT)
        for (t = G->adj[v]; t != NULL; t = t->next)
          if (P < wt[w = t->v]) 
            { wt[w] = P; PQdec(w); st[w] = v; }
  }
\end{verbatim}
  } Seja~$G$ o grafo de~$5$ vértices e~$10$ arcos com custos nos arcos dado
  por {\small
\begin{verbatim}
0: 1(5) 3(10)
1: 2(2) 3(3) 4(9)
2: 0(7) 4(6)
3: 1(2) 4(1)
4: 2(4)
\end{verbatim}
  } Na notação acima, por exemplo, \verb|0: 1(5)| significa que há um arco
  de~\verb|0| para~\verb|1| de custo~\verb|5|.  
  \begin{enumerate}
  \item[(\textit{i})]Execute o Programa~21.1 no grafo~$G$ dado acima,
    com~$s=0$, ilustrando a evolução do algoritmo através de diagramas
    convenientes (uns~6 diagramas bastam).
  \item[(\textit{ii})]Determine um potencial~$p\:V(G)\to\RR$ para certificar
    que você encontrou as distâncias de~$0$ a todos os outros vértices em~$G$
    em~(\textit{i}) acima corretamente (veja a Questão~\ref{q:pot}).  Você
    deve dizer explicitamente por que sua função~$p$ é um potencial e por que
    ela de fato certifica as distâncias encontradas.
  \item[(\textit{iii})]Descreva um algoritmo de complexidade~$O(n+m)$ que
    poderia ser executado após o Programa~21.1 para verificar que de fato as
    distâncias a partir de~$s$ foram determinadas corretamente.  Por
    simplicidade, suponha que todos os vértices de~$G$ são acessíveis a partir
    de~$s$.  (Como você pode se livrar dessa hipótese?)
  \end{enumerate}
  \datedue{exercício recomendado, sem data de entrega} 

\end{enumerate}  
 
\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
