Вложимость графов в поверхность

[gogoshik]

Помогите, плиз, разобраться.

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

Читаю в одной работе:

Цитата:

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

Почему это верно?

[vpb]

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

[Munin]

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

[gogoshik]

vpb в сообщении #1435022 писал(а):

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

Рассуждая тривиально, к такому утверждению можно прийти следующим образом. Рассмотрим плоскость или сферу и предположим, что любой граф вложим в неё. Однако это не так. Например, графы $K_5$ и $K_{3,3}$ не планарны. Поэтому семейство графов вложимых в плоскость или сферу не бесконечно, то есть ограничено.

[Munin]

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

[gogoshik]

Munin в сообщении #1435047 писал(а):

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

Это не верно. Если, например, в графе $K_3$ заменить любую вершину на планарный (конечный) подграф, то получится нечто другое. Но $K_3$ будет не планарный. Поэтому в числе всех возможных графов (их число бесконечно) существуют графы, которые не планарны. То есть не любой граф планарен и следовательно множество планарных графов ограничено в этом смысле. Других каких-то осмысленных интерпретаций фразы:

Цитата:

При этом для поверхности фиксированного рода семейство графов, вложимых в неё, ограничено.

я не придумал.

[arseniiv]

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

[gogoshik]

arseniiv в сообщении #1435122 писал(а):

А откуда она?

Из рецензии. Рецензент -- ведущий научный сотрудник Стекловки.

[vpb]

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

[gogoshik]

vpb
Неужто вы думаете иначе?

[Sender]

gogoshik в сообщении #1435103 писал(а):

То есть не любой граф планарен и следовательно множество планарных графов ограничено в этом смысле. Других каких-то осмысленных интерпретаций фразы:

Цитата:

При этом для поверхности фиксированного рода семейство графов, вложимых в неё, ограничено.

я не придумал.

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

[vpb]

gogoshik в сообщении #1435127 писал(а):

Неужто вы думаете иначе?

Нет, конечно.

[mihaild]

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

[vpb]

vpb в сообщении #1435130 писал(а):

Нет, конечно.

Поясним, на всякий случай. Вы сделали такое утверждение

gogoshik в сообщении #1435046 писал(а):

Поэтому семейство графов вложимых в плоскость или сферу не бесконечно,

вот я и хотел намекнуть, что это, скажем так, не так.

[Munin]

gogoshik в сообщении #1435103 писал(а):

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

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

gogoshik в сообщении #1435103 писал(а):

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

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

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

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