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

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

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

Размерности графа $G$ написано: . ${\ displaystyle \ dim G}$

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

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

Примеры [ править ]

С 4 равноотстоящими точками нам нужно 3 измерения.

Полный график [ править ]

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

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

{\ Displaystyle \ тусклый K_ {п} = п-1}

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

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

{\ displaystyle K_ {4,2}}

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

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

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

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

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

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

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

Обозначая координаты 4-пространства , мы располагаем один набор вершин произвольно на окружности, заданной как where , а другой набор произвольно на окружности . Затем мы видим, что расстояние между любой вершиной в одном наборе и любой вершиной в другом наборе равно . ${\ displaystyle w, x, y, z}$ $w^{2}+x^{2}=a,y=0,z=0$ $0<a<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: $K_{3,3}$

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

Чтобы подвести итог:

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

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

m

и

n

.

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

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

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

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

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

Мы пишем $п$ хроматического числа $G$ и присвоить целые числа в $п$ цветов. В -мерном евклидовом пространстве с обозначенными его размерами мы расположим все вершины цвета $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 {Edim} G$

\dim G\leq \operatorname {Edim} G

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

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

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

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

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

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

Ссылки [ править ]

^ Некоторые математики расценивают это строго как « погружение », но многие теоретики графов, в том числе Эрдеш, Харари и Тутте, используют термин « вложение ».
^ Erdős, P .; Harary, F .; Тутте, WT (1965). «О размерности графа» (PDF) . Математика . 12 (2): 118–122. DOI : 10.1112 / s0025579300005222 .
^ Каванг, Райан. «Исследования размерности графиков» (PDF) . Проверено 16 августа 2018 года .
^ Сойфер, Александр (2009). Математическая книжка-раскраска . Springer. ISBN 978-0-387-74640-1.
^ a b Erdős, P .; Симоновиц, М. (1980). «О хроматическом числе геометрических графов». Ars Comb. (9): 229–246.
↑ Schaefer, Marcus (2013), «Реализуемость графов и связей», в Pach, János (ed.), Thirty Essays on Geometric Graph Theory , Springer, pp. 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] Erdős, P .; Harary, F .; Тутте, WT (1965). «О размерности графа» (PDF) . Математика . 12 (2): 118–122. DOI : 10.1112 / s0025579300005222 .

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

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

[esi-5] Erdős, P .; Симоновиц, М. (1980). «О хроматическом числе геометрических графов». Ars Comb. (9): 229–246.

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

[1]