Транспонований граф
Для орієнтованого графа G терміни транспонований[1] (англ. transpose[2]), обернений[3] (англ. converse або англ. reverse)[4] використовують для позначення іншого орієнтованого графа з тим самим набором вершин і з тими ж дугами, але протилежної орієнтації. Тобто, якщо граф G містить дугу (u, v), то транспонований/обернений граф графу G містить дугу (v, u), і навпаки.
Позначення[ред. | ред. код]
Назва обернений виникає тому, що обернення стрілок дуг відповідає оберненню логічного висновку в логіці. Термін транспонований походить із алгебри, оскільки матриця суміжності орієнтованого транспонованого графа є транспонованою матрицею матриці суміжності початкового графа.
Не існує усталеної думки, який з термінів кращий.
Транспонований граф може позначатися як G', GT, GR або інакше, залежно від прийнятої в статті або книзі термінології.
Застосування[ред. | ред. код]
Хоча математично різниця між графом та його транспонованим графом не велика, в інформатиці різниця може виявитися значною, залежно від способу подання графа. Наприклад, для вебграфа легко визначити вихідні з'єднання вершин, але важко визначити вхідні з'єднання, тоді як для транспонованого графа істинне протилежне. Тому для алгоритмів на графах іноді корисно побудувати транспонований граф, щоб звести граф до вигляду, придатнішого для потрібних операцій. Прикладом цього є алгоритм Косараджу для сильно зв'язних компонент, який застосовує двічі пошук у глибину, один раз для даного графа і вдруге для його транспонованого.
Пов'язані концепції[ред. | ред. код]
Кососиметричний граф — це граф, ізоморфний своєму власному транспонованому графу через ізоморфізм особливого виду, який розбиває на пари всі вершини.
Обернене відношення бінарного відношення — це відношення, яке змінює на обернений порядок кожної пари пов'язаних відношенням об'єктів. Якщо відношення інтерпретувати як орієнтований граф, то обернене відношення відповідає транспонованому графу. Зокрема, двоїстий порядок часткового порядку можна інтерпретувати як транспонування транзитивно замкнутого спрямованого ациклічного графа.
Примітки[ред. | ред. код]
- ↑ Тарануха В.Ю. (2021). Задачі на графах для курсу Алгоритміка (PDF) (Навчальний посібник). Київ. с. 22.
- ↑ Introduction to Algorithms, ex. 22.1–3, p. 530.
- ↑ Карнаух Т.О., Ставровський А.Б. (2004). Теорія графів у задачах (PDF). Київ: ВПЦ "Київський університет". с. 71. Архів оригіналу (PDF) за 31 березня 2022. Процитовано 6 вересня 2022.
- ↑ 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. — Bibcode:. — DOI:.