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