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

В математике , и особенно в теории графов , размерность графа — это наименьшее целое число n , такое, что существует «классическое представление» графа в евклидовом пространстве размерности n, где все ребра имеют единичную длину.
В классическом представлении вершины должны быть различными точками, но ребра могут пересекать друг друга. [ 1 ]
Размерность графа G записывается .
Например, граф Петерсена можно нарисовать с единичными ребрами в , но не в : следовательно, его размерность равна 2 (см. рисунок справа).
Эта концепция была введена в 1965 году Полом Эрдешем , Фрэнком Харари и Уильямом Таттом . [ 2 ] Он обобщает концепцию графа единичных расстояний на более чем два измерения.
Примеры
[ редактировать ]
Полный график
[ редактировать ]В худшем случае каждая пара вершин связана, образуя полный граф .
Чтобы погрузить полный график поскольку все ребра имеют единичную длину, нам нужно евклидово пространство размерности . [ 3 ] Например, для погружения требуется два измерения. (равносторонний треугольник) и три для погружения (правильный тетраэдр), как показано справа.
Другими словами, размерность полного графа такая же, как и размерность симплекса с тем же числом вершин.

Полные двудольные графы
[ редактировать ]
Все звездные графики , для , имеют размерность 2, как показано на рисунке слева. Звездчатым графам с m, равным 1 или 2, требуется только измерение 1.
Размерность полного двудольного графа , для , можно нарисовать, как показано на рисунке справа, поместив m вершин на круг, радиус которого меньше единицы, а две другие вершины — по одной с каждой стороны плоскости круга, на подходящем расстоянии от нее. имеет размерность 2, так как его можно изобразить на плоскости как единичный ромб.
Теорема . Размерность общего полного двудольного графа. , для и , равно 4. Доказательство |
Подводя итог:
- , в зависимости от значений m и n .
Размер и хроматическое число
[ редактировать ]Теорема . Размерность любого графа G всегда меньше или равна удвоенному его хроматическому числу :
Евклидово измерение
[ редактировать ]

Определение размерности графа, данное выше, говорит о минимальном представлении n :
- если две вершины графа G соединены ребром, они должны находиться на расстоянии единицы друг от друга;
- однако две вершины, находящиеся на единичном расстоянии друг от друга, не обязательно соединены ребром.
Это определение отвергается некоторыми авторами. Другое определение было предложено в 1991 году Александром Сойфером для того, что он назвал евклидовым измерением графа. [ 4 ] Ранее, в 1980 году, Пауль Эрдеш и Миклош Симоновиц уже предлагали его под названием « Верное измерение» . [ 5 ] По этому определению минимальное представление — это такое, в котором две вершины графа соединены тогда и только тогда, когда их представления находятся на расстоянии 1.
На рисунках напротив показана разница между этими определениями в случае графа-колеса, имеющего центральную вершину и шесть периферийных вершин с удаленной одной спицей. Его представление на плоскости допускает две вершины на расстоянии 1, но они не связаны.
Мы запишем это измерение как . Он никогда не может быть меньше размера, определенного выше:
Евклидова размерность и максимальная степень
[ редактировать ]Пауль Эрдеш и Миклош Симоновиц доказали в 1980 году следующий результат: [ 5 ]
Теорема . Евклидова размерность графа G не более чем в два раза превышает его максимальную степень плюс один:
Вычислительная сложность
[ редактировать ]NP -трудно , а точнее, полно для экзистенциальной теории реальных чисел , проверить, является ли размерность или евклидова размерность данного графа не более чем заданным значением. Проблема остается сложной даже для проверки того, равна ли размерность или евклидова размерность двум. [ 6 ]
Ссылки
[ редактировать ]- ^ Некоторые математики рассматривают это строго как « погружение », но многие теоретики графов, в том числе Эрдеш, Харари и Тутте, используют термин « вложение ».
- ^ Эрдеш, П.; Харари, Ф.; Тутте, WT (1965). «О размерности графа» (PDF) . Математика . 12 (2): 118–122. дои : 10.1112/s0025579300005222 . hdl : 2027.42/152495 .
- ^ Каванг, Райан. «Исследования размерности графов» (PDF) . Проверено 16 августа 2018 г.
- ^ Сойфер, Александр (2009). Математическая раскраска . Спрингер. ISBN 978-0-387-74640-1 .
- ^ Jump up to: а б Эрдеш, П.; Симоновиц, М. (1980). «О хроматическом числе геометрических графов». Арс Комбинатория . 9 : 229–246. CiteSeerX 10.1.1.210.6641 . Збл 0466.05031 .
- ^ Шефер, Маркус (2013), «Реализуемость графов и связей», в Пач, Янош (ред.), « Тридцать эссе по геометрической теории графов » , Springer, стр. 461–482, CiteSeerX 10.1.1.220.9651 , doi : 10.1007/978-1-4614-0110-0_24 , ISBN 978-1-4614-0109-4 .