2014 dxdy logo

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

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


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


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



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


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

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

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


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

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


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

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


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

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

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

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


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

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


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

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

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

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



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

Сейчас этот форум просматривают: Swarg


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

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