2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Вложение конечного графа в евклидово пространство
Сообщение16.11.2018, 22:25 
Заслуженный участник


27/04/09
28128
Элементарно вложить граф с $n$ вершинами в $n$-мерное евклидово пространство, чтобы его автоморфизмы были автоморфизмами пространства, оставляющими образ графа на месте (каждую вершину перевести в вектор заданного базиса, каждое ребро в отрезок). Однако если мы выкинем из полученной фигуры все отрезки, мы потеряем всю информацию о графе, группа симметрий станет $S_n$. Можно ли вложить граф получше — найти в некотором пространстве такое множество $n$ точек, что группа его симметрий будет изоморфна группе автоморфизмов графа, а точки при этом будут соответствовать вершинам?

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

 Профиль  
                  
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение17.11.2018, 15:57 
Заслуженный участник
Аватара пользователя


16/07/14
8342
Цюрих
Для каждой вершины $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 
Заслуженный участник


27/04/09
28128
Спасибо, прекрасно! :appl:

 Профиль  
                  
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение19.11.2018, 23:44 
Заслуженный участник
Аватара пользователя


16/07/14
8342
Цюрих
arseniiv, зря аплодируете, я вас, кажется, обманул. По крайней мере доказать, что мой способ работает, я не могу.
Но можно так: ребра - это базисные вектора (попарно ортогональные), вектор вершины - сумма векторов инцидентных ей ребер. Тогда вершины ортогональны тогда и только тогда, когда они не смежны.

 Профиль  
                  
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение20.11.2018, 00:19 
Заслуженный участник
Аватара пользователя


01/09/13
4318
mihaild в сообщении #1354743 писал(а):
Теперь отправляем вершину $i$ в вектор

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

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

 Профиль  
                  
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение20.11.2018, 02:17 
Заслуженный участник
Аватара пользователя


16/07/14
8342
Цюрих
Меньшую размерность не просили:) И скажем полный граф на $n$ вершинах меньше чем в $\mathbb{R}^{n - 1}$ вложить не получится.
Корни брать затем что я писал одно, думал про другое, а надо было третье... :facepalm:

 Профиль  
                  
 
 Re: Вложение конечного графа в евклидово пространство
Сообщение20.11.2018, 04:36 
Заслуженный участник


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gevin Magnus, Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group