Come modificare il numero di componenti fortemente collegati di un grafico se si aggiunge un nuovo fronte

Question

Esercizio: 22.5-1 CLRS
Come può cambiare il numero di componenti fortemente connessi di un grafico se viene aggiunto un nuovo fronte ?

Somewhere la risposta data è Se viene aggiunto un nuovo spigolo, potrebbe accadere una delle due cose.
1) Se il nuovo fronte collega due vertici che appartengono a un componente fortemente connesso, il numero di componenti fortemente connessi rimarrà lo stesso.
2) Se, invece, il bordo collega due componenti fortemente connessi e il bordo si trova nella direzione inversa di un percorso esistente tra i due componenti, verrà creato un nuovo componente fortemente connesso, aumentando il numero di componenti.

Penso che il secondo punto non sia corretto. supponiamo di avere due fortemente collegato componente C e C '
a) Se nessun bordo o bordo C-> C' esiste tra loro e nuovo bordo collega come C-> C' poi non succederà nulla.
b) Se bordo C-> C' esistente tra loro e nuovo bordo collega come C '-> C allora C' saranno fuse C diminuire il numero di componente fortemente connessa da 1 come ogni vertice sarà raggiungibile l'uno dall'altro.

Per favore correggimi se sbaglio.

Answer 1

Hai esattamente ragione. La risposta che hai citato è errata nella sua descrizione: l'aggiunta di spigoli diminuirà sempre il numero di componenti fortemente connessi. Una volta aggiunti tutti i bordi possibili, rimane solo un singolo componente fortemente connesso, l'intero grafico.