Modo più semplice per controllare il set di bordo per la transitività
-
30-10-2019 - |
Domanda
Sto giocando con i tornei e attualmente ho il problema che devo verificare se un determinato sottoinsieme dei bordi di un torneo è transitivo (non deve essere aciclico). Sono consapevole che posso sempre prendere la chiusura transitiva del set di bordi e vedere se termina senza aggiungere un singolo bordo o meno, ma mi chiedevo se potesse esserci un modo più semplice di così.
Nota che sto cercando in particolare semplicità, non per efficienza; I tornei che voglio controllare hanno un massimo di $ 7 $ vertici, quindi la complessità non è davvero un problema. Preferirei modi semplici e facili da implementare. Il più semplice che potrei trovare finora è Floyd-Warshall, ma forse qualcuno sa qualcosa di più semplice.
Nessuna soluzione corretta