В полном двудольном графе nXm построен наибольший эйлеров цикл. Сколько ребер он содержит?

задан 12 Янв 23:37

Формулировку желательно сделать более корректной. Эйлеров цикл должен содержать все рёбра графа. Значит, если речь о полном двудольном, то в нём эйлеров цикл имеется тогда и только тогда, когда m,n чётны. Если это не так, то речь должна идти о наибольшем (по длине) эйлеровом цикле в подграфе.

(12 Янв 23:55) falcao

Положим, граф полный двудольный, n, m - четные. Тогда сколько ребер содержит эйлеров цикл? полагаю, что n * m.

(12 Янв 23:57) log0

@log0: этот-то случай как раз очевиден -- степени всех вершин чётны, эйлеров цикл существует, а число рёбре графа равно mn. В задаче, наверное, не только этот случай имелось в виду рассматривать, только надо формулировку чуть подкорректировать.

(13 Янв 0:10) falcao

к сожалению, перед глазами вижу лист бумаги и там в точности такая. Увы. А каков будет наибольший цикл в подграфе для нечетных m, n? А если один из параметров - четный?

(13 Янв 0:22) log0
10|600 символов нужно символов осталось
1

Давайте рассмотрим тогда скорректированную версию задачи. Пусть m<=n. Тогда в каждую вершину меньшей доли мы заходим в цикле не более [m/2] раз. Поскольку всего там m вершин, общее число упоминаний вершин этой доли не больше m[m/2]. Вершины той и другой доли чередуются, и столько же раз упоминаются вершины второй доли. Итого не более 2m[m/2] упоминаний вершин, а это и есть длина цикла.

Проверим, что указанное значение достигается для некоторого подграфа. Оставим сначала подграф K(m,m). Если m чётно, но он эйлеров, и там есть эйлеров цикл из m^2 рёбер, что совпадает с 2m[m/2]. Если m нечётно, то рассмотрим произвольное совершенное паросочетание вершин той и другой доли, и удалим его. Останется граф с m(m-1) рёбрами. При m > 1 он связен (это легко проверяется), поэтому эйлеров. Получается эйлеров цикл в подграфе из m(m-1) рёбер, что также совпадает с величиной 2m[m/2].

ссылка

отвечен 13 Янв 10:46

Тогда в каждую вершину меньшей доли мы заходим в цикле не более [m/2] раз

Точно ли не более $%m/2$%? Не $%n/2$%?

(14 Янв 21:12) log0

@log0: да, Вы правы. Оценку я в итоге занизил. Постараюсь в ближайшее время исправить рассуждение.

(15 Янв 0:44) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,036
×950
×129

задан
12 Янв 23:37

показан
223 раза

обновлен
15 Янв 0:44

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

по почте:

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

по RSS:

Ответы

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

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