Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№116

Задача ММ116 навеяна обсуждением одной из последовательностей в OEIS.

Конкурсная задача ММ116 (10 баллов)

Сколько существует связных графов, таких что произведение степеней вершин равно: а) сумме степеней вершин;
б) сумме квадратов степеней вершин?

Решение

а) Приведу решение Юрия Вольвовского (впрочем, решения некоторых других участников, по сути идентичны).

Сначала докажем, что связный граф, у которого произведение степеней вершин не больше их суммы, является деревом.
Доказывается в два шага:
(1) если нет висячих вершин, то произведение равно как минимум 2n, а сумма никак не больше n(n-1), что невозможно.
(2) удаляя висячую вершину, мы уменьшаем сумму на 2, а произведение на 1 только в том случае, если граф является звездочкой (т. е. деревом с одной вершиной степени больше 1). В остальных случаях, произведение уменьшается как минимум на 2 и утверждение следует по индукции. Остается разобраться с деревьями.
Для начала заметим, что одновершинное дерево удовлетворяет условию.
Пусть теперь в дереве есть k вершин степени больше единицы. Произведение их степеней не меньше, чем (n-k)2k-1, что должно быть не больше, чем 2n-2. Это возможно только если k=2 или k=3.
При k=3 имеем 4(n-3) ≤ 2n-2, т.е.n ≤ 5. Но в дереве не менее двух висячих вершин, поэтому n=5 и граф - цепочка длины 4.
Если k=2, то сумма степеней этих двух вершин должна быть равна n. Пусть степень одной из двух узловых вершин равна s.
Получаем уравнение s(n-s)=2n-2. Оно имеет целые решения, только если n2 - 8n + 8 - полный квадрат, что возможно только при n=7. Тогда степени узловых вершин 3 и 4 и мы нашли еще один (и последний) требуемый граф: дерево со степенями вершин 1, 1, 1, 1, 1, 3, 4.

Ответ к пункту а): 3 графа.

б) Докажем, что множество требуемых графов бесконечно. Для этого укажем алгоритм построения бесконечной серии подходящих графов. Легко убедиться, что дерево, у которого 7 из 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4, удовлетворяет всем условиям пункта б). Это дерево (на самом деле таких деревьев 3, но для нас это не важно) будет открывать нашу серию. Положим x0=4, y0 = 4, xk = yk-1, yk = 3yk-1-xk-1-1. Легко убедиться (по индукции), что дерево, у которого три вершины, не являющиеся висячими, имеют степени 3, xk, yk при любом натуральном будет удовлетворять условиям пункта б).

Ответ к пункту б): бесконечно много графов.

Обсуждение

С первом пунктом участники в целом справились успешнее, чем со вторым. Основным недоостатком здесь была потеря одновершинного дерева. Учитывая вырожденность этого случая (его и деревом-то называть странно:)), я не снижал оценок за этот момент.

Очевидно, что построенная нами бесконечная серия графов, не исчерпывает всех графов, удовлетворяющих условиям пункта б). Каждое дерево с тремя узловыми вершинами, удовлетворяющее условиям пункта б) порождает серию, аналогичную описанной. Например, стартуя с дерева со степенями узловых вершин 4, 4, 12 положим x0=4,  y0 = 12,   xk = yk-1,  yk = 4yk-1-xk-1-1. Деревья со степенями узловых вершин (4, xk, yk) будут обладать требуемыми свойствами. В отличие от пункта a), графы из пункта б) не обязаны быть деревьями. Очевидным примером служит четырехзвенный цикл. Юрий Вольвовский указал красивый способ получать новые подходящие графы из любого графа, удовлетворяющего условию пункта б), а не только из деревьев с тремя узловыми вершинами. На любом ребре такого графа возьмем новую вершину (выражаясь аккуратнее, заменим ребро конструкцией ребро-вершина-ребро) и подвесим к ней еще x-4 вершины, где x - произведение степеней вершин исходного графа. Тривиально проверяется, что полученный граф будет подходящим.

Награды

За решение задачи ММ116 участникам начислены следующие призовые баллы:
Дмитрий Пашуткин и Юрий Вольвовский - по 10 баллов;
Сергей Половинкин - 9 баллов;
Эдвард Туркевич, Алексей Волошин и Анатолий Казмерчук - по 6 призовых баллов.

Эстетическая оценка задачи - 4.8 балла


 

 


Страница: [[marathon:problem_116]]

marathon/problem_116.txt · Последние изменения: 2019/05/30 21:15 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006