Алгоритм проверки транзитивности отношения?

Question

Мне нужно проверить, является ли отношение транзитивным или нет?

Не могли бы вы предложить некоторый алгоритм для проверки транзитивности отношений?

Я храню отношение как булевой матрицы есть если элементы связаны другие мудрые как в виде графиков.

Спасибо.

Answer 1

Гораздо более простой алгоритм в качестве моей карты/установки версии (удален), теперь с булевой матрицей. Может быть, это легче понять, даже если вы не знаете 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

Несмотря на это полностью звучит как домашнее задание ...

Вы должны были бы сохранить ваши отношения, так что вы можете смотреть их на антецеденте очень быстро. Затем вы можете обнаружить переходные отношения типа A-> B-> C, добавить их в одно хранилище и продолжить поиск A-> B-> C-> D и т. Д. И т.д. ...

Answer 3

Топологическая сортировка может быть правильной. Эта связь транзитивна, если в ее ориентированном графическом представлении нет петель. Если вам небезразлична скорость, алгоритмы графа, вероятно, являются способом выхода.