Изоморфи́зм — соотношение между математическими объектами, выражающее общность их строения; используется в разных разделах математики и в каждом из них определяется в зависимости от структурных свойств изучаемых объектов. Обычно изоморфизм определяется для множеств, наделённых некоторой структурой, например, для групп, колец, линейных пространств; в этом случае он определяется как обратимое отображение (биекция) между двумя множествами со структурой, сохраняющее эту структуру, то есть показывающее, что объекты «одинаково устроены» в смысле этой структуры. Если между объектами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Автоморфизм — изоморфизм между математическим объектом и им самим; отображение, изменяющее объект с сохранением всех его изначальных свойств. Множество всех автоморфизмов объекта образует группу автоморфизмов, которую можно рассматривать как обобщение группы симметрий объекта.
В теории графов мультиграфом называется граф, в котором разрешается присутствие кратных рёбер, то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром.
Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.
Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых.
Гамильтонов граф — граф, содержащий гамильтонов цикл. При этом гамильтоновым циклом является такой цикл, который проходит через каждую вершину данного графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа.
Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Граф Радо — единственный счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов. Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.
В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона, в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .
В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Файл назван в честь А. Голднера и Ф. Харари, которые в 1975 году доказали, что он является наименьшим негамильтоновым максимальным планарным графом. Тот же самый граф был уже приведён в качестве примера негамильтонова симплициального многогранника Грюнбаумом в 1967.
В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф. Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона — граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля.
В математике абстрактный многогранник, неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).
Рёберное покрытие графа — это множество рёбер C, такое, что каждая вершина графа инцидентна по меньшей мере одному ребру из C.
Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.
Граф Шрикханде — граф, найденный С. С. Шрикханде в 1959 году. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.
