Lista de Exercicios - Teoria dos Grafos - Digrafos UFABC

MCTA02817 Teoria dos Grafos Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Lista 4 Conceitos básicos em digrafos 1 Vimos o seguinte resultado para grafos Se G é um grafo com δG 2 então G contém um caminho de comprimento pelo menos δG e um ciclo de comprimento pelo menos δG 1 Se for possível reescrevao e proveo adequadamente para digrafos Se não for apresente um contraexemplo 2 Vimos o seguinte resultado para grafos Todo grafo que não contém ciclos tem pelo menos dois vértices de grau 1 Se for possível reescrevao e proveo adequadamente para digrafos Se não for apresente um contraexemplo 3 Prove ou exiba um contraexemplo todo digrafo com ao menos dois vértices possui ao menos dois vértices com o mesmo grau de entrada ou ao menos dois vértices com o mesmo grau de saída 4 Quantas orientações um grafo simples possui 5 Vimos em sala que Se D é um um digrafo então D admite uma ordenação topo lógica se e somente se D é acíclico É possível extrair da prova desse teorema um algoritmo que devolve uma ordenação topológica para um dado digrafo de entrada Apresente um pseudocódigo para esse algoritmo 6 Prove que todo DAG tem um sorvedouroralo 7 Qual a relação entre as componentes fortemente conexas de um digrafo D e seu reverso D 8 Seja D um digrafo qualquer e seja x y V D tal que xy ED e yx ED Qual a relação entre as componentes fortemente conexas de D e D xy 9 Descreva um algoritmo que determine se um dado digrafo D é um DAG O seu algoritmo deve executar em tempo OV E 10 Prove que se D é um digrafo então vV G dv ED por indução no número de vértices 11 O que acontece quando nosso algoritmo de ordenação topológica executar a DFS e devolver os vértices em ordem decrescente de posordem é executado em um grafo dirigido que possui um ciclo 12 Prove que todo torneio possui um caminho gerador 1 13 Seja D um digrafo Seja CD o digrafo das componentes fortemente conexas de D também chamado digrafo condensação definido de forma que para cada componente fortemente conexa Ci de D há um vértice vi em V CD e existe um arco vivj ECD se e somente se existir um arco ab ED tal que a V Ci e b Cj a Desenhe CD1 e CD2 para os digrafos D1 e D2 das Figuras 1 e 2 b Prove que CD para qualquer D é um DAG 14 Prove que um digrafo D é um DAG se e somente se não são encontradas arestas de retorno em nenhuma chamada da DFS sobre D 15 O algoritmo de Kosajaru continuaria funcionando se uma ou ambas as passadas usassem busca em largura Justifique 16 Execute o algoritmo de ordenação topológica para o digrafo D3 17 Execute o algoritmo de Kosajaru sobre o digrafo D1 18 Execute o algoritmo de Tarjan sobre o digrafo D1 0 1 2 4 5 6 7 8 9 10 11 12 13 14 Figura 1 Digrafo D1 0 1 2 3 4 5 6 Figura 2 Digrafo D2 0 1 2 4 5 6 7 8 9 Figura 3 Digrafo D3 2