Quitar ciclos del gráfico

Question

Supongamos que tengo un gráfico no dirigido conectado$G=(V,E)$, quiero encontrar un subconjunto más pequeño de$E$eliminar para que se eliminen todos los ciclos.

Desde la página de Wikipedia sobre el rango del circuito , si entiendo bien, el siguiente enfoque funciona: encuentre un ciclo arbitrario en$G$, elimine cualquier borde del ciclo y repita. ¿Hay una manera simple de probar que esto funciona?

Answer 1

Definir el rango de circuito de un gráfico finito$G=(V,E)$como$r(G)=|E|-|V|+c$dónde$c$es el número de componentes conectados de$G$. Tenga en cuenta que un gráfico conexo$G$posee$r(G)\geq 0$y$r(G)=0$si y si$G$es un árbol Además, si las componentes conexas de$G$son$G_1,\dots,G_n$, después$r(G)=\sum_{i=1}^n r(G_i)$. Resulta que$r(G)=0$si y si$G$es un bosque, es decir$G$no tiene ciclos.

Ahora considere lo que sucede cuando elimina un borde de un gráfico$G$. Si ese borde es parte de un ciclo, disminuyes$|E|$por$1$pero no cambies$|V|$o$c$, asi que$r(G)$disminuye en$1$. Si el borde no es parte de un ciclo, aumenta adicionalmente$c$por$1$(ya que divides un componente en dos), entonces$r(G)$no cambia.

Por lo tanto, si desea reducir$r(G)$Abajo a$0$eliminando la menor cantidad de bordes posible, siempre debe eliminar los bordes que son parte de un ciclo, y tomará$r(G)$pasos.