[Grafi] Massimo sottografo completo
Ciao a tutti ragazzi, vi espongo questo problema di cui non riesco a venire a capo:
Dato un grafo G rappresentato come [size=150]matrice di adiacenza[/size], costruire il massimo sottografo completo di G in tempo $ O(|V|^3) $.
Per grafo completo si intende un grafo ove i vertici siano componenti fortemente connesse, cioè ogni vertice è adiacente a tutti gli altri.
Voi avreste qualche idea a livello logico?
Io posso anche identificare quali sono tutte le componenti fortemente connesse nel grafo G ($ O(|V|^2) $), ma poi come controllo se sono contigue?
Dato un grafo G rappresentato come [size=150]matrice di adiacenza[/size], costruire il massimo sottografo completo di G in tempo $ O(|V|^3) $.
Per grafo completo si intende un grafo ove i vertici siano componenti fortemente connesse, cioè ogni vertice è adiacente a tutti gli altri.
Voi avreste qualche idea a livello logico?
Io posso anche identificare quali sono tutte le componenti fortemente connesse nel grafo G ($ O(|V|^2) $), ma poi come controllo se sono contigue?
Risposte
Le definizioni di grafo completo e di componente fortemente connessa non sono corrette.
Parliamo di grafi orientati o non ?
Parliamo di grafi orientati o non ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo