WikiDer > Транспонировать график

Transpose graph
График и его транспонирование

В математическом и алгоритмическом исследовании теория графов, то разговаривать,[1] транспонировать[2] или обеспечить регресс[3] из ориентированный граф г - другой ориентированный граф на том же множестве вершин со всеми перевернутыми ребрами по сравнению с ориентацией соответствующих ребер в г. То есть, если г содержит край (u, v) затем обратное / транспонирование / обратное г содержит край (v, u) и наоборот.

Обозначение

Название разговаривать возникает потому, что переворот стрелок соответствует взятию разговаривать импликации в логике. Название транспонировать потому что матрица смежности транспонированного ориентированного графа транспонировать матрицы смежности исходного ориентированного графа.

Нет общего согласия по предпочтительной терминологии.

Обратное обозначено символически как Г', гТ, гр, или другие обозначения, в зависимости от того, какая терминология используется и какая книга или статья является источником обозначений.

Приложения

Хотя математически между графиком и его транспонированием небольшая разница, разница может быть больше в Информатика, в зависимости от того, как представлен данный граф. Например, для веб-график, легко определить исходящие связи вершины, но сложно определить входящие связи, тогда как при обращении этого графа верно обратное. В графовые алгоритмыпоэтому иногда может быть полезно построить разворот графа, чтобы придать графу форму, которая больше подходит для операций, выполняемых над ним. Примером этого является Алгоритм Косараджу за компоненты сильной связности, который применяется поиск в глубину дважды, один раз к данному графику и второй раз к его развороту.

Связанные понятия

А кососимметричный граф это граф, который изоморфный в свой собственный транспонированный граф с помощью особого вида изоморфизма, который объединяет все вершины в пары.

В обратное отношение из бинарное отношение - это отношение, которое меняет порядок каждой пары связанных объектов. Если отношение интерпретируется как ориентированный граф, это то же самое, что транспонирование графа. В частности, двойной порядок из частичный заказ можно интерпретировать таким образом как перестановку транзитивно-замкнутый ориентированный ациклический граф.

использованная литература

  1. ^ Харари, Фрэнк; Норман, Роберт З .; Картрайт, Дорвин (1965), Структурные модели: введение в теорию ориентированных графов, Нью-Йорк: Wiley
  2. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. Введение в алгоритмы. MIT Press и McGraw-Hill., пр. 22.1–3, с. 530.
  3. ^ Эссам, Джон В .; Фишер, Майкл Э. (1970), «Некоторые основные определения в теории графов», Обзоры современной физики, 42 (2): 275, Bibcode:1970РвМП ... 42..271Э, Дои:10.1103 / RevModPhys.42.271, запись 2.24