%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Time-stamp: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[11pt,reqno]{amsart} %% Escrevendo em português: \usepackage[brazil]{babel} \usepackage[latin1]{inputenc} %---------------------------- %\usepackage{refcheck} \usepackage{srcltx} \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} %\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\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\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\sugestao#1{[\textit{Sugestão.} #1]} \def\observacao#1{[\textit{Observação.} #1]} \begin{document} \title[MAC0328 Algoritmos em Grafos]{Segunda Prova de Algoritmos em grafos\\BCC, 1{\tiny o.} semestre de 2004} %\date{Versão de \today} \maketitle \footskip=20pt %\noindent\textbf{Instruções.} %\bigskip \begin{enumerate} \thispagestyle{empty} \item{}[2~pontos] Descreva o que ocorre quando executamos o algoritmo de Kosaraju em um DAG. \item{}[3~pontos] Seja~$G$ um grafo conexo e~$c\:E(G)\to\RR$ uma função custo definida nas arestas de~$G$. Por simplicidade, suponha que~$c$ é injetora, isto é, não há arestas com custos iguais em~$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 do corte $E(V(T_1^e),V(T_2^e))=\big\{\{u,v\}\in E(G)\:u\in V(T_1^e),\;v\in V(T_2^e)\big\}$. \end{enumerate} \sugestao{Para provar que~(\textit{ii}) implica~(\textit{i}), faça o seguinte: suponha que~$T$ não seja uma árvore mínima e seja~$T^*$ uma árvore mínima. Seja~$e$ uma aresta em~$E(T)\setminus E(T^*)$, e considere~$E(V(T_1^e),V(T_2^e))$. Seja~$f$ uma aresta em~$E(T^*)\cap E(V(T_1^e),V(T_2^e))$ adequada. Considere~$T^*+e-f$.} \item\label{q:pot}[3~pontos] 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$. \item{}[4~pontos] 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} \end{enumerate} \end{document} % Local Variables: % mode: latex % eval: (Portug-mode) % TeX-master: t % End: