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