Detransitivization? Поиск транзитивной базы?
Меня интересует операция, которую я опишу ниже, но я не знаю, изучалась ли она уже (возможно, под другим названием) и была ли она реализована.
Идея состоит в следующем: для любого ориентированного графа мы можем вычислить транзитивное замыкание, сказав, что "когда есть направленный путь между вершинами v и v ', я добавляю направленное ребро vv'". Назовем TC(G) транзитивным замыканием группы G.
Я хотел бы найти минимальный граф G' такой, что TC(G)=TC(G'). Минимальным в смысле не должно быть ребра в G', которое может быть получено транзитивностью от двух других ребер G'.
Поскольку я не знаю имя, данное этой операции, я называю это детранзитивизацией G, можно также назвать ее поиском транзитивной базы G (в том смысле, что из базы G' я могу получить TC(G) и также любой G такой, что TC(G) = TC (G'), применяя некоторые транзитивные отношения, но не обязательно все они).
Может кто-нибудь сказать мне, изучалось ли это в теории графов и под каким именем, чтобы я мог найти литературу, а также была ли она реализована?