Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
В теории графов мультиграфом называется граф, в котором разрешается присутствие кратных рёбер, то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона, в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.
Сильно регулярный граф — вариация понятия регулярный граф.
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.
Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрами. Граф представляет собой полный граф 
без одного ребра.
Граф Холла — Янко, также называемый графом Холла — Янко — Уэлса, это 36-регулярный неориентированный граф со 100 вершинами и 1800 рёбрами.
Граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 рёбрами. Граф является уникальным сильно регулярным графом srg(100,22,0,6), т.е. никакая соседняя пара вершин не имеет общих соседей и любая несоседняя пара вершин имеет шесть общих соседей. Граф был впервые построен Меснером и был переоткрыт в 1968 Дональдом Дж. Хигманом и Чарльзом Симсом как путь определения группы Хигмана — Симса и эта группа является подгруппой с индексом два в группе автоморфизмов графа Хигмана — Симса.
Граф Шрикханде — граф, найденный С. С. Шрикханде в 1959 году. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.
Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q4.
Граф M22, называемый также графом Меснера, это единственный сильно регулярный граф с параметрами (77, 16, 0, 4). Граф строится из системы Штейнера (3, 6, 22), принимая его 77 блоков в качестве вершин и соединяя две вершины тогда и только тогда, когда они не имеют общих элементов. Граф можно получить также удалением вершины и её соседей из графа Хигмана — Симса.
Спектр графа - это множество собственных значений матрицы смежности графа.
Медиафайлы на Викискладе
