Размерность графа

Размерность графа — наименьшее целое  такое, что существует «классическое представление» графа в евклидовом пространстве размерности  с единичными длинами рёбер.

В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться.

Размерность графа  записывается как .

Например, граф Петерсена может быть нарисован с единичными рёбрами в , но не в , его размерность поэтому равна 2 (см. рисунок справа).

Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям Татт. Она обобщает концепцию графа единичных расстояний для размерностей более 2.

Примеры

Полный граф 
В худшем случае каждая пара вершин соединена, что даёт полный граф.

Для погружения полного графа  со всеми рёбрами единичной длины нам необходимо евклидово пространство размерности . Например, нужно двухмерное пространство для погружения  (равносторонний треугольник) и трёхмерное для погружения  (правильный тетраэдр) как показано справа.
 

Другими словами, размерность полного графа совпадает с размерностью симплекса, имеющего то же самое число вершин.

Полные двудольные графы 

Все звёзды  для  имеют размерность 2 как показано на рисунке слева. Для звёзд с  равным 1 или 2 достаточна размерность 1.

Полный двудольный граф  для  может быть нарисован как на рисунке справа путём расположения  вершин на окружности, радиус которой меньше единицы, другие две точки располагаем по обеим сторонам от плоскости окружности на соответствующем расстоянии.  имеет размерность 2, так как он может быть нарисован на плоскости в виде ромба.

В итоге:
 , в зависимости от значений  и .

Размерность и хроматическое число 

Это доказательство использует окружности.

Обозначим через  хроматическое число графа  и назначим целые числа  для  цветов. В -мерном евклидовом пространстве с размерностями, обозначенными через , мы располагаем все вершины цвета  произвольно на окружности, заданной формулой .

Тогда расстояние от вершины цвета  до вершины цвета  задаётся формулой .

Евклидова размерность 

Определение размерности графа, данное выше, утверждает для -минимального представления:
 если две вершины графа  связаны ребром, они должны быть на расстоянии единица;
 однако две вершины на расстоянии единица не обязательно должны быть соединены ребром.

Это определение отвергается некоторыми авторами. Другое определение предложил в 1991 году, которое он называет евклидовой размерностью графа. Перед этим в 1980 году Пал Эрдёш и  уже предложили это же определение под названием истинная размерность. По этому определению -минимальное представление — это то, в котором две вершины графа соединены тогда и только тогда, когда их представление находится на расстоянии 1.

Рисунок напротив показывает разницу между этими определениями для случая колеса, имеющего центральную вершину и шесть периферийных вершин с удалённой одной спицей. Представление графа на плоскости позволяет двум вершинам находиться на расстоянии 1, но при этом они не соединены.

Мы записываем евклидово расстояние как . Оно никогда не меньше расстояния, определённого выше:

Евклидова размерность и максимальная степень 
Пал Эрдёш и Миклош Шимонович доказали в 1980 году следующий результат:

Вычислительная сложность 
Задача NP-трудна, и более конкретно, для экзистенциальной теории вещественных чисел полна задача определения, больше или нет размерность или евклидова размерность данного графа заданного значения.
Задача остаётся трудной даже для проверки, равна ли двум размерность или евклидова размерность.

Примечания

Литература 
 
 
 
 

Геометрическая теория графов
Инварианты графов