Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

Обозначения

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

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

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

Приложения

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

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

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

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

Примечания

  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. — Bibcode1970RvMP...42..271E.
Эта страница в последний раз была отредактирована 16 апреля 2019 в 15:54.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).