T09 Desmontagem de um grafo
Dado um grafo \(G\) e um vértice $x$ de $G$, o grafo $G-x$ é o grafo com conjunto de vértices $V(G)\setminus\{x\}$ e conjunto de arestas $E(G)\setminus\partial(x)$, onde $\partial(x)=\{e\in E(G)\colon x\in e\}$, isto é, $\partial(x)$ é o conjunto de arestas de $G$ que incidem em $x$.
Descreva um algoritmo para resolver o seguinte problema:
Problema. Dado um grafo conexo \(G\), encontrar uma ordenação $x_0,x_1,\dots,x_{n-1}$ de de seus vértices de forma que os grafos $G-x_0$, $G-x_0-x_1$, $G-x_0-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, $n$ é o número de vértices em $G$.
Seu algoritmo deve encontrar a ordenação $x_0,x_1,\dots,x_{n-1}$ em tempo $O(n+m)$, onde $m$ é o número de arestas em $G$.
Argumente que seu algoritmo está correto e que ele tem a eficiência pedida.
Exemplo. Considere o grafo definido pela entrada
6
8
0 5
2 4
2 3
1 2
0 1
3 4
3 5
0 2
Uma possível ordem de remoção seria
1 5 4 3 2 0