Открыть главное меню
Graph isomorphism a.svg Graph isomorphism b.svg
Пример двух изоморфных графов. Изоморфизм ставит в соответствие вершинам одного графа вершины другого графа того же цвета: две вершины соединены ребром в одном графе тогда и только тогда, когда вершины тех же цветов соединены ребром в другом графе.

Изоморфи́зм (от др.-греч. ἴσος — «равный, одинаковый, подобный» и μορφή — «форма») — это очень общее понятие, которое определяется по-разному в различных разделах математики. Изоморфизм определяется для множеств, наделённых некоторой структурой (например, для групп, колец, линейных пространств и т. п.). В общих чертах его можно описать так: обратимое отображение (биекция) между двумя множествами, наделёнными структурой, называется изоморфизмом, если оно сохраняет эту структуру. Если между такими структурами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.

Так, например, два графа называются изоморфными, если между ними существует изоморфизм: то есть вершинам одного графа можно сопоставить вершины другого графа, так чтобы соединённым вершинам первого графа соответствовали соединённые вершины второго графа и наоборот. Иными словами, два графа изоморфны, если они «одинаковы» (с точностью до переименования вершин).

В общем случае, объекты, между которыми существует изоморфизм, являются «одинаково устроенными» в смысле этой структуры.

Другим классическим примером изоморфных систем могут служить множество всех вещественных чисел с определённой на нём операцией сложения и множество положительных вещественных чисел с заданной на нём операцией умножения. Отображение в этом случае является изоморфизмом.

Общая алгебраПравить

В общей алгебре изоморфизмом называется обратимое отображение, которое является гомоморфизмом. Ниже приводятся несколько примеров.

ГруппыПравить

Пусть   и   — две группы. Биекция   называется изоморфизмом, если для любых  

 .

Если группа является топологической, добавляется условие гомеоморфности соответствующих топологических пространств.[1]

ПоляПравить

Пусть   и   — поля. Биекция   называется изоморфизмом, если она сохраняет обе операции поля, то есть для любых   выполняется

  1.  ,
  2.  .

Пример. Факторкольцо для кольца многочленов с вещественными коэффициентами   по модулю многочлена   является полем, изоморфным[2] полю комплексных чисел  

 

Для полей с дополнительной структурой (упорядоченные, топологические поля и т. д.) может добавляться условие, что биекция сохраняет также эти дополнительные структуры.

Теория множествПравить

В теории множеств любая биекция является изоморфизмом.

К примеру, два частично упорядоченных множества изоморфны, если между ними есть биекция, сохраняющая порядок[3].

Изоморфизм в теории категорийПравить

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

Нормированные пространстваПравить

Для нормированных пространств отображение одного из них в другое называется изоморфизмом нормированных пространств, если оно линейно, непрерывно и биективно, и обратное отображение тоже непрерывно. В этом смысле изоморфизм сохраняет структуру линейного пространства и топологию, но не обязательно сохраняет норму. Если изоморфизм еще и сохраняет норму, то он называется изометрическим изоморфизмом или изометрией[4].

Теория графовПравить

Основная статья: Изоморфизм графов

Граф   называется изоморфным графу  , если существует биекция   из множества вершин графа   в множество вершин графа  , обладающая следующим свойством: если в графе   есть ребро из вершины   в вершину  , то в графе   должно быть ребро из вершины   в вершину   и наоборот — если в графе   есть ребро из вершины   в вершину  , то в графе   должно быть ребро из вершины   в вершину  . В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

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

Связанные определенияПравить

Изоморфизм алгебраической системы на себя называется автоморфизмом.

ИсторияПравить

Понятие изоморфизма возникло в математике применительно к группам и было естественным образом распространено на более широкий класс математических структур.

Вариации и обобщенияПравить

  • Некоторая общая теория, уточняющая понятия изоморфизма (и других близких понятий) была предложена группой Бурбаки в их книге «Теория множеств» (Глава 4. Структуры).

См. такжеПравить

ПримечанияПравить

  1. Л. С. Понтрягин Непрерывные группы стр. 392
  2. Фаддеев Д. К. Лекции по алгебре. — М.: Наука, 1984. — С. 200—201. — 416 с.
  3. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. стр. 48
  4. Петр Бородин, А. Савчук, И. Шейпак. Задачи по функциональному анализу. — МЦНМО, 2017. — С. 28. — 337 с. — ISBN 9785040485147.

ЛитератураПравить

СсылкиПравить