2014 dxdy logo

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

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




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

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

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

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

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

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

 
 
 
 Re: Вложимость графов в поверхность
Сообщение13.01.2020, 22:04 
Аватара пользователя
Если "ограничено" значит "конечно", то это не так. Любую вершину графа, например, можно заменить на планарный (конечный) подграф, а их число бесконечно.

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

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

 
 
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 13:26 
arseniiv в сообщении #1435122 писал(а):
А откуда она?
Из рецензии. Рецензент -- ведущий научный сотрудник Стекловки.

 
 
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 13:55 
gogoshik
А цепь из 100 вершин (а еще лучше --- 100 отдельных вершин) в плоскость вложить можно ?

 
 
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:06 
vpb
Неужто вы думаете иначе?

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

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

 
 
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:25 
gogoshik в сообщении #1435127 писал(а):
Неужто вы думаете иначе?
Нет, конечно.

 
 
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 14:40 
Аватара пользователя
Может быть где-то в работе или в рецензии вводится какая-то структура, позволяющая говорить об ограниченности? Просто придумать причину, зачем без такой кто-то мог бы использовать слово "ограничено" в каком-то нестандартном смысле вместо того чтобы написать "для любой поверхности существует не вложимый в неё граф" (или что-то подобное), я не могу.

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

 
 
 
 Re: Вложимость графов в поверхность
Сообщение14.01.2020, 17:02 
Аватара пользователя
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