Quindi per MST ci sono 2 possibili definizioni in un grafo non orientato. Tenere presente che in un grafico non orientato l'algoritmo MST ha sempre n - 1 spigoli e nessun ciclo. In un grafico non orientato, non importa quale definizione si utilizza, poiché entrambi sono corretti, tuttavia all'interno di un grafico diretto non è più il caso. Definizioni:
- Scegliendo un vertice di radice u in un grafico, l'MST è l'albero di costo più piccolo che collega ogni altro vertice da te.
- Dato un grafico, il sottografo a costo minimo che connette tutti i nodi è chiamato MST. (In un grafico non orientato deve essere un albero)
In un grafico diretto la prima definizione per un grafico diretto è l'arborescenza. Tuttavia l'arborescenza è diversa con ogni vertice scelto (questo non è il caso in un grafo non orientato), risultando in più possibili variazioni MST dirette. Nella sezione links ho un video che spiega la def. di un'arborescenza.
La seconda definizione richiede che il grafo diretto sia una grande componente strongmente connessa. Quindi ora è possibile passare da qualsiasi vertice u a qualsiasi altro vertice v, c'è solo 1 MST in un grafico diretto. Tuttavia ora non stiamo più parlando di alberi, quindi il MST deve includere cicli. Nella sezione dei collegamenti ho incluso un grafico come esempio per la seconda definizione. In questa immagine ci sono più di 1 possibili grafici minimi, uno per uno dei bordi rossi rimossi, per esempio.
La mia domanda è, qual è la seconda definizione chiamata in un grafico diretto? (Ha un nome speciale come l'arborescenza) e, in caso affermativo, non è la variante diretta di MST? Esiste un algoritmo per calcolare il grafico minimo all'interno di un componente strongmente connesso?
Definizione di arborescenza su Wikipedia
Video rapido che spiega cos'è un'arborescenza
Ho creato un esempio di grafico di cosa intendo con la seconda definizione:
