Русская Википедия:Размерность графа
Размерность графа — наименьшее целое Шаблон:Mvar такое, что существует «классическое представление» графа в евклидовом пространстве размерности Шаблон:Mvar с единичными длинами рёбер.
В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться[1].
Размерность графа Шаблон:Mvar записывается как <math>\dim G</math>.
Например, граф Петерсена может быть нарисован с единичными рёбрами в <math>E^2</math>, но не в <math>E^1</math>, его размерность поэтому равна 2 (см. рисунок справа).
Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям ТаттШаблон:Sfn. Она обобщает концепцию графа единичных расстояний для размерностей более 2.
Примеры
Полный граф
В худшем случае каждая пара вершин соединена, что даёт полный граф.
Для погружения полного графа <math>K_n</math> со всеми рёбрами единичной длины нам необходимо евклидово пространство размерности <math>n-1</math>[2]. Например, нужно двухмерное пространство для погружения <math>K_3</math> (равносторонний треугольник) и трёхмерное для погружения <math>K_4</math> (правильный тетраэдр) как показано справа.
- <math>\dim K_n=n-1</math>
Другими словами, размерность полного графа совпадает с размерностью симплекса, имеющего то же самое число вершин.
Полные двудольные графы
Все звёзды <math>K_{m,1}</math> для <math>m \geqslant 3</math> имеют размерность 2 как показано на рисунке слева. Для звёзд с Шаблон:Mvar равным 1 или 2 достаточна размерность 1.
Полный двудольный граф <math>K_{m,2}</math> для <math>m \geqslant 3</math> может быть нарисован как на рисунке справа путём расположения Шаблон:Mvar вершин на окружности, радиус которой меньше единицы, другие две точки располагаем по обеим сторонам от плоскости окружности на соответствующем расстоянии. <math>K_{2,2}</math> имеет размерность 2, так как он может быть нарисован на плоскости в виде ромба.
| Шаблон:Теорема
Шаблон:Начало скрытого блока Чтобы показать, что 4-мерного пространства достаточно, как и в предыдущем случае используем окружности. Обозначим координаты 4-мерного пространства <math>w, x, y, z</math>. Расположим один набор вершин произвольно на окружности <math>w^2+x^2=a, y=0, z=0</math>, где <math>0 < a < 1</math>, а другой произвольно на окружности <math>y^2+z^2=1-a, w=0, x=0</math>. Мы видим, что расстояние между любой вершиной из первого множества и любой вершиной из второго множества равно <math>{\sqrt{w^2+x^2+y^2+z^2}}={\sqrt{a+1-a}}=1</math>. Мы также можем показать, что подграф <math>K_{3,3}</math> не позволяет такого представления в размерности, меньшей 4: Если такое представление существует, то три точки <math>A_1</math>, <math>A_2</math> и <math>A_3</math> лежат на единичной сфере с центром <math>B_1</math>. Аналогично, они лежат на единичных сферах с центрами <math>B_2</math> и <math>B_3</math>. Первые две сферы должны пересекаться по окружности, в точке или не пересекаться вообще. Для размещения трёх различных точек <math>A_1</math>, <math>A_2</math> и <math>A_3</math> мы должны предположить пересечение по окружности. Либо эта окружность лежит полностью на третьей единичной сфере, откуда следует, что третья сфера совпадает с одной из первых двух, так что <math>B_1</math>, <math>B_2</math> и <math>B_3</math> не все различны. Если же окружности не пересекаются по окружности, они пересекаются с третьей сферой не более чем в двух точках, а этого недостаточно, чтобы расположить три точки <math>A_1</math>, <math>A_2</math> и <math>A_3</math>. Шаблон:Конец скрытого блока |
В итоге:
- <math>\dim K_{m,n}=1, 2, 3, 4</math>, в зависимости от значений Шаблон:Mvar и Шаблон:Mvar.
Размерность и хроматическое число
Шаблон:Теорема Шаблон:Начало скрытого блока Это доказательство использует окружности.
Обозначим через Шаблон:Mvar хроматическое число графа Шаблон:Mvar и назначим целые числа <math>(1..n)</math> для Шаблон:Mvar цветов. В <math>2n</math>-мерном евклидовом пространстве с размерностями, обозначенными через <math>x_1, x_2, .. x_{2n}</math>, мы располагаем все вершины цвета Шаблон:Mvar произвольно на окружности, заданной формулой <math>x_{2n-2}^2+x_{2n-1}^2=1/2,\quad x_i|(i\neq 2{n-2}, i\neq 2{n-1})=0</math>.
Тогда расстояние от вершины цвета Шаблон:Mvar до вершины цвета Шаблон:Mvar задаётся формулой <math>{\sqrt{x_{2p-2}^2+x_{2p-1}^2+x_{2q-2}^2+x_{2q-1}^2}}={\sqrt{1/2+1/2}}=1</math>. Шаблон:Конец скрытого блока
Евклидова размерность
Определение размерности графа, данное выше, утверждает для Шаблон:Mvar-минимального представления:
- если две вершины графа Шаблон:Mvar связаны ребром, они должны быть на расстоянии единица;
- однако две вершины на расстоянии единица не обязательно должны быть соединены ребром.
Это определение отвергается некоторыми авторами. Другое определение предложил в 1991 годуШаблон:Не переведено 5, которое он называет евклидовой размерностью графаШаблон:Sfn. Перед этим в 1980 году Пал Эрдёш и Шаблон:Не переведено 5 уже предложили это же определение под названием истинная размерностьШаблон:Sfn. По этому определению Шаблон:Mvar-минимальное представление — это то, в котором две вершины графа соединены тогда и только тогда, когда их представление находится на расстоянии 1.
Рисунок напротив показывает разницу между этими определениями для случая колеса, имеющего центральную вершину и шесть периферийных вершин с удалённой одной спицей. Представление графа на плоскости позволяет двум вершинам находиться на расстоянии 1, но при этом они не соединены.
Мы записываем евклидово расстояние как <math>\operatorname{Edim}G</math>. Оно никогда не меньше расстояния, определённого выше:
- <math>\dim G \leqslant \operatorname{Edim}G</math>
Евклидова размерность и максимальная степень
Пал Эрдёш и Миклош Шимонович доказали в 1980 году следующий результатШаблон:Sfn:
Вычислительная сложность
Задача NP-трудна, и более конкретно, для экзистенциальной теории вещественных чисел полна задача определения, больше или нет размерность или евклидова размерность данного графа заданного значения. Задача остаётся трудной даже для проверки, равна ли двум размерность или евклидова размерностьШаблон:Sfn.
Примечания
Литература
- ↑ Некоторые математики считают это «погружением», но многие теоретики графов, включая Эрдёша, Харари и Татта, использовали термин «вложение»
- ↑ Шаблон:Cite web
