Algorithme pour vérifier la transitivité de la relation?

Question

Je dois vérifier si la relation est transitive ou non?

Pourriez-vous suggérer un algorithme pour vérifier la transitivité des relations?

Je stocke la relation sous forme de matrice booléenne , il y a 1 si les éléments sont liés autrement 0 , comme dans les graphiques.

Merci.

Answer 1

Algorithme beaucoup plus simple que ma version Map / Set (supprimé), maintenant avec la matrice booléenne. C’est peut-être plus facile à comprendre, même si vous ne connaissez pas Java?

public class Trans
{

  final static int SIZE = 4;

  static boolean isTransitive(boolean[][] function)
  {
    for (int i = 0; i < SIZE; i++)
    {
      for (int j = 0; j < SIZE; j++)
      {
        if (function[i][j])
        {
          for (int k = 0; k < SIZE; k++)
          {
            if (function[j][k] && !function[i][k])
            {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  public static void main(String[] args)
  {
    boolean[][] function = new boolean[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++)
    {
      function[i] = new boolean[SIZE];
    }
    function[0][1] = true;
    function[1][2] = true;
    function[0][2] = true;
    function[0][3] = true;
    function[1][3] = true;   
    System.out.println(isTransitive(function));
  }
}

Answer 2

Malgré cela, ça sonne comme un devoir ...

Vous devez stocker vos relations pour pouvoir les rechercher rapidement par l’antécédent. Ensuite, vous pourrez découvrir des relations transitives de type A- & B & C, les ajouter au même stockage et continuer à rechercher A- & B- & C- & D, etc. etc. .

Answer 3

Le tri topologique peut être la bonne direction. La relation est transitive s'il n'y a pas de boucles dans sa représentation graphique dirigée. Si vous vous souciez de la vitesse, les algorithmes de graphes sont probablement la voie à suivre.