Транзитивность отношения на матрице

Пусть А – бинарное отношение в множестве Х. Определим общие свойства таких отношений, которые должны выполняться для всех пар (Xi, Xj) Î A.

Отношение А рефлексивно, если А É Е (Е – тождественное отношение), т. е. оно всегда выполняется между объектом и им самим: Х А Х.

Отношение А антирефлексивно, если А Е = , т. е. оно выполняется только для несовпадающих объектов: из Xi А Xj следует, что Xi ¹ Xj (строгое неравенство; «быть старше»).

Отношение А симметрично, если А = А-1, т. е. при выполнении соотношения Xi А Xj выполняется соотношение Xj А Xi («быть братом»).

Отношение А асимметрично, если А А-1 = Æ, т. е. из двух соотношений Xi А Xj и Xj А Xi одно неверно («быть отцом»). Если отношение А асимметрично, то оно и антирефлексивно.

Отношение А антисимметрично, если А А-1 Ì Е, т. е. оба соотношения Xi А Xj и Xj А Xi выполняются одновременно только тогда, когда Xi = Xj.

Отношение А транзитивно, если из соотношений Xi А Xj и Xj А Xk следует соотношение Xi А Xk («быть делителем»).

Для Рефлексивного Отношения все элементы матрицы на главной диагонали равны 1; для Антирефлексивного Отношения – это нули.

Симметричность отношения влечет за собой и симметричность матрицы; Асимметричность Отношения – несимметричность матрицы с нулевыми элементами на главной диагонали; Антисимметричность – только несимметричность матрицы.

В матрице Транзитивного отношения для каждой пары единичных элементов, один из которых расположен в I-м столбце и J-й строке, а другой – в J-м столбце и K—Й строке, обязательно существует единичный элемент, расположенный в I-м столбце и K—Й строке. Наличие единичных элементов на главной диагонали не нарушает транзитивности.

Содержание

Определение [ править ]

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется транзитивным, если для любых трёх элементов [math]a, b, c[/math] из выполнения отношений [math] aRb [/math] и [math] bRc [/math] следует выполнение отношения [math] aRc [/math] .

a, b, c in Xcolon

(aRc)[/math] .

Если это условие соблюдается не для всех троек [math]a, b, c[/math] , то такое отношение называется нетранзитивным. Например, не для всех троек [math] a, b, c in mathbb [/math] верно, что [math]

a, b, c in Xcolon

eg(aRc)[/math] .

Существует более "сильное" свойство — антитранзитивность. Под этим термином понимается, что для любых троек [math]a, b, c[/math] отсутствует транзитивность. Антитранзитивное отношение, например — отношение победить в турнирах «на вылет»: если [math]A[/math] победил игрока [math]B[/math] , а [math]B[/math] победил игрока [math]C[/math] , то [math]A[/math] не играл с [math]C[/math] , следовательно, не мог его победить.

a, b, c in Xcolon

eg(aRc)[/math] .

Свойства [ править ]

• Если отношение [math]R[/math] транзитивно, то обратное отношение [math]R^<-1>[/math] также транзитивно. Пусть [math]aR^<-1>b,

bR^<-1>c[/math] , но по определению обратного отношения [math]cRb,

bRa[/math] . Так как [math]R[/math] транзитивно, то [math]cRa[/math] и [math]aR^<-1>c[/math] , что и требовалось доказать.
Если отношения [math]R,

S[/math] транзитивны, то отношение [math]T

R cap S[/math] транзитивно. Пусть [math]aTb,

bSc[/math] . Из транзитивности [math]R,

S[/math] следует [math]aRc,

aSc[/math] , но из определения пересечения отношений получаем [math]aTc[/math] , что и требовалось доказать.

Примеры транзитивных отношений [ править ]

• Отношения частичного порядка:

• строгое неравенство [math]colon

a lt c);[/math]
нестрогое неравенство [math]colon

("leqslant ");[/math]
включение подмножества:

строгое подмножество [math]colon

("subset ");[/math]
нестрогое подмножество [math]colon

("subseteq ");[/math]

делимость:

[math](a mid b),

(a mid c);[/math]
[math](a ,vdots, b),

(a ,vdots, c);[/math]

Равенство [math]colon

(b = c) Rightarrow

(a Leftrightarrow b),

(b Leftrightarrow c)

(a Leftrightarrow c);[/math]
Импликация [math]colon

(a Rightarrow c);[/math]
Параллельность [math]colon

(a parallel c);[/math]

0 kbang [2012-12-08 08:52:00]

Я пишу программу на C, чтобы найти транзитивность. В 2D-массиве, если adj[0][1] = 1 и adj[1][2] = 1 , я хочу отметить adj[0][2] также как 1 . Это должно иметь место для любого транзитивного отношения в матрице.

Пожалуйста, помогите мне с некоторым кодом для этого.

c algorithm adjacency-matrix

3 ответа

1 Решение Richard [2012-12-08 15:42:00]

То, что вы хотите, является "транзитивным алгоритмом закрытия",

Алгоритм Флойда-Варшалла является хорошим примером одного из них, хотя есть много (многих) других, таких как Johnson Algorithm. Быстрый поиск по Google Scholar укажет вам на некоторые другие источники и более технические описания.

Код для алгоритма Флойда-Варшалла в его первоначальном виде (который находит кратчайшие пути между каждой подключенной точкой):

Изменение этого кода для сценария использования дает:

Обратите внимание, что порядок нижних индексов здесь. Наличие индексов в этом порядке соответствует критерию динамического программирования, обеспечивающему постепенное улучшение пути и всегда оптимальным.

Сложность времени — O (N ^ 3).

1 cube [2012-12-08 15:05:00]

Я считаю, что это сработает:

Как заметил Ричард, это эквивалентно вычислению пересечения графика.

Вы можете придумать adj_matrix[i][j] как о числе, говорящих, сколько путей длины 1 ведет от i до j . Тогда adj_matrix ** l (то есть матрица смежности в степени l ) сообщает вам, сколько путей длины по крайней мере l существует между любыми двумя двумя узлами.

Внутренние циклы в моем коде (петля с переменными i, j и k) являются в основном умножением reachable_matrix на reachable_matrix и сохраняют ее в tmp_matrix , только вместо добавления и умножения я использую логические или или и, потому что нас не интересует точное число, только в его значении истинности.

Внешняя петля удерживает квадрат reachable_matrix а мощность, к которой она поднята (длина пройденных путей) меньше N — 1 . Остановка в N — 1 достаточно, потому что если у вас есть путь к этой длине, это означает, что вы посещаете все узлы графика. Пути с большим количеством шагов обязательно должны содержать циклы. С другой стороны, я не выполняю двоичное возведение в степень, чтобы все было просто (я думаю, что это будет немного менее эффективно, но я не уверен в этом), и потому что попытка более длинных путей не наносит никакого вреда.

В целом этот алгоритм имеет сложность O (log (N) * N ** 3).