T04
Completion requirements
Opened: Wednesday, 30 June 2021, 12:00 AM
Due: Tuesday, 6 July 2021, 11:59 PM
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.)