2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вложение конечного графа в евклидово пространство
Сообщение16.11.2018, 22:25 
Элементарно вложить граф с $n$ вершинами в $n$-мерное евклидово пространство, чтобы его автоморфизмы были автоморфизмами пространства, оставляющими образ графа на месте (каждую вершину перевести в вектор заданного базиса, каждое ребро в отрезок). Однако если мы выкинем из полученной фигуры все отрезки, мы потеряем всю информацию о графе, группа симметрий станет $S_n$. Можно ли вложить граф получше — найти в некотором пространстве такое множество $n$ точек, что группа его симметрий будет изоморфна группе автоморфизмов графа, а точки при этом будут соответствовать вершинам?

Тут наверно тоже всё легко, но я не подумал ещё.

 
 
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение17.11.2018, 15:57 
Аватара пользователя
Для каждой вершины $i$ запишем вектор расстояний по графу от нее до всех остальных $(d_{i,1}, d_{i,2}, \ldots, d_{i, n})$. Теперь отправляем вершину $i$ в вектор $(\sqrt{d_{i, 1}}, \ldots, \sqrt{d_{i, n}})$. Тогда по скалярным произведениям однозначно восстанавливаются ребра - и, соответственно, автоморфизмы графа это в точности изометрии, оставляющие $S$ на месте.

 
 
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение18.11.2018, 04:16 
Спасибо, прекрасно! :appl:

 
 
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение19.11.2018, 23:44 
Аватара пользователя
arseniiv, зря аплодируете, я вас, кажется, обманул. По крайней мере доказать, что мой способ работает, я не могу.
Но можно так: ребра - это базисные вектора (попарно ортогональные), вектор вершины - сумма векторов инцидентных ей ребер. Тогда вершины ортогональны тогда и только тогда, когда они не смежны.

 
 
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение20.11.2018, 00:19 
Аватара пользователя
mihaild в сообщении #1354743 писал(а):
Теперь отправляем вершину $i$ в вектор

А зачем корни брать здесь?

И ведь размерность $n$...

 
 
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение20.11.2018, 02:17 
Аватара пользователя
Меньшую размерность не просили:) И скажем полный граф на $n$ вершинах меньше чем в $\mathbb{R}^{n - 1}$ вложить не получится.
Корни брать затем что я писал одно, думал про другое, а надо было третье... :facepalm:

 
 
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение20.11.2018, 04:36 
mihaild в сообщении #1355313 писал(а):
По крайней мере доказать, что мой способ работает, я не могу.
Хм, я тогда сначала в одну сторону не понял (что любой автоморфизм реализуется), а потом как будто понял. Про необязательность корней тоже увидел.

Подумаю когда посплю с выписыванием над новым и над старым тоже, чтобы удостовериться. :-)

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group