Блок-схема — это множество вместе с семейством подмножеств, члены которого удовлетворяют некоторым свойствам, которые считаются полезными для конкретного приложения. Эти приложения приходят из разных областей, включая планирование эксперимента, конечную геометрию, тестирование программного обеспечения, криптографию и алгебраическую геометрию. Рассматривалось много вариантов, но наиболее интенсивно изучались сбалансированные неполные блок-схемы, которые исторически были связаны со статистическими задачами при планировании эксперимента.
В математике конференс-матрица (также называемая C-матрица, конференц-матрица) — это квадратная матрица C с нулями на диагонали, и с +1 и −1 вне диагонали такая, что CTC кратна единичной матрице I. Таким образом, если матрица C имеет порядок n, то CTC = (n−1)I. Некоторые авторы дают более общее определение, требуя наличия нуля в каждой строке и в каждом столбце, но не обязательно на диагонали.
В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром. Окрестностью вершины v в графе G называется порождённый подграф графа G, состоящий из всех вершин, сопряжённых v и всех рёбер, соединяющих две такие вершины. Например, рисунок показывает граф с 6 вершинами и 7 рёбрами. Вершина 5 смежна вершинам 1, 2 и 4, но не смежна вершинам 3 и 6. Окрестность вершины 5 — это граф с тремя вершинами 1, 2 и 4, и одним ребром, соединяющим вершины 1 и 2.
Экспандер — сильносвязный разреженный граф, при этом связность может определяться по вершинам, дугам или спектру.
В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона, в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .
Сильно регулярный граф — вариация понятия регулярный граф.
В математике энергия графа — это сумма абсолютных величин собственных значений матрицы смежности графа. Эта величина изучается в контексте спектральной теории графов.
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
В математике два-граф это (неупорядоченное) множество троек, выбранных из конечного множества вершин X таким образом, что любая (неупорядоченная) четвёрка из X содержит чётное число выбранных троек два-графа. В регулярном (однородном) два-графе любая пара вершин лежит в одном и том же числе троек два-графа. Два-графы изучаются ввиду их связи с равноугольными прямыми, связи регулярных два-графов с сильно регулярными графами, а также ввиду связи регулярных два-графов с конечными группами, поскольку многие из этих графов имеют интересные группы автоморфизмов.
Равноугольные прямые — семейство прямых в евклидовом пространстве такое, что угол между любыми двумя прямыми из этого множества один и тот же.
Пусть имеется структура инцидентности 
, состоящая из точек 
, прямых 
и флагов 
. Говорят, что точка 
инцидентна прямой 
, если 
. Структура называется конечной частичной геометрией, если существуют целые числа 
, такие, что:
- Для любой пары различных точек и
существует максимум одна прямая, инцидентная обеим точкам. - Каждая прямая инцидентна
точкам. - Каждая точка инцидентна
прямым. - Если точка и прямая не инцидентны, существует в точности
пар 
, таких, что инцидентна 
, а инцидентна .
В спектральной теории графов граф Рамануджана, названный по имени индийского математика Рамануджана, — это регулярный граф, спектральная щель которого почти настолько велика, насколько это возможно. Такие графы являются прекрасными спектральными экспандерами.
Граф Шрикханде — граф, найденный С. С. Шрикханде в 1959 году. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.
Граф судоку — это неориентированный граф, вершины которого представляют ячейки (пустой) головоломки судоку, а рёбра представляют пары ячеек, которые принадлежат той же строке, тому же столбцу или блоку головоломки. Задача головоломки судоку может быть представлена как расширение предварительной раскраски на этом графе. Граф является целочисленным графом Кэли.
Граф Брауэра — Хемерса — 20-регулярный неориентированный граф с 81 вершиной и 810 рёбрами. Это сильно регулярный, дистанционно-транзитивный граф и граф Рамануджана. Хотя его построение является математическим фольклором, он был назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые доказали его единственность в качестве строго регулярного графа.
Задача Конвея о 99-вершинном графе — нерешённая задача, которая спрашивает, существует ли неориентированный граф с 99 вершинами, в которых каждые две смежные вершины имеют в точности одного общего соседа и в которых две несмежные вершины имеют в точности два общих соседа. Эквивалентно, любое ребро должно быть частью единственного треугольника, а любая пара несмежных вершин должна быть на диагонали единственного 4-цикла. Джон Хортон Конвей объявил о призе в 1000 долларов тому, кто решит эту проблему.
Граф Геймса — это наибольший из известных локально линейных сильно регулярных графов. Его параметры как сильно регулярного графа равны (729,112,1,20). Это значит, что граф имеет 729 вершин и 40824 рёбер. Каждое ребро находится в единственном треугольнике и каждая несмежная пара вершин имеет в точности 20 общих соседей. Граф назван именем Ричарда А. Геймса, который предложил его построение в неопубликованной переписке и написал о связанных конструкциях.
Спектр графа - это множество собственных значений матрицы смежности графа.
