Supponiamo di avere un grafico $ G $. Scegliamo un lato da esso (qualsiasi bordo). Ci sarà sempre un albero di copertura tale che contiene proprio quel bordo?
Penso che la risposta sia sì, perché qualunque cosa facciamo, possiamo sempre creare un tale spanning tree in modo che il bordo che abbiamo scelto sia incluso. Ovviamente, una dimostrazione più formale sarebbe necessario?
Commenti
- Tu ' non hai scritto nemmeno una dimostrazione informale: essenzialmente, tu ' hai detto " Penso che la risposta sia sì, perché la risposta è sì. "
Risposta
Nota che il grafico iniziale $ G $ deve essere connesso o non ha alcuno spanning tree (sebbene lo stesso argomento applicato a ciascun componente mostrerebbe che ogni grafo ha una foresta spanning contenente qualsiasi bordo scelto).
Sia $ G = (V, E) $ sia un grafo connesso, sia $ T $ sia qualsiasi sottostruttura spanning e $ e $ qualsiasi edgein $ E $. Affermiamo che esiste uno spanning tree che include $ e $. Se $ e \ in T $, abbiamo finito. Altrimenti, $ T + e $ contiene un ciclo. Quel ciclo contiene necessariamente almeno un bordo $ e “\ neq e $ (in realtà, ne contiene almeno due). $ T + ee” $ è uno spanning tree che contiene $ e $.
Dovresti provare a te stesso che $ T + ee “$ è davvero uno spanning tree.
Answer
Laggiunta di un bordo a un albero causa un ciclo unico. Puoi rimuovere qualsiasi bordo da questo ciclo (diverso da quello che hai aggiunto) per recuperare un albero. Questo nuovo albero contiene il bordo che è stato aggiunto.
Commenti
- Questo ' è esattamente quello che ho detto!
- Sì, ma Lho detto con meno parole. 🙂
- Perché le mie sette frasi davvero devono essere riassunte in tre. Abbiamo cinque migliaia di domande senza risposta sul sito: sarebbe molto meglio rispondere ad alcune di queste piuttosto che pubblicare risposte duplicate a domande che ' non ne hanno bisogno.
- Quindi leggi la risposta esistente s prima di postarne uno tuo.
- Niente è veramente richiesto – come potremmo comunque applicarlo? Ma generalmente ci si aspetta che le risposte contribuiscano a qualcosa di nuovo, e come puoi sapere che ' lo stai facendo se ' non lo sai cosa è già stato detto '? Avere più risposte che dicono tutte la stessa cosa ingombra la pagina, anche se ovviamente ' non è un grosso problema con solo due. Pubblicare una risposta breve, in stile riepilogo può sicuramente essere utile quando le risposte esistenti sono lunghe; Semplicemente non ' penso che aggiunga qualcosa in questo caso particolare.