Измерение (теория графов)

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

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

Размерность графа $G$ обозначается как . $\dim G$

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

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

Примеры

При наличии четырех равноудаленных точек нам понадобится три измерения.

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

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

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

\dim K_{n}=n-1

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

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

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

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

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

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

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

Теорема — Размерность общего полного двудольного графа для и равна 4. $K_{м,н}$ $m\geq 3$ $n\geq 3$

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

Чтобы показать, что 4-мерного пространства достаточно, как и в предыдущем случае, мы используем круги.

Обозначая координаты 4-пространства через , мы располагаем один набор вершин произвольно на окружности, заданной как , а другой набор произвольно на окружности . Тогда мы видим, что расстояние между любой вершиной в одном наборе и любой вершиной в другом наборе равно . $w,x,y,z$ $w^{2}+x^{2}=a,y=0,z=0$ $0<а<1$ $y^{2}+z^{2}=1-a,w=0,x=0$ ${\sqrt {w^{2}+x^{2}+y^{2}+z^{2}}}={\sqrt {a+1-a}}=1$

Мы также можем показать, что подграф не допускает такого представления в пространстве размерности меньше 3: $К_{3,3}$

Если такое представление существует, то три точки , и лежат на единичной сфере с центром . Аналогично, они лежат на единичных сферах с центрами и . Первые две сферы должны пересекаться по окружности, в точке или вообще не пересекаться; чтобы разместить три различные точки , и , мы должны предположить окружность. Либо эта окружность полностью лежит на третьей единичной сфере, подразумевая, что третья сфера совпадает с одной из двух других, так что , и не все различны; либо это не так, так что ее пересечение с третьей сферой не более чем в двух точках, недостаточно для размещения , и . $А_{1}$ $A_{2}$ $A_{3}$ $B_{1}$ $B_{2}$ $B_{3}$ $А_{1}$ $A_{2}$ $A_{3}$ $B_{1}$ $B_{2}$ $B_{3}$ $А_{1}$ $A_{2}$ $A_{3}$

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

\dim K_{m,n}=1,2,3{\text{ или }}4

, в зависимости от значений

m

и

n

.

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

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

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

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

В этом доказательстве также используются круги.

Обозначим $n$ как хроматическое число $G$ и присвоим целые числа цветам $n$ . В -мерном евклидовом пространстве, размеры которого обозначены , мы произвольно располагаем все вершины цвета $n$ на окружности, заданной . $(1..n)$ $2n$ $x_{1},x_{2},..x_{2n}$ $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$

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

Граф колеса с удаленной одной спицей имеет размерность 2.

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

Приведенное выше определение размерности графа говорит о минимальном $n-$ представлении:

если две вершины $G$ соединены ребром, они должны находиться на единичном расстоянии друг от друга;
Однако две вершины, находящиеся на единичном расстоянии друг от друга, не обязательно соединены ребром.

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

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

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

\dim G\leq \operatorname {Edim} G

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

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

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

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

Сложность вычислений

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

Ссылки

^ Некоторые математики рассматривают это строго как « погружение », но многие специалисты по теории графов, включая Эрдёша, Харари и Тутте, используют термин « вложение ».
^ Эрдеш, П.; Харари, Ф.; Тутте, WT (1965). «О размерности графа» (PDF) . Математика . 12 (2): 118– 122. doi : 10.1112/s0025579300005222. hdl : 2027.42/152495 .
^ Каванг, Райан. «Исследования размерности графов» (PDF) . Получено 16 августа 2018 г.
^ Сойфер, Александр (2009). Математическая раскраска . Springer. ISBN 978-0-387-74640-1.
^ ab Erdős, P.; Simonovits, M. (1980). «О хроматическом числе геометрических графов». Ars Combinatoria . 9 : 229–246 . CiteSeerX 10.1.1.210.6641 . Zbl 0466.05031.
^ Шефер, Маркус (2013), «Реализуемость графов и связей», в Pach, János (ред.), Thirty Essays on Geometric Graph Theory , Springer, стр. 461–482 , CiteSeerX 10.1.1.220.9651 , doi :10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.

[1] Некоторые математики рассматривают это строго как « погружение », но многие специалисты по теории графов, включая Эрдёша, Харари и Тутте, используют термин « вложение ».

[2] Эрдеш, П.; Харари, Ф.; Тутте, WT (1965). «О размерности графа» (PDF) . Математика . 12 (2): 118– 122. doi : 10.1112/s0025579300005222. hdl : 2027.42/152495 .

[3] Каванг, Райан. «Исследования размерности графов» (PDF) . Получено 16 августа 2018 г.

[4] Сойфер, Александр (2009). Математическая раскраска . Springer. ISBN 978-0-387-74640-1.

[esi-5] Erdős, P.; Simonovits, M. (1980). «О хроматическом числе геометрических графов». Ars Combinatoria . 9 : 229–246 . CiteSeerX 10.1.1.210.6641 . Zbl 0466.05031.

[6] Шефер, Маркус (2013), «Реализуемость графов и связей», в Pach, János (ред.), Thirty Essays on Geometric Graph Theory , Springer, стр. 461–482 , CiteSeerX 10.1.1.220.9651 , doi :10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.