Algoritmi di infittimento di un albero

[phate867]

Allora, non studio nello specifico la teoria dei grafi e quindi non sono un grande esperto avendo dato un solo esame di base in materia, ma mi ritrovo con la necessità di applicarla per un problema di ingegneria, in particolare reti.

Chiedo quindi a voi ponendovi il problema nella maniera più astratta e matematica possibile.

Ho un insieme di nodi e inizio col crearmi un albero, in questo modo il grafo risultante è connesso con un numero minimo di archi. Ora, vorrei infittirlo con altri archi, in modo che se un nodo arbitrario dovesse cadere il grafico risulti ancora connesso.
Quindi il mio problema è "trovare il numero minimo di archi n (non solo il numero ma anche quali sono), tale che tolto un numero arbitrario di nodi, al più k, il grafo risulti ancora connesso".

Esiste un algoritmo della teoria dei grafi, applicabile nella realtà (quindi con assunzioni e tempi di computazione accettabili) che risolva questo problema?

edit.
potrei, volendo (ma immagino si debba arrivare a questo), fornire una certa % affinchè ciò avvenga mediante ad esempio pesi sui nodi: nodi con pesi più alti è meno probabile che cadano rispetto ad altri.
edit2.
dimenticavo, il grafo non è orientato.

[Pappappero1]

In generale credo dipenda pesantemente da come e' fatto l'albero.

I due casi piu' facili dovrebbero essere i seguenti:
un minimo di $1$ arco aggiuntivo per l'albero unario dato semplicemente da una catena di nodi e archi. In quel caso basta aggiungere un arco che collega il primo nodo all'ultimo;
un massimo di $n-2$ archi, per l'albero in cui hai una radice $n-1$-aria. In quel se cade la radice hai $n-1$ componenti connesse, che quindi devi collegare insieme con archi aggiuntivi, e per farlo ti servono almeno $n-2$ archi aggiuntivi.

Se cadono $k$ nodi diventa piu' complicato, ma credo che il caso peggiore necessiti di qualcosa dell'ordine di $kn$ nodi aggiuntivi (almeno quando $k$ e' molti piu' piccolo di $n$).

Non so se esiste un algoritmo che, dato un albero, ti trova quali sono gli archi da aggiungere. Ho pero' l'impressione che, almeno per $k=1$, qualcosa di facile ci dovrebbe essere (dato un albero, caratterizzare il piu' piccolo grafo tale che il tuo albero e' un sottografo e per cui, ogni volta che cade un nodo, il grafo e' ancora connesso).