componente fortemente connessa

Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra ogni coppia di nodi ad esso appartenenti. Le componenti fortemente connesse formano una partizione di G poiché un nodo non può trovarsi contemporaneamente in due componenti fortemente connesse, di conseguenza un grafo diretto è fortemente connesso se e solo se ha una sola componente fortemente connessa. Due vertici di G sono fortemente connessi se e solo se fanno parte dello stesso ciclo orientato.