Rimozione di cicli dal grafico

Question

Supponiamo di avere un grafo non orientato connesso$G=(V,E)$, voglio trovare un sottoinsieme più piccolo di$E$rimuovere in modo che tutti i cicli vengano rimossi.

Dalla pagina di Wikipedia sul rango del circuito , se ho capito bene, il seguente approccio funziona: trova un ciclo arbitrario in$G$, rimuovere qualsiasi bordo del ciclo e ripetere. C'è un modo semplice per dimostrare che funziona?

Answer 1

Definire il rango del circuito di un grafo finito$G=(V,E)$come$r(G)=|E|-|V|+c$dove$c$è il numero di componenti connessi di$G$. Si noti che un grafico connesso$G$ha$r(G)\geq 0$e$r(G)=0$se$G$è un albero. Inoltre, se i componenti collegati di$G$sono$G_1,\dots,G_n$, poi$r(G)=\sum_{i=1}^n r(G_i)$. Ne consegue che$r(G)=0$se$G$è una foresta, ad es$G$non ha cicli

Ora considera cosa succede quando rimuovi un arco da un grafico$G$. Se quel bordo fa parte di un ciclo, diminuisci$|E|$di$1$ma non cambiare$|V|$o$c$, Così$r(G)$diminuisce di$1$. Se il bordo non fa parte di un ciclo, aumenti ulteriormente$c$di$1$(poiché hai diviso un componente in due), così$r(G)$non cambia.

Quindi, se vuoi diminuire$r(G)$giù verso$0$rimuovendo il minor numero possibile di bordi, dovresti sempre rimuovere i bordi che fanno parte di un ciclo e ci vorrà$r(G)$passi.