Non sono così entusiasta della matematica per questo, ma per quello che capisco ...
Un grafico g esiste con v vertici e spigoli. g = (V, E);
Il grafico spanning per questo è una copia aciclica di questo in cui sono presenti tutti i vertici e tutti i bordi sono un sottoinsieme del grafico con la condizione che ciascuna connessione sia distinta.
Apparentemente il MST dovrebbe avere nodi n-1. Come può essere provato?
Fonti:
Prova per induzione:
Ogni grafico aciclico può essere rappresentato come un albero, se tutti i nodi sono collegati.
Quindi pensiamo agli alberi. Hai un nodo radice. Diamo un'occhiata al caso più semplice, in cui l'albero ha solo un ramo, quindi è un semplice elenco collegato.
Se ci sono due nodi, c'è uno spigolo tra loro. Aggiungi un nodo alla fine dell'elenco collegato e ci sono tre nodi e due bordi e così via.
Ora, se prendiamo l'elenco collegato e aggiungiamo un altro nodo a uno dei nodi nel mezzo, abbiamo un vero albero. E ancora, stiamo aggiungendo un nodo insieme a un lato. Aggiungi un altro ed è lo stesso.
Indipendentemente dal numero di nodi che aggiungi o dove li aggiungi, finché rimane un albero aciclicamente connesso, ci saranno sempre bordi N-1 per N nodi.
Considera qualsiasi albero spanning minimo. Scegli un vertice come radice. Quindi ogni vertice ha un genitore, eccetto la radice.
Essenzialmente lo stesso che Mason e Mike hanno già detto, ma in parole diverse ...
Se non hai bordi, il massimo (connesso) dei vertici che puoi avere è uno. Chiama questo vertice alla radice.
Per aggiungere un nuovo vertice ad un albero, devi anche aggiungere un nuovo bordo (in modo che il nuovo vertice sia connesso). Quel limite può (e deve) connettersi a qualsiasi vertice preesistente. Il nuovo vertice è figlio del vertice preesistente e non limitiamo il numero di figli che un genitore può avere.
Se inizi con solo la radice (1 vertice e 0 bordi) ti ritroverai con 2 vertici e 1 bordo. Ripeti n volte per ottenere n + 1 vertici e n bordi.
Questa non è una prova completa di per sé, ma è impossibile aggiungere bordi o vertici in qualsiasi altro modo (eccetto che potresti aggiungere due bambini alla volta, a condizione che tu lo faccia in un modo che è equivalente a fare aggiungendo uno prima poi l'altro). Non è possibile aggiungere un bordo senza aggiungere un vertice perché così facendo si completerebbe un ciclo. Non puoi aggiungere un vertice senza aggiungere un bordo perché quel vertice non sarebbe connesso all'albero.
BTW - per i grafi non orientati, parole come "root", "parent" e "child" non significano molto, almeno non formalmente. Qualsiasi vertice in qualsiasi albero non orientato può essere considerato la radice, e quale vertice si chiama chiamare la radice decide per tutti i bordi il cui vertice è il genitore e che è il bambino. La mia immagine mentale di un albero tende ad includere l'identificazione di un particolare vertice come radice, ma è probabilmente un'immagine mentale fuorviante.
Leggi altre domande sui tag algorithms trees graph