2014 dxdy logo

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

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


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


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



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


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

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

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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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

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


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

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


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

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


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

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


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

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

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

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

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

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

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

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



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

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


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

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