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

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

Размерность графа Петерсена равна 2.

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

Размерность графа G записывается как $\dim <!--\; \; -->G$$\dim G$.

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

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

ПримерыПравить

 

Для 4 равноудалённых точек нужна размерность 3.

Полный графПравить

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

Для погружения полного графа $K_n$$K_n$  со всеми рёбрами единичной длины нам необходимо евклидово пространство размерности $n-<!--\; -\; -->1$$n-1$ . Например, нужно двухмерное пространство для погружения $K_3$$K_{3}$  (равносторонний треугольник) и трёхмерное для погружения $K_4$$K_{4}$  (правильный тетраэдр) как показано справа.

$\dim <!--\; \; -->K_n=n-<!--\; -\; -->1$$\dim K_{n}=n-1$ 

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

 

Полный двудольный граф $K_{4,2}$$K_{4,2}$  нарисованный в евклидовом 3-мерном пространстве.

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

 

Граф-звезда, нарисованный на плоскости с рёбрами единичной длины.

Все звёзды $K_{m,1}$$K_{m,1}$  для $m⩾<!--\; ⩾\; -->3$$m\geqslant 3$  имеют размерность 2 как показано на рисунке слева. Для звёзд с m равным 1 или 2 достаточна размерность 1.

Полный двудольный граф $K_{m,2}$$K_{m,2}$  для $m⩾<!--\; ⩾\; -->3$$m\geqslant 3$  может быть нарисован как на рисунке справа путём расположения m вершин на окружности, радиус которой меньше единицы, другие две точки располагаем по обеим сторонам от плоскости окружности на соответствующем расстоянии. $K_{2,2}$$K_{2,2}$  имеет размерность 2, так как он может быть нарисован на плоскости в виде ромба.

Размерность полного двудольного графа $K_{m,n}$$K_{{m,n}}$  для $m⩾<!--\; ⩾\; -->3$$m\geqslant 3$  и $n⩾<!--\; ⩾\; -->3$$n\geqslant 3$  равна 4. Доказательство Чтобы показать, что 4-мерного пространства достаточно, как и в предыдущем случае используем окружности. Обозначим координаты 4-мерного пространства $w,x,y,z$$w,x,y,z$ . Расположим один набор вершин произвольно на окружности $w^2+x^2=a,y=0,z=0$$w^{2}+x^{2}=a,y=0,z=0$ , где $0<a<1$ , а другой произвольно на окружности $y^2+z^2=1-<!--\; -\; -->a,w=0,x=0$$y^{2}+z^{2}=1-a,w=0,x=0$ . Мы видим, что расстояние между любой вершиной из первого множества и любой вершиной из второго множества равно $\sqrt{w^2+x^2+y^2+z^2}=\sqrt{a+1-<!--\; -\; -->a}=1$${\sqrt {w^{2}+x^{2}+y^{2}+z^{2}}}={\sqrt {a+1-a}}=1$ . Мы также можем показать, что подграф $K_{3,3}$$K_{{3,3}}$  не позволяет такого представления в размерности, меньшей 4: Если такое представление существует, то три точки $A_1$$A_{1}$ , $A_2$$A_{2}$  и $A_3$$A_{3}$  лежат на единичной сфере с центром $B_1$$B_1$ . Аналогично, они лежат на единичных сферах с центрами $B_2$$B_{2}$  и $B_3$$B_{3}$ . Первые две сферы должны пересекаться по окружности, в точке или не пересекаться вообще. Для размещения трёх различных точек $A_1$$A_{1}$ , $A_2$$A_{2}$  и $A_3$$A_{3}$  мы должны предположить пересечение по окружности. Либо эта окружность лежит полностью на третьей единичной сфере, откуда следует, что третья сфера совпадает с одной из первых двух, так что $B_1$$B_1$ , $B_2$$B_{2}$  и $B_3$$B_{3}$  не все различны. Если же окружности не пересекаются по окружности, они пересекаются с третьей сферой не более чем в двух точках, а этого недостаточно, чтобы расположить три точки $A_1$$A_{1}$ , $A_2$$A_{2}$  и $A_3$$A_{3}$ .

В итоге:

$\dim <!--\; \; -->K_{m,n}=1,2,3,4$$\dim K_{m,n}=1,2,3,4$ , в зависимости от значений m и n.

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

Размерность графа G всегда меньше или равна удвоенному хроматическому числу: $\dim <!--\; \; -->G⩽<!--\; ⩽\; -->2\mathrm{\chi <!--\; \chi \; -->}(G)$$\dim G\leqslant 2\,\chi (G)$

Доказательство

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

Обозначим через n хроматическое число графа G и назначим целые числа $(\mathrm{1..}n)$$(1..n)$  для n цветов. В $2n$$2n$ -мерном евклидовом пространстве с размерностями, обозначенными через $x_1,x_2,..x_{2n}$$x_{1},x_{2},..x_{2n}$ , мы располагаем все вершины цвета n произвольно на окружности, заданной формулой $x_{2n-<!--\; -\; -->2}^2+x_{2n-<!--\; -\; -->1}^2=1/2,x_i|(i\ne <!--\; \ne \; -->2n-<!--\; -\; -->2,i\ne <!--\; \ne \; -->2n-<!--\; -\; -->1)=0$$x_{2n-2}^{2}+x_{2n-1}^{2}=1/2,\quad x_{i}|(i\neq 2{n-2},i\neq 2{n-1})=0$ .

Тогда расстояние от вершины цвета p до вершины цвета q задаётся формулой $\sqrt{x_{2p-<!--\; -\; -->2}^2+x_{2p-<!--\; -\; -->1}^2+x_{2q-<!--\; -\; -->2}^2+x_{2q-<!--\; -\; -->1}^2}=\sqrt{1/2+1/2}=1$${\sqrt {x_{2p-2}^{2}+x_{2p-1}^{2}+x_{2q-2}^{2}+x_{2q-1}^{2}}}={\sqrt {1/2+1/2}}=1$ .

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

 

Колесо с одной удалённой спицей имеет размерность 2.

 

То же самое колесо имеет евклидову размерность 3.

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

• если две вершины графа G связаны ребром, они должны быть на расстоянии единица;
• однако две вершины на расстоянии единица не обязательно должны быть соединены ребром.

Это определение отвергается некоторыми авторами. Другое определение предложил в 1991 годуАлександр Сойфер^[en], которое он называет евклидовой размерностью графа. Перед этим в 1980 году Пал Эрдёш и Миклош Шимонович^[en] уже предложили это же определение под названием истинная размерность. По этому определению n-минимальное представление — это то, в котором две вершины графа соединены тогда и только тогда, когда их представление находится на расстоянии 1.

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

Мы записываем евклидово расстояние как $\mathrm{Edim}<!--\; \; -->G$$\operatorname {Edim} G$ . Оно никогда не меньше расстояния, определённого выше:

$\dim <!--\; \; -->G⩽<!--\; ⩽\; -->\mathrm{Edim}<!--\; \; -->G$$\dim G\leqslant \operatorname {Edim} G$ 

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

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

Евклидова размерность графа G не больше чем его удвоенная максимальная степень + 1: $\mathrm{Edim}<!--\; \; -->G⩽<!--\; ⩽\; -->2\mathrm{\Delta <!--\; \Delta \; -->}(G)+1$$\operatorname {Edim} G\leqslant 2\,\Delta (G)+1$

Вычислительная сложностьПравить

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

ЛитератураПравить

• Erdős P., Harary F., Tutte W. T. On the dimension of a graph // Mathematika. — 1965. — Т. 12. — doi:10.1112/s0025579300005222.
• Alexander Soifer. The Mathematical Coloring Book. — Springer, 2009. — ISBN 978-0-387-74640-1.
• Erdős P., Simonovits M. On the chromatic number of geometric graphs // Ars Comb.. — 1980. — Вып. 9. — С. 229–246.
• Marcus Schaefer. Realizability of graphs and linkages // Thirty Essays on Geometric Graph Theory / János Pach. — Springer, 2013. — С. 461–482. — doi:10.1007/978-1-4614-0110-0_24.