Удалить переходные ребра в графе

Question

У меня есть график,

Так как я могу перейти от 1 до 2 до 3 (то есть от 1 до 3 через 2), край от 1 до 3 не является необходимым.

Поэтому я хочу, чтобы удалить ребро непосредственно между 1 и 3.

Как бы это сделать? Я предполагаю, что я должен делать поиск в ширину, чтобы решить, куда я могу пойти с 1

Так что, если у меня есть все мои узлы и край

nodes = [1, 2, 3] 
edges = [ 
    {source: 1, target: 2}, 
    {source: 1, target: 3}, 
    {source: 2, target: 3} 
] 

Я хочу удалить

{source: 1, target: 3}, 

так это необязательно из-за транзитивности, но как я могу определить, следует ли удалять

{source: 1, target: 3}, 

вместо

{source: 2, target: 3} 

?

Answer 1

Вы ищете транзитивное уменьшение графика, this article should help.