Граф, который можно правильно вложить в поверхность рода $%g$% и невозможно вложить в поверхность меньшего рода, называется графом рода $%g$%. Доказать, что род $%g(K_n)$% полного графа $%K_n$% удовлетворяет неравенству: $$g(K_n)\geq \frac{(n-3)(n-4)}{12}.$$

задан 30 Мар '16 9:00

1

Это хорошо известное неравенство. Оно доказывается с использованием обобщения формулы Эйлера на случай не только сферических графов, но и графов на поверхностях типа сфер с ручками. Доказательство можно найти, например, в книге Р.Уилсон, "Введение в теорию графов".

(30 Мар '16 9:34) falcao
(30 Мар '16 10:13) gus
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,324
×506
×272
×159
×48

задан
30 Мар '16 9:00

показан
422 раза

обновлен
30 Мар '16 10:13

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

по почте:

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

по RSS:

Ответы

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

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