В графе каждая вершина имеет степень 3. Всегда ли можно выбрать в нем несколько ребер так, чтобы в каждую его вершину входило ровно одно выбранное ребро?

задан 29 Окт '18 16:39

изменен 2 Ноя '18 13:59

%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


9.1k335

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

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

Для многих графов (типа тетраэдра, куба, додекаэдра) ответ положительный. Один из "старейших" результатов в теории графов -- теорема Петерсена, полученная ещё в XIX веке. Она даёт достаточное условие возможности такого разбиения.

Но в общем случае ответ отрицательный. Минимальный пример имеет 16 вершин. Строится он так: одна вершина графа находится в центре; пусть это O. Она соединена тремя отрезками с A1, A2, A3. Конструкция переходит в себя при повороте на 120 градусов.

Для каждой из вершин A=Ai строим пятиугольник ABCDE (все буквы -- с одинаковыми индексами), где все стороны -- рёбра графа. Добавляем две диагонали BD и CE.

Теперь все вершины имеют степень 3. Разбиение на пары невозможно. Действительно, O соединена с какой-то одной вершиной -- скажем, A1. Тогда ни с A2, ни с A3 она не соединена. В итоге возникает пятиугольник, который больше ни с чем не связан, и его вершины на пары не разбить по причине нечётности их числа.

ссылка

отвечен 29 Окт '18 17:23

3
(29 Окт '18 17:44) knop
1

@falcao, @knop, спасибо!

(30 Окт '18 15:49) make78

@falcao, "Минимальный пример имеет 16 вершин." ............ Почему именно 16? Как это доказать?

(2 Ноя '18 14:01) Казвертеночка
1

@Казвертеночка: перебор + достаточные условия (типа теоремы Петерсена).

(2 Ноя '18 14:40) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×640
×115
×27

задан
29 Окт '18 16:39

показан
1039 раз

обновлен
2 Ноя '18 14:40

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

по почте:

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

по RSS:

Ответы

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

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