Removendo ciclos do gráfico

Question

Suponha que eu tenha um gráfico não direcionado conectado$G=(V,E)$, eu quero encontrar um menor subconjunto de$E$remover para que todos os ciclos sejam removidos.

Na página da Wikipedia sobre classificação do circuito , se bem entendi, a seguinte abordagem funciona: Encontre um ciclo arbitrário em$G$, remova qualquer borda do ciclo e repita. Existe uma maneira simples de provar que isso funciona?

Answer 1

Definir a classificação do circuito de um grafo finito$G=(V,E)$Como$r(G)=|E|-|V|+c$Onde$c$é o número de componentes conectados de$G$. Note que um grafo conectado$G$tem$r(G)\geq 0$e$r(G)=0$se$G$é uma árvore. Além disso, se os componentes conectados de$G$são$G_1,\dots,G_n$, então$r(G)=\sum_{i=1}^n r(G_i)$. Segue que$r(G)=0$se$G$é uma floresta, ou seja$G$não tem ciclos.

Agora considere o que acontece quando você remove uma aresta de um gráfico$G$. Se essa aresta fizer parte de um ciclo, você diminui$|E|$por$1$mas não mude$|V|$ou$c$, assim$r(G)$diminui em$1$. Se a borda não fizer parte de um ciclo, você aumenta adicionalmente$c$por$1$(já que você divide um componente em dois), então$r(G)$não muda.

Então, se você quiser diminuir$r(G)$até$0$removendo o mínimo possível de arestas, você deve sempre remover arestas que fazem parte de um ciclo, e isso levará$r(G)$degraus.