Размерность (теория графов)

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

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

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

Размерность графа G записывается $\dim G$.

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

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

Примеры

Имея 4 равноотстоящие друг от друга точки, нам нужны 3 измерения.

Полный график

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

Чтобы погрузить полный график $K_{n}$ поскольку все ребра имеют единичную длину, нам нужно евклидово пространство размерности $n-1$. Например, для погружения требуется два измерения. $K_{3}$ (равносторонний треугольник) и три для погружения $K_{4}$ (правильный тетраэдр), как показано справа.

$\dim K_{n}=n-1$

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

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

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

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

Все звездные графики $K_{m,1}$, для $m\geq 3$, имеют размерность 2, как показано на рисунке слева. Звездчатым графам с m, равным 1 или 2, требуется только измерение 1.

Размерность полного двудольного графа $K_{m,2}$, для $m\geq 3$, можно нарисовать, как показано на рисунке справа, поместив m вершин на круг, радиус которого меньше единицы, а две другие вершины — по одной с каждой стороны плоскости круга, на подходящем расстоянии от нее. $K_{2,2}$ имеет размерность 2, так как его можно изобразить на плоскости как единичный ромб.

Теорема . Размерность общего полного двудольного графа. $K_{m,n}$, для $m\geq 3$ и $n\geq 3$, равно 4. показывать Доказательство To show that 4-space is sufficient, as with the previous case, we use circles. Denoting the coordinates of the 4-space by $w,x,y,z$, we arrange one set of vertices arbitrarily on the circle given by $w^{2}+x^{2}=a,y=0,z=0$ where $0<a<1$, and the other set arbitrarily on the circle $y^{2}+z^{2}=1-a,w=0,x=0$. Then we see that the distance between any vertex in one set and any vertex in the other set is ${\sqrt {w^{2}+x^{2}+y^{2}+z^{2}}}={\sqrt {a+1-a}}=1$. We can also show that the subgraph $K_{3,3}$ does not admit such a representation in a space of dimension less than 3: If such a representation exists, then the three points $A_{1}$, $A_{2}$ and $A_{3}$ lie on a unit sphere with center $B_{1}$. Likewise, they lie on unit spheres with centers $B_{2}$ and $B_{3}$. The first two spheres must intersect in a circle, in a point, or not at all; to accommodate the three distinct points $A_{1}$, $A_{2}$ and $A_{3}$, we must assume a circle. Either this circle lies entirely on the third unit sphere, implying that the third sphere coincides with one of the other two, so $B_{1}$, $B_{2}$ and $B_{3}$ are not all distinct; or it does not, so its intersection with the third sphere is no more than two points, insufficient to accommodate $A_{1}$, $A_{2}$ and $A_{3}$.

Подводя итог:

$\dim K_{m,n}=1,2,3{\text{ or }}4$, в зависимости от значений m и n .

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

Теорема . Размерность любого графа G всегда меньше или равна удвоенному его хроматическому числу :

$\dim G\leq 2\,\chi (G)$

показывать

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

This proof also uses circles.

We write n for the chromatic number of G, and assign the integers $(1..n)$ to the n colours. In $2n$-dimensional Euclidean space, with its dimensions denoted $x_{1},x_{2},..x_{2n}$, we arrange all the vertices of colour n arbitrarily on the circle given by $x_{2n-2}^{2}+x_{2n-1}^{2}=1/2,\quad x_{i}|(i\neq 2{n-2},i\neq 2{n-1})=0$.

Then the distance from a vertex of colour p to a vertex of colour q is given by ${\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 году Александром Сойфером для того, что он назвал евклидовым измерением графа. Ранее, в 1980 году, Пауль Эрдеш и Миклош Симоновиц уже предлагали его под названием « Верное измерение» . По этому определению минимальное представление — это такое, в котором две вершины графа соединены тогда и только тогда, когда их представления находятся на расстоянии 1.

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

Мы запишем это измерение как $\operatorname {Edim} G$. Он никогда не может быть меньше размера, определенного выше:

$\dim G\leq \operatorname {Edim} G$

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

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

Теорема . Евклидова размерность графа G не более чем в два раза превышает его максимальную степень плюс один:

$\operatorname {Edim} G\leq 2\,\Delta (G)+1$

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

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