Транспонировать график
В математическом и алгоритмическом исследовании теории графов обратное происходит : [1] транспонировать [2] или наоборот [3] ориентированного графа G — это другой ориентированный граф на том же наборе вершин , у которого все ребра перевернуты по сравнению с ориентацией соответствующих ребер в G . То есть, если G содержит ребро ( u , v ) , то обратное/транспонированное/обратное преобразование G содержит ребро ( v , u ) и наоборот.
Обозначения [ править ]
Название «конверс» возникает потому, что перестановка стрелок соответствует обращению импликации в логике. Название «транспонирование» связано с тем, что матрица смежности транспонированного ориентированного графа является транспонированием матрицы смежности исходного ориентированного графа.
Общего согласия относительно предпочтительной терминологии не существует.
Обратное обозначено символически как G' , G Т , Г Р или другие обозначения, в зависимости от того, какая терминология используется и какая книга или статья является источником обозначений.
Приложения [ править ]
Хотя с математической точки зрения разница между графом и его транспонированием незначительна, в информатике разница может быть больше , в зависимости от того, как представлен данный граф . Например, для веб-графа легко определить исходящие ссылки вершины, но сложно определить входящие ссылки, тогда как при развороте этого графа верно обратное. Поэтому в графовых алгоритмах иногда может оказаться полезным построить явное представление обращения графа, чтобы придать графу форму, более подходящую для выполняемых над ним операций. Примером этого является алгоритм Косараджу для сильно связанных компонентов , который дважды применяет поиск в глубину : один раз к заданному графу и второй раз к его обращению.
Связанные понятия [ править ]
Кососимметричный граф — это граф, который изоморфен своему собственному транспонированному графу посредством особого вида изоморфизма, который объединяет все вершины в пары.
Обратное отношение бинарного отношения — это отношение, которое меняет порядок каждой пары связанных объектов. Если отношение интерпретируется как ориентированный граф, это то же самое, что транспонирование графа. В частности, двойственный порядок частичного порядка можно интерпретировать таким образом как транспозицию транзитивно-замкнутого ориентированного ациклического графа .
См. также [ править ]
- Обратное отношение - изменение порядка элементов бинарного отношения.
Ссылки [ править ]
- ^ Харари, Фрэнк; Норман, Роберт З.; Картрайт, Дорвин (1965), Структурные модели: введение в теорию ориентированных графов , Нью-Йорк: Wiley
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. Введение в алгоритмы . MIT Press и McGraw-Hill. , бывший. 22.1–3, с. 530.
- ^ Эссам, Джон В.; Фишер, Майкл Э. (1970), «Некоторые основные определения в теории графов», Reviews of Modern Physics , 42 (2): 275, Bibcode : 1970RvMP...42..271E , doi : 10.1103/RevModPhys.42.271 , запись 2.24