Suppression de cycles du graphique

Question

Supposons que j'ai un graphe non orienté connecté$G=(V,E)$, je veux trouver un plus petit sous-ensemble de$E$supprimer afin que tous les cycles soient supprimés.

À partir de la page Wikipedia sur circuit rank , si je comprends bien, l'approche suivante fonctionne : trouver un cycle arbitraire dans$G$, supprimez tout bord du cycle et répétez. Existe-t-il un moyen simple de prouver que cela fonctionne?

Answer 1

Définir le rang du circuit d'un graphe fini$G=(V,E)$comme$r(G)=|E|-|V|+c$où$c$est le nombre de composantes connexes de$G$. Notez qu'un graphe connexe$G$a$r(G)\geq 0$et$r(G)=0$ssi$G$est un arbre. De plus, si les composants connexes de$G$sommes$G_1,\dots,G_n$, alors$r(G)=\sum_{i=1}^n r(G_i)$. Il s'ensuit que$r(G)=0$ssi$G$est une forêt, c'est-à-dire$G$n'a pas de cycles.

Considérez maintenant ce qui se passe lorsque vous supprimez une arête d'un graphique$G$. Si ce front fait partie d'un cycle, vous diminuez$|E|$par$1$mais ne change pas$|V|$ou$c$, alors$r(G)$diminue de$1$. Si le front ne fait pas partie d'un cycle, vous augmentez en plus$c$par$1$(puisque vous divisez un composant en deux), donc$r(G)$ne change pas.

Donc, si vous voulez diminuer$r(G)$jusqu'à$0$en supprimant le moins d'arêtes possible, vous devez toujours supprimer les arêtes qui font partie d'un cycle, et il faudra$r(G)$pas.