Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.
В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду.
В данном списке приводятся математические утверждения и объекты, названные именем венгерского математика Пала Эрдёша.
В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром. Окрестностью вершины v в графе G называется порождённый подграф графа G, состоящий из всех вершин, сопряжённых v и всех рёбер, соединяющих две такие вершины. Например, рисунок показывает граф с 6 вершинами и 7 рёбрами. Вершина 5 смежна вершинам 1, 2 и 4, но не смежна вершинам 3 и 6. Окрестность вершины 5 — это граф с тремя вершинами 1, 2 и 4, и одним ребром, соединяющим вершины 1 и 2.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
В теории графов графом Шлефли называется 16-регулярный ненаправленный граф с 27 вершинами и 216 рёбрами. Граф назван в честь Людвига Шлефли. Это сильно регулярный граф с параметрами srg(27, 16, 10, 8).
Граф Радо — единственный счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов. Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины.
В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения.
В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф. Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона — граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля.
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
В теории графов граф «бабочка» — это планарный неориентированный граф с 5 вершинами и 6 рёбрами. Граф может быть построен объединением двух копий циклов C3 по одной общей вершине, а потому граф изоморфен графу дружеских отношений F2.
Универсальный граф — это бесконечный граф, содержащий любой конечный граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и отражает другие меры разреженности, такие как древесность графа.
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр, ни нечётных антидыр. Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нейла Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
