Алгори́тм Де́йкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.
Двудо́льный граф или бигра́ф в теории графов — это граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. То есть, между вершинами одной и той же части рёбра отсутствуют.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины.
В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.
В теории графов рамочным графом называется вид неориентированного графа, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.
В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.
Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности.Граф несравнимости — это неориентированный граф, в котором пары элементов соединяются ребром, если элементы несравнимы в некотором частичном порядке.
Блоковый граф — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.
В теории графов дистанционно-наследуемый граф — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе. Таким образом, любой порождённый подграф наследует расстояния большего графа.
Птолеме́ев граф — это неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея. Птолемеевы графы — это в точности графы, которые одновременно являются и хордальными, и дистанционно наследуемыми. Эти графы включают блоковые графы и являются подклассом совершенных графов.
В теории графов части́чный куб — это подграф гиперкуба, сохраняющий расстояния — расстояние между любыми двумя вершинами подграфа то же самое, что и в исходном графе. Эквивалентно, частичный куб — это граф, вершины которого можно пометить битовыми строками одинаковой длины, так что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между этими двумя метками. Такая разметка называется разметкой Хэмминга и она представляет изометричное вложение частичного куба в гиперкуб.
Фактор-критический граф — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание.
Двудольное двойное покрытие неориентированного графа G — это двудольный накрывающий граф графа G с двойным числом вершин по сравнению с G. Покрытие можно построить как тензорное произведение графов, G × K2. Это покрытие также называется двойным покрытием Кронекера или каноническим двойным покрытием графа G.
st-Планарный граф — это биполярная ориентация планарного графа, для которого как источник, так и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что не имеется ориентированных циклов в графе, точно одна вершина графа не имеет входных дуг, точно одна вершина графа не имеет исходящих дуг, и обе эти две специальные вершины лежат на внешней грани графа.
Граф чётности — это граф, в котором любые два порождённых пути между двумя вершинами имеют одинаковую чётность — либо оба пути имеют нечётные длины, либо оба пути имеют чётные длины. Этот класс графов первым начали изучать и дали ему название Барлет и Ури.
Хорда́льный двудо́льный граф — это двудольный граф 
, в котором любой цикл длины по меньшей мере 6 в B имеет хорду, то есть ребро, которое соединяет две вершины, находящиеся на расстоянии > 1. Следовало бы называть эти графы «слабо хордальными и двудольными», поскольку хордальные двудольные графы, вообще говоря, не хордальны, так как могут содержать порождённый путь длины 4.
