Для орієнтованого графа G терміни транспонований (Introduction to Algorithms, ex. 22.1–3, p. 530.), обернений ( або ) використовують для позначення іншого орієнтованого графа з тим самим набором вершин і з тими ж дугами, але протилежної орієнтації. Тобто, якщо граф G містить дугу (u, v), то транспонований/обернений граф графу G містить дугу (v, u), і навпаки.
Позначення Назва обернений виникає тому, що обернення стрілок дуг відповідає оберненню логічного висновку в логіці. Термін транспонований походить із алгебри, оскільки матриця суміжності орієнтованого транспонованого графа є транспонованою матрицею матриці суміжності початкового графа.
Не існує усталеної думки, який з термінів кращий.
Транспонований граф може позначатися як G''', GT, G''R або інакше, залежно від прийнятої в статті або книзі термінології.
Застосування Хоча математично різниця між графом та його транспонованим графом не велика, в інформатиці різниця може виявитися значною, залежно від способу подання графа. Наприклад, для вебграфа легко визначити вихідні з'єднання вершин, але важко визначити вхідні з'єднання, тоді як для транспонованого графа істинне протилежне. Тому для алгоритмів на графах іноді корисно побудувати транспонований граф, щоб звести граф до вигляду, придатнішого для потрібних операцій. Прикладом цього є алгоритм Косараджу для сильно зв'язних компонент, який застосовує двічі пошук у глибину, один раз для даного графа і вдруге для його транспонованого.
Пов'язані концепції Кососиметричний граф — це граф, ізоморфний своєму власному транспонованому графу через ізоморфізм особливого виду, який розбиває на пари всі вершини.
Обернене відношення бінарного відношення — це відношення, яке змінює на обернений порядок кожної пари пов'язаних відношенням об'єктів. Якщо відношення інтерпретувати як орієнтований граф, то обернене відношення відповідає транспонованому графу. Зокрема, двоїстий порядок часткового порядку можна інтерпретувати як транспонування транзитивно замкнутого спрямованого ациклічного графа.
Примітки
Література