Exercícios de algoritmos
686 palavras
3 páginas
SEGUNDA LISTA DE EXERCÍCIOS - ALGORITMOS E GRAFOS 1) Seja G um grafo. Um emparelhamento M em G é um subconjunto de arestas de G com a seguinte propriedade: quaisquer duas arestas distintas em M não possuem vértice em comum. Um emparelhamento M em G é dito máximo quando não existe emparelhamento M' em G tal que | M' | > | M |. Dado um grafo bipartido G, mostre como obter um emparelhamento máximo em G convertendo este problema num problema de fluxo máximo. 2) Um digrafo admite ordenação topológica se e somente se for acíclico. Falso ou verdadeiro?
3) Seja D(V,E) um digrafo que contém exatamente um ciclo C. Seja V' V o subconjunto dos vértices de D alcançáveis de algum vértice de C. Se D for fornecido como entrada para o algoritmo de ordenação topológica visto em aula, qual será a saída correspondente?
4) Formule o problema de fluxo máximo em uma rede como um problema de programação linear.
5) Execute o algoritmo de Floyd-Warshall sobre o digrafo cuja matriz inicial W é dada a seguir. Exiba todas as matrizes intermediárias.
0
3
8
0
1
4
0
2
5
0
6) Ainda com relação ao exercício anterior, explique como construir os caminhos mais curtos através das matrizes predecessoras. Exiba as matrizes predecessoras em cada iteração, e no final liste os caminhos mais curtos entre cada par de vértices.
7) O algoritmo de Floyd-Warshall, tal como definido, ocupa espaço (n3). Explique como modificá-lo de modo que ele ocupe espaço (n2).
8) Decida a planaridade do grafo de Petersen através do algoritmo visto em sala.
9) Mostre que se G é um grafo com pelo menos 11 vértices, então ou G ou o seu complemento é um grafo não-planar. É possível um exemplo em que ambos não são planares?
10) Encontre três grafos planares tais que sua união é o grafo completo com 10 vértices.
11) Dado um digrafo com pesos positivos nas arestas, considere o seguinte algoritmo guloso para encontrar uma tour mínima: iniciando no vértice