2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Вложимость графов в поверхность
Сообщение13.01.2020, 18:17 


11/12/16
352
сБп
Помогите, плиз, разобраться.

Граф называется вложимым в поверхность, если его можно расположить (нарисовать) на этой поверхности так, что ребра не пересекаются.

Читаю в одной работе:
Цитата:
"Известно, что всякий граф вложим в некоторую поверхность. При этом для поверхности фиксированного рода семейство графов, вложимых в неё, ограничено."
Почему это верно?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение13.01.2020, 20:06 
Заслуженный участник


18/01/15
1966
В данном случае уместно спросить, а каковы ваши собственные попытки решения ?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение13.01.2020, 20:18 
Заслуженный участник
Аватара пользователя


30/01/06
72408
Извините за дилетантский вопрос, а что такое "ограничено"?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение13.01.2020, 21:55 


11/12/16
352
сБп
vpb в сообщении #1435022 писал(а):
В данном случае уместно спросить, а каковы ваши собственные попытки решения ?
Рассуждая тривиально, к такому утверждению можно прийти следующим образом. Рассмотрим плоскость или сферу и предположим, что любой граф вложим в неё. Однако это не так. Например, графы $K_5$ и $K_{3,3}$ не планарны. Поэтому семейство графов вложимых в плоскость или сферу не бесконечно, то есть ограничено.

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


30/01/06
72408
Если "ограничено" значит "конечно", то это не так. Любую вершину графа, например, можно заменить на планарный (конечный) подграф, а их число бесконечно.

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 09:54 


11/12/16
352
сБп
Munin в сообщении #1435047 писал(а):
Любую вершину графа, например, можно заменить на планарный (конечный) подграф, а их число бесконечно.
Это не верно. Если, например, в графе $K_3$ заменить любую вершину на планарный (конечный) подграф, то получится нечто другое. Но $K_3$ будет не планарный. Поэтому в числе всех возможных графов (их число бесконечно) существуют графы, которые не планарны. То есть не любой граф планарен и следовательно множество планарных графов ограничено в этом смысле. Других каких-то осмысленных интерпретаций фразы:
Цитата:
При этом для поверхности фиксированного рода семейство графов, вложимых в неё, ограничено.
я не придумал.

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 13:11 
Заслуженный участник
Аватара пользователя


27/04/09
27145
А откуда она? Вполне можно было бы тогда там написать «для поверхностей каждого рода найдутся не вложимые в них графы» и всё. :-) А ограниченность — это или метрика нужна, или порядок, или ещё что-то — на множестве всех графов есть разве какая-то подходящая структура?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 13:26 


11/12/16
352
сБп
arseniiv в сообщении #1435122 писал(а):
А откуда она?
Из рецензии. Рецензент -- ведущий научный сотрудник Стекловки.

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 13:55 
Заслуженный участник


18/01/15
1966
gogoshik
А цепь из 100 вершин (а еще лучше --- 100 отдельных вершин) в плоскость вложить можно ?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:06 


11/12/16
352
сБп
vpb
Неужто вы думаете иначе?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:20 


14/01/11
2331
gogoshik в сообщении #1435103 писал(а):
То есть не любой граф планарен и следовательно множество планарных графов ограничено в этом смысле. Других каких-то осмысленных интерпретаций фразы:
Цитата:
При этом для поверхности фиксированного рода семейство графов, вложимых в неё, ограничено.
я не придумал.

Возможно, тут имеется в виду конечность множества запрещённых миноров, характеризующего данное семейство графов?

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:25 
Заслуженный участник


18/01/15
1966
gogoshik в сообщении #1435127 писал(а):
Неужто вы думаете иначе?
Нет, конечно.

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:40 
Заслуженный участник
Аватара пользователя


16/07/14
4021
Москва
Может быть где-то в работе или в рецензии вводится какая-то структура, позволяющая говорить об ограниченности? Просто придумать причину, зачем без такой кто-то мог бы использовать слово "ограничено" в каком-то нестандартном смысле вместо того чтобы написать "для любой поверхности существует не вложимый в неё граф" (или что-то подобное), я не могу.

 Профиль  
                  
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 15:35 
Заслуженный участник


18/01/15
1966
vpb в сообщении #1435130 писал(а):
Нет, конечно.
Поясним, на всякий случай. Вы сделали такое утверждение
gogoshik в сообщении #1435046 писал(а):
Поэтому семейство графов вложимых в плоскость или сферу не бесконечно,
вот я и хотел намекнуть, что это, скажем так, не так.

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


30/01/06
72408
gogoshik в сообщении #1435103 писал(а):
Поэтому в числе всех возможных графов (их число бесконечно) существуют графы, которые не планарны. То есть не любой граф планарен

Я этого и не утверждал. А утверждал я иное.

gogoshik в сообщении #1435103 писал(а):
Это не верно. Если, например, в графе $K_3$ заменить любую вершину на планарный (конечный) подграф, то получится нечто другое. Но $K_3$ будет не планарный.

Однако если $K_3$ можно вложить в некую поверхность $S$ (например, как известно, его можно вложить в $T^2=S^1\times S^1$), то в неё же можно вложить и любой такой новый граф. Таким образом, для данной поверхности получаем бесконечную серию графов, которые в неё вложимы.

Более того, в любую поверхность вложимы как минимум все планарные графы сами по себе.

Так что, не получается интерпретировать "ограничено" как "конечно".

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

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



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

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


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

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