В полном графе часть рёбер покрасили в красный цвет, а остальные - в синий. Рассмотрим два графа: один состоящий из всех красных рёбер, а второй из синих. а) Докажите, что хотя бы один из этих графов связен. б) Докажите, что для каждой вершины можно выбрать такой цвет, что от неё до любой другой минимальное расстояние по этому цвету будет меньше 3.

задан 4 Дек 14:45

изменен 5 Дек 12:00

%D0%9A%D0%B0%D0%B7%D0%B2%D0%B5%D1%80%D1%82%D0%B5%D0%BD%D0%BE%D1%87%D0%BA%D0%B0's gravatar image


2.6k210

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

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

Итак, докажем б). Возьмём любую вершину v. Она соединена синими рёбрами с вершинами из A, и красными с вершинами из B (пустые множества допускаем). Допустим, что синий цвет для данной вершины не подходит. Тогда найдётся вершина w, которой нельзя достичь из v по синим рёбрам за 1 или 2 шага. Ясно, что w взята из B, и она не соединена синим цветом ни с какой вершиной из A. Тогда она соединена красным цветом со всеми вершинами из A. Получается, что красный цвет для v подходит: до вершин из B добираемся за один 1 шаг, до вершин из A -- за 2 (через w).

ссылка

отвечен 5 Дек 3:35

@falcao, "Утверждение легко доказать индукцией по числу вершин." .................... Простите за тупейший вопрос, а с какого числа начинать? Ведь в графе может быть и 0 вершин. Может ли пустой граф быть полным (извините за каламбур)?

(5 Дек 11:34) Казвертеночка
1

@Казвертеночка: понятие полного графа $%K_n$% определяется для значений $%n\ge1$% -- см., например, Уилсон, "Введение в теорию графов". Даже если для чего-то считать удобным понятие пустого графа, то он будет связен (любые две точки соединены путём -- это верно, так как нет контрпримера). Поэтому при $%n=0$% утверждение окажется тривиальным. Но здесь этого всего явно допускать не надо.

(5 Дек 11:43) falcao

@falcao, теперь всё прояснилось, большое спасибо!

(5 Дек 11:46) Казвертеночка
1

@falcao, "... это верно, так как нет контрпримера" ................... Очень важный момент, между прочим. Многие школьники на нём спотыкаются, поскольку для них он контринтуитивен. Как говорила товарищ Раскина, умение отличать решенную задачу от нерешенной – основа математической культуры. Можно обобщить её высказывание: Умение отличать решенную проблему от нерешенной – основа человеческой культуры.

(5 Дек 12:11) Казвертеночка

@Казвертеночка: да, мне это явление очень знакомо. Если спросить "среднего" студента, верно ли, что все элементы пустого множества являются серо-буро-малиновыми сусликами, то он не будет знать правильного ответа :)

(5 Дек 14:05) falcao

@falcao, верно ли, что A - граф с синими рёбрами и B - граф с красными рёбрами? Если да, то почему "w взята из B, и она не соединена синим цветом ни с какой вершиной из A"? Не могут ли v и w быть в разных компонентах связности графа A?

(11 Дек 21:14) Igore

@Igore: нет, A и B -- это не графы, а всего лишь множества вершин. У нас зафиксирована v, и все остальные вершины относим к одному из этих множеств в зависимости от цвета их соединения с v. Утверждение про w следует из того, что она по предположению не соединена с v путём длиной 1 или 2.

(12 Дек 0:28) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×838
×413
×72
×1

задан
4 Дек 14:45

показан
66 раз

обновлен
12 Дек 0:28

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

по почте:

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

по RSS:

Ответы

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

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