Как нарисовать плоский граф, у которого всякая вершина имеет степень 5?

2 дня изрисовываю тетрадь и ничего не выходит, наверное я глупый и делаю что-то не так, прошу помощи у более смышленых. )
Тут вообще есть какой-то "логически-обоснованный" алгоритм?

задан 11 Май '15 22:15

изменен 11 Май '15 22:18

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


9917

Это граф икосаэдра. Он планарен, то есть реализуется в виде плоского графа.

(11 Май '15 22:24) falcao

Спасибо. А он единственный? Посмотрел на картинку, не понимаю как до такого можно додуматься самому. Именно в таком порядке, заметить что он может быть планарен ИМХО несложно. Если воспринимать мой вопрос именно как задачу, то каким могло бы быть решение?

(11 Май '15 23:36) sapere aude

@sapere aude, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

(12 Май '15 7:57) Виталина
10|600 символов нужно символов осталось
1

Такой граф не единственный даже среди связных. Нарисуем две плоских копии графа икосаэдра, и сблизим два ребра у одной и другой из них. Пусть ребро a-b идёт параллельно ребру c-d. Тогда сотрём эти рёбра и вместо них проведём соединения a-c, b-d. Так можно делать несколько раз, получая всё более сложные рисунки.

Граф икосаэдра -- это "наименьший" граф с данным свойством. Действительно, если в графе $%n$% вершин, то рёбер будет $%5n/2$%, где $%n$% чётно. Если нарисовать граф на сфере, то по формуле Эйлера число граней будет равно $%F=2-V+E=2-n+5n/2=2+3n/2$%. Поскольку граф простой (в противном случае можно обеспечить какие угодно степени вершин), все грани являются как минимум треугольными. Выделяя в каждой из них по три ребра, а также с учётом того, что ребро является общим для двух граней, выводим отсюда, что $%3F\le2E$%. Тогда $%2+3n/2\le5n/3$%, то есть $%n\ge12$%. Равенство имеет место, если все грани треугольные, и при этом $%F=20$%, то есть это граф икосаэдра.

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

Вообще, здесь сам граф рисуется сравнительно просто, даже если не знать. Надо начать с точки, вывести из неё симметрично 5 рёбер. Потом дорисовать треугольники, далее выводя наружу недостающее число рёбер и определённым образом их соединяя.

ссылка

отвечен 12 Май '15 3:38

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,015
×379

задан
11 Май '15 22:15

показан
373 раза

обновлен
12 Май '15 7:57

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

по почте:

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

по RSS:

Ответы

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

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