В математическом и алгоритмическом исследовании теории графов обратный , [1] транспонированный [2] или обратный [3] ориентированный граф G представляет собой другой ориентированный граф на том же наборе вершин со всеми ребрами, перевернутыми по сравнению с ориентацией . соответствующих ребер в G . То есть, если G содержит ребро ( u , v ) , то обратное/транспонированное/обратное преобразование G содержит ребро ( v , u ) и наоборот.
Название « конверс» возникает потому, что перестановка стрелок соответствует обращению импликации в логике. Название «транспонирование» связано с тем, что матрица смежности транспонированного ориентированного графа является транспонированием матрицы смежности исходного ориентированного графа.
Общего согласия относительно предпочтительной терминологии не существует.
Обратное обозначено символически как G' , GT , GR или другими обозначениями, в зависимости от того , какая терминология используется и какая книга или статья является источником обозначений.
Хотя с математической точки зрения разница между графом и его транспонированием незначительна, в информатике разница может быть больше , в зависимости от того, как представлен данный граф . Например, для веб-графа легко определить исходящие ссылки вершины, но сложно определить входящие ссылки, тогда как при развороте этого графа верно обратное. Поэтому в графовых алгоритмах иногда может оказаться полезным построить явное представление обращения графа, чтобы придать графу форму, более подходящую для выполняемых над ним операций. Примером этого является алгоритм Косараджу для сильно связанных компонентов , который дважды применяет поиск в глубину : один раз к заданному графу и второй раз к его обращению.
Кососимметричный граф — это граф, который изоморфен своему собственному транспонированному графу посредством особого вида изоморфизма, который объединяет все вершины в пары.
Обратное отношение бинарного отношения — это отношение, которое меняет порядок каждой пары связанных объектов. Если отношение интерпретируется как ориентированный граф, это то же самое, что транспонирование графа. В частности, двойственный порядок частичного порядка можно интерпретировать таким образом как транспозицию транзитивно-замкнутого ориентированного ациклического графа .