Jump to content

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

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

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

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

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

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

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

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

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

[ редактировать ]

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

Чтобы погрузить полный график поскольку все ребра имеют единичную длину, нам нужно евклидово пространство размерности . [ 3 ] Например, для погружения требуется два измерения. (равносторонний треугольник) и три для погружения (правильный тетраэдр), как показано справа.

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

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

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

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

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

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

Теорема . Размерность общего полного двудольного графа. , для и , равно 4.

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

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

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

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

[ редактировать ]

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

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

Евклидово измерение

[ редактировать ]
Граф колеса с удаленной одной спицей имеет размерность 2.
Это же колесо имеет евклидову размерность 3.

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

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

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

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

Мы запишем это измерение как . Он никогда не может быть меньше размера, определенного выше:

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

[ редактировать ]

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

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

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

[ редактировать ]

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

  1. ^ Некоторые математики рассматривают это строго как « погружение », но многие теоретики графов, в том числе Эрдеш, Харари и Тутте, используют термин « вложение ».
  2. ^ Эрдеш, П.; Харари, Ф.; Тутте, WT (1965). «О размерности графа» (PDF) . Математика . 12 (2): 118–122. дои : 10.1112/s0025579300005222 . hdl : 2027.42/152495 .
  3. ^ Каванг, Райан. «Исследования размерности графов» (PDF) . Проверено 16 августа 2018 г.
  4. ^ Сойфер, Александр (2009). Математическая раскраска . Спрингер. ISBN  978-0-387-74640-1 .
  5. ^ Jump up to: а б Эрдеш, П.; Симоновиц, М. (1980). «О хроматическом числе геометрических графов». Арс Комбинатория . 9 : 229–246. CiteSeerX   10.1.1.210.6641 . Збл   0466.05031 .
  6. ^ Шефер, Маркус (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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 9f16ea013ced4cc3ab9f07a27c5a391d__1691983140
URL1:https://arc.ask3.ru/arc/aa/9f/1d/9f16ea013ced4cc3ab9f07a27c5a391d.html
Заголовок, (Title) документа по адресу, URL1:
Dimension (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)