У выпуклого многогранника $%2n$% граней ($%n$% не меньше 3), и все грани являются треугольниками. Какое наибольшее число вершин, в которых сходится ровно 3 ребра, может быть у такого многогранника?

Есть такой вопрос - есть какие-то правила для изображения графа выпуклого многогранника на плоскости? И вообще, тут можно как-то перейти к чисто теоретико-графовой задачи (воображения не хватает для больших $%N$%).

задан 16 Июн '15 5:31

изменен 24 Июн '15 21:09

Несложно получить оценку - количество искомых вершин не больше, чем $$2n/3,$$ иначе n = 2, и мы имеем тетраедр, что противоречит условию.

Вопрос в том, как построить пример (желательно на графовом языке).

(19 Июн '15 2:03) sapere aude

У меня есть некоторые соображения по этой задаче, но они пока что неполные. Изображать многогранник на плоскости можно в виде стереографической проекции. В данной задаче можно просто рисовать большой треугольник, и разбивать его на маленькие, выбирая одну из граней, точку внутри неё, и соединяя её с вершинами. Внешняя грань при этом как бы находится сверху, а всё остальное -- плоское.

Для небольших чисел я знаю ответ, и он равен $%[2n/3]$%. Скорее всего, это так и есть в общем случае.

(25 Июн '15 4:02) falcao
10|600 символов нужно символов осталось
0

Не совсем ответ, просто кое-какие рассуждения по последнему комментарию:

Только что узнал, что такое стереографическая проекция, стыд и позор мне, но если я все правильно понял, то, по сути, тут 2 утверждения есть: из любого планарного графа можно сделать многогранник, и обратное. Мы используем первое для решения задачи.
Разбивать большой треугольник на маленькие это равносильно добавлению новой вершин многогранника к какой-то грани, то есть, по сути, присоединению тетраеда к какой-то обязательно треугольник грани. Вопрос только в том, а сохранится ли выпуклость при этом? Это не всегда верно же, но мы строим пример, а поэтому если хотя бы когда-то верно, то все хорошо. Можно продолжить соседние грани и получить замкнутное пространство над треугольной гранью, внутри него из соображений здравого смысла (ну или как-то построже через выпуклость?) можно взять точку и все будет хорошо.

ссылка

отвечен 25 Июн '15 8:13

изменен 25 Июн '15 21:37

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

@sapere aude: если нам просто дан какой-то планарный граф (например, дерево), то мы из него многогранник прямо не сделаем, но можно дорисовать какие-то рёбра, и тогда многогранник получить будет можно. Кроме того, есть теорема (её разным авторам приписывают), что простой планарный граф всегда можно нарисовать так, чтобы рёбра были прямолинейными отрезками.

Разбиениям на треугольники соответствуют выпуклые многогранники, если к грани добавлять тетраэдр с очень маленькой высотой.

(25 Июн '15 13:06) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,526
×954
×131
×22

задан
16 Июн '15 5:31

показан
480 раз

обновлен
25 Июн '15 13:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru