Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
В теории графов мультиграфом называется граф, в котором разрешается присутствие кратных рёбер, то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром.
Алгори́тм Де́йкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.
Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других людей, чётно.
В математике конференс-матрица (также называемая C-матрица, конференц-матрица) — это квадратная матрица C с нулями на диагонали, и с +1 и −1 вне диагонали такая, что CTC кратна единичной матрице I. Таким образом, если матрица C имеет порядок n, то CTC = (n−1)I. Некоторые авторы дают более общее определение, требуя наличия нуля в каждой строке и в каждом столбце, но не обязательно на диагонали.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины.
Граф Дезарга — дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами. Назван в честь Жерара Дезарга. Возникает в некоторых комбинаторных построениях, имеет высокую степень симметрии, это единственный известный непланарный кубический частичный куб и применяется в химических базах данных.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.
В теории графов «мельница» Wd(k,n) — это неориентированный граф, построенный для k ≥ 2 и n ≥ 2 путём объединения n копий полных графов Kk в одной общей вершине. То есть это сумма по 1-клике этих полных графов.
В теории графов части́чный куб — это подграф гиперкуба, сохраняющий расстояния — расстояние между любыми двумя вершинами подграфа то же самое, что и в исходном графе. Эквивалентно, частичный куб — это граф, вершины которого можно пометить битовыми строками одинаковой длины, так что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между этими двумя метками. Такая разметка называется разметкой Хэмминга и она представляет изометричное вложение частичного куба в гиперкуб.
Универсальный граф — это бесконечный граф, содержащий любой конечный граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.
Совершенная разметка рёбер графа — это вид разметки графа. Это разметка для простых графов. Совершенные разметки рёбер ввёл в своей статье С. Ло.
Граф дружеских отношений Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Разметка графа в математике — это назначение меток, которые традиционно представляются целыми числами, рёбрами, вершинами, или рёбрам, и вершинам графа.
Ку́бы Фибона́ччи, или фибона́ччиевы се́ти, — это семейство неориентированных графов с богатыми рекурсивными свойствами, возникшее в теории чисел. Математически эти кубы похожи на графы гиперкуба, но с числом вершин, равным числу Фибоначчи. Кубы Фибоначчи впервые явно определил в своей статье Сюй в контексте взаимосвязей топологий для связи систем параллельных вычислений или распределённых систем. Они применяются также в химической теории графов.
Книга может быть любым графом некоторого вида, который образован циклами, имеющими общее ребро.
