2014 dxdy logo

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

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


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


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



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


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

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

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


16/07/14
3469
Москва
Для каждой вершины $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
26396
Спасибо, прекрасно! :appl:

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


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

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


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

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

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

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


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

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


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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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