Различия

Здесь показаны различия между двумя версиями данной страницы.

--- marathon:problem_116 [2010/07/07 10:58]
127.0.0.1 внешнее изменение
+++ marathon:problem_116 [2019/05/30 21:15] (текущий)
letsko
@@ Строка 39: / Строка 39: @@
 б) Докажем, что множество требуемых графов бесконечно.
 Для этого укажем алгоритм построения бесконечной серии подходящих графов.
-Легко убедиться, что дерево, у которого 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4,
+Легко убедиться, что дерево, у которого 7 из 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4,
 удовлетворяет всем условиям пункта б).
 Это дерево (на самом деле таких деревьев 3, но для нас это не важно) будет открывать нашу серию.
-Положим x<sub>0</sub>=4, y<sub>0</sub> = 4, x<sub>k</sub> = y<sub>k-1</sub>, y<sub>k</sub> = 3y<sub>k-1</sub>-x<sub>k-1</sub>}-1.
+Положим x<sub>0</sub>=4, y<sub>0</sub> = 4, x<sub>k</sub> = y<sub>k-1</sub>, y<sub>k</sub> = 3y<sub>k-1</sub>-x<sub>k-1</sub>-1.
 Легко убедиться (по индукции), что дерево, у которого три вершины, не являющиеся висячими, имеют степени 3,
 x<sub>k</sub>, y<sub>k</sub> при любом натуральном будет удовлетворять условиям пункта б).
@@ Строка 56: / Строка 56: @@
 Каждое дерево с тремя узловыми вершинами, удовлетворяющее условиям пункта б) порождает серию, аналогичную описанной.
 Например, стартуя с дерева со степенями узловых вершин 4, 4, 12
-положим x<sub>0</sub>=4, \ y<sub>0</sub> = 12, \ \ x<sub>k</sub> = y<sub>k-1</sub>, \ y<sub>k</sub> = 4y<sub>k-1</sub>}-x<sub>k-1</sub>-1.
+положим x<sub>0</sub>=4, \ y<sub>0</sub> = 12, \ \ x<sub>k</sub> = y<sub>k-1</sub>, \ y<sub>k</sub> = 4y<sub>k-1</sub>-x<sub>k-1</sub>-1.
 Деревья со степенями узловых вершин (4, x<sub>k</sub>, y<sub>k</sub>) будут обладать требуемыми свойствами.
 В отличие от пункта a), графы из пункта б) не обязаны быть деревьями. Очевидным примером служит четырехзвенный цикл.