Изоморфи́зм — соотношение между математическими объектами, выражающее общность их строения; используется в разных разделах математики и в каждом из них определяется в зависимости от структурных свойств изучаемых объектов. Обычно изоморфизм определяется для множеств, наделённых некоторой структурой, например, для групп, колец, линейных пространств; в этом случае он определяется как обратимое отображение (биекция) между двумя множествами со структурой, сохраняющее эту структуру, то есть показывающее, что объекты «одинаково устроены» в смысле этой структуры. Если между объектами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Автоморфизм — изоморфизм между математическим объектом и им самим; отображение, изменяющее объект с сохранением всех его изначальных свойств. Множество всех автоморфизмов объекта образует группу автоморфизмов, которую можно рассматривать как обобщение группы симметрий объекта.
Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной:
Диэдральная группа — группа симметрии правильного многоугольника, включающая как вращения, так и осевые симметрии. Диэдральные группы являются простейшими примерами конечных групп и играют важную роль в теории групп, геометрии и химии. Хорошо известно и совершенно тривиально проверяется, что группа, образованная двумя инволюциями с конечным числом элементов в области определения является диэдральной группой.
Группа симметрии некоторого объекта ― группа всех преобразований, для которых данный объект является инвариантом, с композицией в качестве групповой операции. Как правило, рассматриваются множества точек n-мерного евклидова пространства и движения этого пространства, но понятие группы симметрии сохраняет свой смысл и в более общих случаях.
В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v1 и v2 графа G существует автоморфизм
В теории графов рёберно-транзитивным называется такой граф G, для двух любых рёбер которого e1 и e2 существует автоморфизм, отображающий e1 в e2.
Граф Радо — единственный счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов. Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.
Граф Фрухта — определённый планарный минимальный кубический граф, не имеющий нетривиальных автоморфизмов. Описан Робертом Фрухтом в 1939 году.
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм:
- f : V(G) → V(G)
Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.
Граф Татта — Коксетера — 3-регулярный граф с 30 вершинами и 45 рёбрами. Единственный наименьший кубический граф с обхватом 8, является клеткой и графом Мура. Двудольный и может быть построен как граф Леви обобщённого четырёхугольника W2. Назван в честь Уильяма Томаса Татта и Гарольда Коксетера. Найден Уильямом Таттом, но его связь с геометрической комбинацией исследована обоими авторами в паре совместных статей.
Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф. Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона — граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля.
Плоскость Фано — конечная проективная плоскость порядка 2, имеющая наименьшее возможное число точек и прямых, с тремя точками на каждой прямой и с тремя прямыми, проходящими через каждую точку. Названа по имени итальянского математика Джино Фано.
В математике абстрактный многогранник, неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).
Граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 рёбрами. Граф является уникальным сильно регулярным графом srg(100,22,0,6), т.е. никакая соседняя пара вершин не имеет общих соседей и любая несоседняя пара вершин имеет шесть общих соседей. Граф был впервые построен Меснером и был переоткрыт в 1968 Дональдом Дж. Хигманом и Чарльзом Симсом как путь определения группы Хигмана — Симса и эта группа является подгруппой с индексом два в группе автоморфизмов графа Хигмана — Симса.
Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.
