Нaйдите нaименьшее n, для кoтoрoгo любoй прoстoй кoнечный плaнaрный грaф мoжнo былo oриентировать тaк чтo бы пoлустепень выхoду кaждoй с йегo вершин не превoсходилo n. Пoлустепень выхoда этo количествo "стрелoк" кoтoрые выхoдят с этoй вершины.

задан 21 Окт '13 15:39

10|600 символов нужно символов осталось
0

Ответом является $%n=3$%.

Прежде всего, рассмотрим граф икосаэдра. Он удовлетворяет условиям задачи, и в нём 12 вершин и 30 рёбер. Поэтому не существует такой расстановки стрелок на рёбрах, при которой из каждой вершины выходило бы не более двух стрелок: рёбер в этом случае оказалось бы не более 24. Этот пример показывает, что $%n\ge3$%.

Теперь докажем, что $%n\le3$%. Это значит, что в любом конечном простом планарном графе можно расставить стрелки на рёбрах так, что из каждой вершины исходит не более трёх стрелок. Здесь нужно привлечь один достаточно стандартный вспомогательный факт, который доказывается при помощи формулы Эйлера для плоских графов, и он изложен во многих источниках. Я поэтому буду ссылаться на него как на известное утверждение, а если нужно, то могу потом напомнить его доказательство. (Судя по всему, этой части рассуждения всё равно не избежать, так как планарность где-то должна использоваться.)

Утверждение такое: в конечном простом плоском графе количество рёбер меньше утроенного количества вершин. Из этого факта можно вывести нужное нам утверждение, проводя индукцию по числу рёбер графа. Если рёбер вообще нет, то доказывать нечего. Если рёбра есть, то удалим одно ребро, идущее из $%u$% в $%v$%. Оставшийся граф можно по предположению индукции ориентировать так, что в нём из любой вершины исходит не более трёх стрелок.

Допустим, что из вершины $%u$% в оставшемся графе исходит менее трёх стрелок. Тогда добавим стрелку, идущую из $%u$% в $%v$%, получая требуемое. Пусть теперь из $%u$% уже исходят три стрелки. Рассмотрим такое множество вершин $%V'$%, в которые можно добраться из вершины $%u$%, идя по направлениям стрелок. Это множество вершин определяет подграф, в котором все стрелки, выходящие из вершин множества $%V'$%, в пределах этого же множества и оканчиваются. К данному подграфу (он удовлетворяет всем условиям) применим тот факт, на который мы выше ссылались: число рёбер в нём меньше $%3|V'|$%. Это значит, что в подграфе имеется вершина $%w$%, из которой выходит менее трёх стрелок. Рассмотрим тогда кратчайший путь из $%u$% в $%w$% по стрелкам, и изменим одновременно направление всех этих стрелок. Для промежуточных вершин все значения останутся прежними. Для вершины $%w$% количество исходящих стрелок станет больше на единицу, но оно было меньше трёх, поэтому станет не больше трёх. А для вершины $%u$% число исходящих рёбер на единицу уменьшается, после чего можно добавить стрелку из $%u$% в $%v$%.

ссылка

отвечен 21 Окт '13 20:51

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

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

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

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

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

отмечен:

×338

задан
21 Окт '13 15:39

показан
671 раз

обновлен
21 Окт '13 20:51

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

по почте:

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

по RSS:

Ответы

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

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