%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Arquivo LaTeX2e para % % % % Exercícios de MAC328 Algoritmos em Grafos % % 1o. semestre de 2004 % % Y. Kohayakawa % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Time-stamp: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[11pt,reqno]{amsart} \usepackage[colorlinks,backref]{hyperref} %% 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} \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\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 2004} \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.) \datedue{9/3/2004} \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{9/3/2004} \item{}[Desafio] Desenvolva um sistema computacional para determinar ou estimar~$g_n$ para valores grandes de~$n$. \datedue{em aberto} \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/3/2004} \item Determine o vertebrado correspondente à função \begin{equation} \label{eq:uma_f} f=\(\begin{matrix} 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ a\ b\ c\ d\ e\ f\\ 0\ b\ f\ e\ c\ 3\ d\ 4\ 8\ 4\ 7\ 4\ 2\ e\ e\ 9 \end{matrix}\) \end{equation} \datedue{16/3/2004} \item Prove que todo grafo~$G$ com~$6$ vértices contém um clique com~$3$ vértices ou um conjunto independente com~$3$ vértices; isto é, $\omega(G)\geq3$ ou~$\alpha(G)\geq3$. Mostre que esta asserção é falsa para grafos com~$5$ vértices; isto é, existem grafos~$H$ com~$5$ vértices para os quais temos~$\omega(H)<3$ e~$\alpha(H)<3$. \datedue{19/3/2004} \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. \datedue{23/03/2004} \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} onde escrevemos~$\log n$ para~$\log_en$. (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~$\lim_{n\to\infty}P_n$ existe. Neste exercício, queremos estimar este limite.} \datedue{26/3/2004 (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 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~$E(G)\setminus E(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{30/3/2004} \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{2/4/2004} \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 blocos de~$G$. 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.) \textbf{[Adiado por 3 dias! \datedue{16/4/2004}]} \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{20/4/2004} \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. \begin{enumerate} \item Seja~$\cT(n)$ a família das árvores sobre o conjunto de vértices~$[n]=\{1,\dots,n\}$. Considere~$\cT(n)$ como um espaço de probabilidade, atribuindo para todo elemento de~$T\in\cT(n)$ a mesma probabilidade. Considere o vértice~$1$ como raiz de todos os~$T\in\cT(n)$; note que, fazendo isso, podemos definir a \textit{altura}~$h(T)$ de~$T$ em relação à raiz~$1$. Estime experimentalmente o valor esperado de~$h(T)$. \sugestao{Para gerar um~$T$, use a prova de Joyal para a fórmula de Cayley.} \textbf{[A entrega deste item fica adiada para o dia 30/4/2004]} \item Consideremos agora o grafo completo~$K_n$ sobre o conjunto de vértices~$[n]$. Podemos gerar uma árvore aleatória com raiz~$1$ sobre~$[n]$ executando uma busca aleatória em~$K_n$ a partir de~$1$ (considere a busca aleatória discutida em sala). Seja~$R_n$ uma tal árvore aleatória. Estime experimentalmente o valor esperado de~$h(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{enumerate} \datedue{23/4/2004} \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{27/4/2004} \item Seja~$G=(V,E)$ um grafo dirigido, onde~$V=\{v_1,\dots,v_n\}$, e seja~$A=(a_{ij})$ a matriz de adjacência para~$G$ com~$a_{ij}=1$ se~$(i,j)\in E$ e~$a_{ij}=0$ se~$(i,j)\notin E$. (Apenas para maior clareza, suponha que~$G$ não tem laços, de forma que~$a_{ii}=0$ para todo~$i$.) O que é a entrada~$ij$ da matriz~$A^2$? (Aqui~$A^2$ é o quadrado usual da matriz~$A$.) Em geral, o que é a entrada~$ij$ da $k$-ésima potência~$A^k$ de~$A$ ($k\geq0$)? \datedue{11/5/2004} \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{18/05/2004} \item \begin{enumerate} \item[(\textit{i})]Descreva o que ocorre quando executamos o algoritmo de Kosaraju em um DAG. \item[(\textit{ii})]Descreva o que ocorre quando executamos o algoritmo de Tarjan em um DAG. \end{enumerate}\datedue{21/5/2004} \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 é o 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{25/5/2004} \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 Suponha que os custos~$c(e)$ ($e\in E(G)$) das arestas de um grafo~$G$ são todos inteiros, com~$1\leq c(e)\leq n=|V(G)|$. O quão rápido podemos encontrar uma árvore geradora mínima de~$(G,c)$? \datedue{1/6/2004} \item Estude as implementações do algoritmo de Kruskal e do algoritmo de (Jarník--)Prim (com heaps binários) em \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Slides/2004.05.28/miles_span.pdf}{\texttt{miles\_span}}, do Stanford GraphBase. As estatísticas relatadas na Seção~71 daquele programa foram compiladas com uma máquina Sun Sparc 2 (bastante antiga!). Compile estatísticas para máquinas Intel (ou Sun) mais modernas. Faça uma pequena discussão com base nos dados que você obtiver. Se você quiser experimentar estas implementações em mais instâncias, vá em frente! \datedue{4/5/2004} \end{enumerate} \end{document} % Local Variables: % mode: latex % eval: (Portug-mode) % TeX-master: t % End: