Транспонированный граф

Граф и его транспонированный граф

Для ориентированного графа G термины converse (обратный)[1], transpose (транспонированный)[2] или reverse (противоположный)[3] используются для обозначения другого ориентированного графа с тем же набором вершин и с теми же дугами, но ориентация дуг этого графа противоположна ориентации дуг графа G. То есть, если граф G содержит дугу (u,v), то обратный/транспонированный/противоположный граф графу G содержит дугу (v,u), и наоборот.

Обозначения

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

Не существует устоявшегося мнения, какой из терминов предпочтительнее.

Обратный граф может обозначаться как G', GT, GR или другим способом, в зависимости от принятой в статье или книге терминологии.

Приложения

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

Связанные концепции

Кососимметрический граф — это граф, изоморфный своему собственному транспонированному графу через изоморфизм специального вида, который разбивает на пары все вершины.

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

Примечания

  1. ↑ Harary, Norman, Cartwright, 1965.
  2. ↑ Introduction to Algorithms, ex. 22.1–3, p. 530. Есть русский перевод книги «Алгоритмы: построение и анализ», но на стр. 461 соответствующее упражнение 23.1-3 упоминания о транспонированых графах не содержит
  3. ↑ Essam, Fisher, 1970, с. 275, entry 2.24.

Литература

  • Frank Harary, Robert Z. Norman, Dorwin Cartwright. Structural Models: An Introduction to the Theory of Directed Graphs. — New York: Wiley, 1965.
  • John W. Essam, Michael E. Fisher. Some basic definitions in graph theory // Reviews of Modern Physics. — 1970. — Т. 42, вып. 2. — doi:10.1103/RevModPhys.42.271. — Bibcode: 1970RvMP...42..271E.