Задача по теории графов

[almayor]

Помогите пжл решить следующую задачу:

Цитата:

Дан граф без кратных рёбер и петель с 40 вершинами. Известно, что у любого ребра хотя бы одним из концов является вершина, из которой выходит не более 4 других рёбер. Какое наибольшее количество рёбер может быть в этом графе?

Мои (пространные) мысли: Можно представить данный граф как двудольный: в одной половине лежат вершины с кратностью равной 5, в другой – вершины с неограниченной кратностью.

Это работает, так как если во второй половине есть не менее 5 вершин, то мы можем удовлетворить кратности всех вершин в левой половине, не соединяя их друг с другом. В данном случае максимальное количество рёбер равно $35 \times 5 = 175$. Если же во второй половине менее 5 вершин, то рёбер будет очевидно меньше.

Буду очень благодарен любому совету!

[pik]

Для такого графа <Кол.рёбер>: 4 х 40+1

. 1 , 2 , 3 , .... 40
-O---O---O--...--O--
/|\ /|\ /|\ ... /|\

Если вершину( 2,3 ...39 ) связать с открытой вершиной, то количество не меняется.
Если добавить в связь с открытой вершиной ещё одну с тремя открытыми связями, то количество не меняется.
В остальных случаях <Кол.рёбер> будет уменьшаться.

[mihaild]

pik в сообщении #1526452 писал(а):

Можно представить данный граф как двудольный: в одной половине лежат вершины с кратностью равной 5, в другой – вершины с неограниченной кратностью.

Нельзя - никто не запрещает ребру соединять две вершины степени не больше 5.
Пусть у нас в графе $n$ вершин степени не больше 5, и у каждого ребра хотя бы одна вершина имеет степень не больше 5. Сколько максимум в графе может быть ребер? Какое простое условие на достижение этого максимума?

[vlad239]

Цитата:

Нельзя - никто не запрещает ребру соединять две вершины степени не больше 5.

Формально, конечно, никто не запрещает. Но можно порвать такое ребро и вместо этого соединить обе вершины с какой-нибудь другой вершиной (степени больше 5). Их степени не изменятся, а ребер станет больше.
Если одна из них уже соединена с этой другой вершиной, то ребер просто будет столько же.
Если же обе, да еще со всеми вершинами большой степени... Надо чуть доделать.

[kirilych]

Назовем "белыми" вершины степени не более 5, а их количество - Б.
Назовем "красными" вершины степени более 5, а их количество - К.
Нам хочется минимизировать Б.
Число ребер не превышает 5Б (ибо каждое ребро по условию приходит хотя бы в одну белую).
6К не больше, чем 5Б, отсюда красных вершин не более 18.
Значит, белых не менее 22, а всего ребер не более 110.

[mihaild]

kirilych в сообщении #1527096 писал(а):

Нам хочется минимизировать Б.
Число ребер не превышает 5Б

Так зачем же нам минимизировать Б, если оно ограничивает число ребер сверху?

[kirilych]

mihaild в сообщении #1527109 писал(а):

Так зачем же нам минимизировать Б, если оно ограничивает число ребер сверху?

Ну, красные вершины же большей степени, а нам хочется больше ребер, поэтому красных надо побольше )

Ребер же не 5Б, а не более 5Б. Когда белых слишком много, часть ребер придется проводить между ними, что невыгодно (мы такие ребра считаем дважды, а нам надо максимально приблизиться к чистому 5Б).
Если ребро соединяет две белые, нам выгодно, одну из них сделать красной. Поэтому ищем максимум красных.

[mihaild]

kirilych в сообщении #1527121 писал(а):

Когда белых слишком много, часть ребер придется проводить между ними, что невыгодно

Как заметил vlad239, мы можем заменить ребро между двумя белыми на два ребра между белыми и красными, если у нас еще остались красные, не связанные с этой парой вершин. В частности, если красных хотя бы 5 (решение ТС), то мы всегда так сможем сделать. Ну и решение ТС содержит больше белых вершин, чем ваше, и заодно и больше ребер.

[EUgeneUS]

almayor в сообщении #1526379 писал(а):

Это работает, так как если во второй половине есть не менее 5 вершин, то мы можем удовлетворить кратности всех вершин в левой половине, не соединяя их друг с другом. В данном случае максимальное количество рёбер равно $35 \times 5 = 175$. Если же во второй половине менее 5 вершин, то рёбер будет очевидно меньше.

Решение так-то верное. Но, имхо, требуют более строгого доказательства утверждения:
А) Вершин с неограниченной кратностью не более $5$. Это не сложно.
Б) Максимум количества вершин достинается при пяти вершинах неограниченной кратности. С учетом А) это тоже не сложно.

[vlad239]

Давайте я пройду своим путем до конца.
Сохраним терминологию - есть белые и красные вершины. Из белых выходит не более 5 ребер, из красных сколько угодно, но красные не соединены между собой. Будем улучшать конструкцию.
Если какая-то белая имеет степень меньше 5 и при этом не соединена с какой-то красной - соединим.
Если две белые соединены, но хоть одна из них не соединена с какой-то красной - уберем ребро между ними и проведем ребро из белой в красную.
Разберем два случая.
Если красных не более 5 - то все белые соединены со всеми красными. Если красных всего x, то будет не более $(40-x)\cdot x+\frac12(40-x)(5-x)=\frac12(40-x)(5+x)$ ребер, что максимально при $x=5$ и дает $\frac12\cdot 35\cdot 10=175$
Если красных более 5 - то белые соединены только с красными, тогда ребер не более $5(40-x)\le 5\cdot 35=175$.