%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 19 Jun 2007 09:48:41am BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\usepackage{fullpage}
\usepackage{setspace}

\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 2007} %\date{Versão de \today}
\maketitle
\footskip=20pt

\vspace{-\medskipamount}
\noindent{\bf Instruções:}
\begin{enumerate}\small
\item Não destaque as folhas do caderno de soluções.
\item A prova pode ser feita a lápis.  Cuidado com a legibilidade.
%\item Há~$3$ questões na prova. Verifique antes de começar a prova
%se o seu caderno de questões está completo.
\item Não é permitido o uso de folhas avulsas para rascunho.
%\item Nas questões que envolvem elaboração de programas, coloque
%comentários suficientes para que o programa seja facilmente
%compreendido.
\item Não é necessário apagar rascunhos no caderno de soluções.
\item Asserções imprecisas valem pouco.  Justifique suas asserções (dentro do
  razoável!). 
\end{enumerate}

\smallskip
\onehalfspacing

\noindent\textbf{Faça no máximo 3 questões.}

\begin{enumerate}
\thispagestyle{empty}  
\item{}[4~pontos] Considere a implementação do algoritmo de Kosaraju vista em sala:
  {\small
\begin{verbatim}
static int post[maxV], postR[maxV];
static int cnt0, cnt1;
void SCdfsR(Graph G, int w)
  { link t;
    G->sc[w] = cnt1; 
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (G->sc[t->v] == -1) SCdfsR(G, t->v); 
    post[cnt0++] = w;
  }
int GRAPHsc(Graph G)
  { int v; Graph R = GRAPHreverse(G);
    cnt0 = 0; cnt1 = 0;
    for (v = 0; v < G->V; v++) R->sc[v] = -1;
    for (v = 0; v < G->V; v++) if (R->sc[v] == -1) SCdfsR(R, v);
    cnt0 = 0; cnt1 = 0;
    for (v = 0; v < G->V; v++) G->sc[v] = -1;
    for (v = 0; v < G->V; v++) postR[v] = post[v];
    for (v = G->V-1; v >= 0; v--)
      if (G->sc[postR[v]] == -1)
        { SCdfsR(G, postR[v]); cnt1++; }
    GRAPHdestroy(R);
    return cnt1;
  }
\end{verbatim}
}\noindent
Seja~$G$ o grafo dirigido com~$10$ vértices e~$20$ arcos dado por {\small
\begin{verbatim}
0: 5                | 5: 9              
1: 2 4              | 6: 8 4 5 1 9 2 7  
2: 6                | 7: 3 8 1          
3:                  | 8: 5              
4: 3                | 9: 8 0 4          
\end{verbatim}
}%
\noindent 
(\textit{i})~Desenhe~$G$.  (\textit{ii})~Simule a execução de %
\verb|GRAPHsc(G)|, ilustrando as etapas principais desta simulação.
Idealmente, diga conceitualmente o que está acontecendo em cada fase do
algoritmo.

\item{}[3~pontos] Sejam~$G=(V,E)$ um grafo e $c\:E\to\RR$ uma função custo nas
  arestas de~$G$.  Por simplicidade, suponha que~$c$ é injetora.  Suponha que
  $E=\{e_1,\dots,e_m\}$ e $c(e_1)<c(e_2)<\dots<c(e_m)$.
  \begin{enumerate}
  \item[(\textit{i})] Sejam~$T$ uma árvore geradora de~$G$ e~$T_0$ a árvore
    geradora mínima (AGM) obtida executando-se o algoritmo de Kruskal
    sobre~$G$.  Suponha que~$T\neq T_0$.  Dizemos que uma aresta~$e\in E$
    \textit{distingue}~$T$ de~$T_0$ se~$e$ pertence a uma das árvores mas não
    pertence a outra, isto é, $e\in (E(T)\setminus E(T_0))\cup(E(T_0)\setminus
    E(T))$.  Seja~$i_0$ o menor inteiro~$i$ tal que~$e_i$ distingue~$T$
    e~$T_0$.  Prove que~$e_{i_0}\in E(T_0)\setminus E(T)$.
    
  \item[(\textit{ii})] Seja~$i_0$ como em~(\textit{i}) e ponha~$f=e_{i_0}$.
    Prove que existe~$e\in E\setminus\{f\}$ que distingue~$T$ e~$T_0$ tal
    que~$T'=T+f-e$ é uma árvore geradora de~$G$.
      
  \item[(\textit{iii})] Prove que $c(T')<c(T)$, onde~$T'$ é a árvore geradora
    em~(\textit{ii}) acima.
    
  \item[(\textit{iv})] Suponha que~$T$ é uma árvore geradora de~$(G,c)$ que
    não tem custo mínimo.  Prove que existem arestas~$e$ e~$f$ em~$G$ tais que
    $T'=T-e+f$ tem custo menor que~$T$.

  \end{enumerate}

\item{}[3~pontos] Considere a rede a seguir, com as capacidades indicadas:
{\small
\begin{verbatim}
0: 1(6) 2(6) 3(4) 4(4)
1: 5(5)
2: 1(4) 6(6)
3: 6(5) 7(8) 
4: 3(5) 
5: 6(4) 9(4)
6: 9(8)
7: 8(5) 9(4)
8: 4(4) 9(3)
9: 
\end{verbatim}
  } Na notação acima, por exemplo, \verb|0: 1(6)| significa que há um arco
  de~\verb|0| para~\verb|1| com capacidade~\verb|6|.  Suponha que~$s=0$
  e~$t=9$.  
  \begin{enumerate}
  \item[(\textit{i})] Desenhe a rede, com as capacidades indicadas. 
  \item[(\textit{ii})] Encontre um fluxo máximo de~$s$ para~$t$ nesta rede.
  \item[(\textit{iii})] \textit{Prove} que o fluxo que você deu
    em~(\textit{ii}) é de fato máximo.
  \end{enumerate}

\item{}[3~pontos]
  \begin{enumerate}
  \item[(\textit{i})] Enuncie o teorema de Hall, que dá uma condição
    necessária e suficiente para a existência de certos emparelhamentos em
    grafos.
    
  \item[(\textit{ii})] Seja~$B$ um grafo bipartido com bipartição~$V=U\cup W$.
    Suponha que~$|U|=|W|=m$ e que todos os vértices de~$B$ têm grau maior
    que~$m/2$.  Prove que~$B$ tem um emparelhamento de tamanho~$m$.
  \end{enumerate}

\end{enumerate}

\end{document}

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

