T04
Condições de conclusão
Aberto: quarta-feira, 30 jun. 2021, 00:00
Vencimento: terça-feira, 6 jul. 2021, 23:59
Descreva um algoritmo para resolver o seguinte problema:
Problema. Dado um grafo conexo \(G\), encontrar uma ordenação de seus vértices $x_1,x_2,\dots,x_{V-1}$ de forma que os grafos $G-x_1$, $G-x_1-x_2$, etc sejam todos conexos. Isto é, queremos uma ordem de remoção dos vértices de $G$ de forma que, após cada uma das remoções, temos ainda um grafo conexo. Aqui, $V$ é o número de vértices em $G$.
Seu algoritmo deve encontrar a ordem $x_1,x_2,\dots,x_{V-1}$ em tempo $O(V+E)$, onde, como de usual, $E$ é o número de arestas em $G$.
Argumente que seu algoritmo está correto e que ele tem a eficiência pedida.
(Veja o Web Exercise 4.1.24 de S&W.)