Dimostrazione albero ricoprente
Dato un grafo G e un suo albero ricoprente qualunque. Come dimostro che l'albero ricoprente è minimo per induzione? (per minimo si intende che rimuovendo un arco qualunque l'albero non è più collegato).
Grazie. All'ultimo esame mi è capitata questa domanda ma non saprei la soluzione, ne ricordo di averla vista a lezione (probabilmente l'ha spiegato in una delle 2 uniche lezioni in cui non c'ero).
Grazie. All'ultimo esame mi è capitata questa domanda ma non saprei la soluzione, ne ricordo di averla vista a lezione (probabilmente l'ha spiegato in una delle 2 uniche lezioni in cui non c'ero).
Risposte
Che succede se togli un arco ad un albero?
non è più collegato? O_O
Sì, è cosi. Siccome un albero non ha cicli, esiste un solo percorso che unisce due dei suoi vertici. Se eliminiamo quindi un arco da questo albero, l'albero non è più connesso (e di fatto non è più un albero..).
non vedo dove sta l'induzione però. Intuitivamente è così e più o meno avevo risposto lo stesso. Non avendolo dimostrato per induzione però non contava.
Sinceramente non vedo il senso dell'induzione in questo caso. Si può dimostrare questo fatto abbastanza direttamente senza usarla. Immagino dipenda da quale definizione venga usata per albero e albero ricoprente. Se viene usata la definizione ricorsiva allora immagino possa essere conveniente usarla. Per esempio:
Caso base: L'albero con un solo elemento è certamente minimo. Non so se in realtà vuole usare come caso base quello di un albero di altezza uno. In questo caso gli archi sono solo quelli che vanno dalla radice ad uno dei suoi figli ed eliminando questo arco il figlio diventa scollegato dal resto dell'albero.
Passo induttivo: Tutti gli albero di altezza h sono minimi. Dimostriamo che anche quelli di altezza h+1 lo sono. Tutti i sottoalberi propri di questo albero avranno altezza minore o uguale ad h, per cui sono minimi. Se eliminiamo un arco in questi, l'albero diventa sconnesso perché non ci sono collegamenti tra i diversi sottoalberi e la radice sarà connessa a solo uno delle due componenti connesse del sottoalbero. Se eliminiamo invece un arco che parte dalla radice, avremo nuovamente due componenti connesse perché il sottoalbero non sarà più connesso al resto dell'albero (i.e. l'unico arco da un sottoalbero all'albero è quello che lo collega al suo nodo genitore).
Ma sinceramente preferisco l'altra.
Caso base: L'albero con un solo elemento è certamente minimo. Non so se in realtà vuole usare come caso base quello di un albero di altezza uno. In questo caso gli archi sono solo quelli che vanno dalla radice ad uno dei suoi figli ed eliminando questo arco il figlio diventa scollegato dal resto dell'albero.
Passo induttivo: Tutti gli albero di altezza h sono minimi. Dimostriamo che anche quelli di altezza h+1 lo sono. Tutti i sottoalberi propri di questo albero avranno altezza minore o uguale ad h, per cui sono minimi. Se eliminiamo un arco in questi, l'albero diventa sconnesso perché non ci sono collegamenti tra i diversi sottoalberi e la radice sarà connessa a solo uno delle due componenti connesse del sottoalbero. Se eliminiamo invece un arco che parte dalla radice, avremo nuovamente due componenti connesse perché il sottoalbero non sarà più connesso al resto dell'albero (i.e. l'unico arco da un sottoalbero all'albero è quello che lo collega al suo nodo genitore).
Ma sinceramente preferisco l'altra.
ok grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo