Главная страница

Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В


Скачать 3.28 Mb.
НазваниеУчебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
Дата16.10.2022
Размер3.28 Mb.
Формат файлаpdf
Имя файлаalgebra.pdf
ТипУчебное пособие
#736986
страница68 из 71
1   ...   63   64   65   66   67   68   69   70   71
4. Построение правильного 17-угольника
В Древней Греции геометры использовали для построений разные инструменты, но основными инструментами были циркуль и линейка. А в самом знаменитом древнегреческом учебнике геометрии, Началах Евклида, никакие другие инструменты вообще не встречаются. Поэтому под геометрическими построениями обычно подразумевают построения циркулем и линейкой. Циркуль позволяет построить окружность данного радиуса с центром в данной точке,
а линейка позволяет построить прямую, проходящую через две данные точки.
Построению правильных многоугольников в «Началах»
Евклида уделено большое внимание. Построение правильного треугольника описано в Предложении 1 Книги I, а почти вся Книга IV посвящена построению других правильных многоугольников квадрата, пятиугольника, шестиугольника, пятнадцатиугольника. Но ничего существенно нового геометры не могли добавить очень долго, вплоть дог, когда летний Гаусс показал, что с помощью циркуля и линейки можно построить правильный угольник. Впоследствии он доказал, что если число n = 2 2
k
+ простое, то с помощью циркуля и линейки можно построить правильный угольник. Гаусс утверждал также, что он умеет доказывать, что правильный угольник можно построить лишь в том случае, когда n = 2
m
p
1
. . . p
s
, где, . . . , p
s
— различные простые числа вида 2 2
k
+ 1. Но нив одной из его работ нет доказательства этого утверждения
550
Дополнение
Построение правильного угольника в большей степени относится не к геометрии, а к алгебре. Формула Муавра
(cos a
+ i sin a
)
n
= cos n
a
+ i sin n
a показывает, что корни уравнения x
n
− 1 = 0 имеют вид cos
2k
p
n
+ i sin
2k
p
n
. На комплексной плоскости эти точки являются вершинами правильного угольника. Таким образом, построение правильного угольника тесно связано с решением уравнения x
n
− 1 = 0. Это уравнение имеет очевидный корень x = 1. Чтобы избавиться от него, поделим многочлен x
n
− 1 на x − 1. В результате получим многочлен+ x
n
−2
+ . . . + x
2
+ x + 1. Именно его мы будем рассматривать в дальнейшем.
Будем говорить, что комплексное число a + ib можно построить, если можно построить отрезки длин a и те. можно построить точку a + ib на комплексной плоскости. Если задан отрезок единичной длины, то поданным отрезками можно построить отрезки a ± b, ab, Несложно проверить, что+ ib = ±
h
p
a
2
+ b
2
+ a
2

1/2
+ i

p
a
2
+ b
2
− Поэтому если отрезки a и b можно построить, то число тоже можно построить. В итоге получаем, что если числа u и v можно построить, то корни уравнения+ ux + v = 0 тоже можно построить.
Разберём для начала с этой точки зрения построение правильных угольников при n = 3 и n = 5. При n = 3 получаем уравнение x
2
+ x + 1 = 0. Это уравнение квадратное, поэтому его корни можно построить.
При n = 5 получаем уравнение x
4
+ x
3
+ x
2
+ x + 1 = Положим u = x + x
−1
. Легко проверить, что u
2
+ u − 1 = Корни и этого уравнения можно построить. Сих помощью можно построить корни уравнений x
2
u
1
x
+ 1 = и x
2
u
2
x
+ 1 = 0. Эти корни являются корнями исходного уравнения

4. Построение правильного 17-угольника
551
Теперь можно непосредственно заняться построением правильного угольника. Для этого, как мы убедились,
достаточно доказать, что корни уравнения x
16
+ x
15
+ . . .
. . .
+ x + 1 = 0 можно получить, последовательно решая квадратные уравнения. Достаточно даже получить один корень e
= cos
2
p
17
+ i sin
2
p
17
; остальные корни имеют вид e
2
,
e
3
, . . . ,
e
16
. Доказательство Гаусса основано на специальной нумерации этих корней. Он нумерует корни таким образом, чтобы при фиксированном l переход от корня с номером k) к происходил по одному и тому же правилу, а именно, чтобы при таком переходе число возводилось в некоторую фиксированную степень. Такую нумерацию можно получить, положив w
k
=
e
g
k
, где числа, g, g
2
, g
3
, . . . , дают разные остатки при делении на В самом деле, в таком случае w
k+l
=
e
g
k+l
=
e
g
k
g
l
= В качестве g можно взять, например, число 3. При этом Рассмотрим сначала квадратное уравнение с корнями
x
1
=
7
X
k=0
w
2k
,
x
2
=
7
X
k=0
w
2k+1
По теореме Виета
P
w
i
= −1, поэтому x
1
+ x
2
= −1. Легко проверить, что (
e
+
e
16
)
+ (
e
8
+
e
9
)
+ (
e
2
+
e
15
)
+ (
e
4
+
e
13
)
=
= 2(cos a
+ cos 8
a
+ cos 2
a
+ cos 4
a
),
x
2
= 2(cos 3
a
+ cos 7
a
+ cos 5
a
+ cos 6
a
),
Дополнение где a
= 2
p
/17. Воспользовавшись формулой cos p
a cos q
a
= cos(p + q)
a
+ cos(p − получим 8(cos a
+ cos 2
a
+ cos 3
a
+ . . . + cos 8
a
)
= 4(x
1
+ x
2
)
= Таким образом, и удовлетворяют квадратному уравнению с целыми коэффициентами. Следовательно, и можно построить.
Рассмотрим теперь квадратные уравнения с корнями 2(cos a
+ cos 4
a
),
y
2
=
3
X
k=0
w
4k+2
= 2(cos 8
a
+ cos Легко проверить, что y
1
+ y
2
= и 2(cos a
+ cos 2
a
+ cos 3
a
+ . . . + cos 8
a
)
= x
1
+ x
2
= Таким образом, и y
2
— корни квадратного уравнения x
1
y
+ 1 = 0. Аналогично доказывается, что 2(cos 3
a
+ cos 5
a
),
y
4
=
3
X
k=0
w
4k+3
= 2(cos 7
a
+ cos являются корнями квадратного уравнения y
2
x
2
y
+ 1 = Следовательно, y
1
, y
2
, и можно построить.
Рассмотрим, наконец, квадратное уравнение с корнями 2 cos a
,
z
2
=
w
4
+
w
12
= 2 cos Ясно, что и z
1
z
2
=2(cos 5
a
+cos 3
a
)
=y
3
. Таким образом, и z
2
— корни квадратного уравнения z
2
y
1
z
+y
3
=0.

5. Построения циркулем и линейкой
553
Поэтому число z
1
= 2 cos можно построить, а значит, можно построить и число e
= cos a
+ i sin a
. Но тогда можно построить и правильный угольник. Построения циркулем и линейкой

Здесь мы докажем, что с помощью циркуля и линейки нельзя выполнить некоторые построения, например, нельзя построить отрезок, если задан отрезок длины a, и нельзя разделить произвольный угол натри равные части. Первая из этих задач называется
удвоением куба, потому что она эквивалентна задаче о построении ребра куба в 2 раза большего объёма, чем куб сданным ребром. Вторая задача называется
трисекцией угла. Кроме того, мы докажем, что с помощью циркуля и линейки нельзя построить треугольник по длинам его биссектрис.
Сначала нужно точно сформулировать, что такое
постро-
ение циркулем и линейкой. В задаче на построение циркулем и линейкой обычно бывает задан некоторый набор точек. Окружность и прямую можно задать двумя точками,
поэтому включать в набор исходных данных окружности и прямые нет необходимости. В некоторых задачах набор исходных данных может быть пустым множеством например, в задаче о построении правильного треугольника или пятиугольника исходного набора данных нет. Задача на построение заключается в том, чтобы добавить к исходному набору точек некоторые другие точки так, чтобы при этом в новом наборе содержались некоторые требуемые точки. К исходным данным разрешается добавлять следующие точки, прямые и окружности) прямую, проходящую через две данные точки) окружность сданным центром, проходящую через данную точку) точку пересечения двух данных прямых, двух данных окружностей или данной прямой и данной окружности) произвольную точку

554
Дополнение
Добавление произвольной точки требует пояснений. Подразумевается, что конечный результат должен не зависеть от выбора этой точки. Точнее говоря, если вместо выбранной произвольной точки мы возьмём любую другую достаточно близкую к ней точку, то при этом конечный результат не должен измениться. Отметим, что операция выбора произвольной точки на данной прямой l или данной окружности не даёт ничего нового. Действительно, вместо этого можно выбрать две произвольные точки A и B и построить точку пересечения прямой AB с прямой l или с окружностью Выясним, по каким алгебраическим правилам координаты добавляемых точек получаются из координат исходных точек. Введём на плоскости прямоугольную систему координат. Каждая точка плоскости имеет две координаты.
Рассмотрим набор всех численных значений координат исходных точек, не различая координаты x и Теорема Предположим, что к набору точек с координатами t
1
, . . . , в процессе построений циркулем и линейкой добавилась ровно одна точка с координатами и Тогда либо число s

i
(i = 1, 2) рационально, либо оно получается из чисел t

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

Д ока за тел ь ст во. Разберём всевозможные варианты добавления одной точки.
а)
Добавление произвольной точки. Для любой точки найдётся сколь угодно близкая к ней точка, обе координаты которой рациональны. Поэтому в качестве произвольной точки всегда можно выбрать точку с рациональными коор- динатами.
б)
Добавление точки пересечения двух прямых. Прямая,
проходящая через точки с координатами (a
1
, b
1
) и (a
2
, b
2
),
задаётся уравнением a
1
y
b
1
=
a
2
a
1
b
2
b
1
,

5. Построения циркулем и линейкой
555
т. е. (b
2
b
1
)x
+ (a
1
a
2
)y
= a
1
b
2
a
2
b
1
. Коэффициенты этого уравнения получаются из координат исходных точек применением операций умножения и вычитания.
Точка пересечения прямых, заданных уравнениями+ q
1
y
= r
1
,
p
2
x
+ q
2
y
= имеет координаты r
2
q
1
p
1
q
2
p
2
q
1
,
p
1
r
2
p
2
r
1
p
1
q
2
− Эти числа получаются из коэффициентов уравнений применением операций вычитания, умножения и деления. Следовательно, координаты точки пересечения двух прямых,
проходящих через две пары данных точек, можно получить из координат этих четырёх данных точек, применяя операции вычитания, умножения и деления.
Операция извлечения квадратного корня пока не использовалась. Она нужна лишь для нахождения координат точек пересечения прямой и окружности или двух окруж- ностей.
в)
Добавление точки пересечения прямой и окружности.
Окружность с центром (a
1
, b
1
), проходящая через точку, b
2
), имеет уравнение a
1
)
2
+ (y b
1
)
2
= (a
2
a
1
)
2
+ (b
2
− те, где c
1
= a
2 2
− 2a
1
a
2
+ b
2 2
− Для нахождения координат точек пересечения прямой+ qy = r и окружности x
2
−2ax +y
2
−2by =c нужно решить систему уравнений+ qy = r,
x
2
− 2ax + y
2
− 2by = Одно из чисел p и q отлично от нуля. Будем для определён- ности считать, что q 6= 0. Тогда из первого уравнения можно получить выражение для y через x:
y
=
r
px
q
(1)

556
Дополнение
Подставив это выражение в уравнение окружности, получим квадратное уравнение+ q
2
)x
2
+ 2(bpq aq
2
pr)x + (r
2
− 2bqr c
2
q)
= Корни и этого уравнения выражаются через его коэффициенты с помощью операций сложения, вычитания,
умножения и извлечения квадратного корня. Соответствующие выражения для и можно получить по формуле (1).
г)
Добавление точки пересечения двух окружностей.
Для нахождения координат точки пересечения двух окружностей нужно решить систему уравнений 2a
1
x
+ y
2
− 2b
1
y
= c
1
,
x
2
− 2a
2
x
+ y
2
− 2b
2
y
= Вычитая из первого уравнения второе, можно перейти к эквивалентной системе уравнений 2(a
2
a
1
)x
+ 2(b
2
b
1
)y
= c
1
c
2
,
x
2
− 2a
2
x
+ y
2
− 2b
2
y
= Система уравнений такого вида была решена при разборе случая в).
У двоение куба Отрезок a можно выбрать в качестве отрезка (1, 0) на оси Ox. Таким образом, в задаче удвоения куба требуется построить точку с координатами (
3

2, 0). Предположим,
что эту точку можно построить с помощью циркуля или- нейки. Тогда согласно теореме 1 число можно получить из рациональных чисел, используя операции сложения, вычитания, деления, умножения и извлечения квадратного корня, те, как мы будем для краткости говорить, это число можно выразить
в квадратных радикалах. Для доказательства неразрешимости задачи удвоения куба с помощью циркуля и линейки нужно доказать, что число не выражается в квадратных радикалах. Напомним, что число
3

2
иррационально (задача 31.2 а

5. Построения циркулем и линейкой
557
Т е орем а Предположим, что один из корней уравнения x

3
+ Ax
2
+ Bx + C = 0, где A
, B, C — рациональные
числа, выражается в квадратных радикалах. Тогда это

уравнение имеет рациональный корень.
Д ока за тел ь ст во. Отметим прежде всего, что любое число, полученное из чисел u
1
, . . . , применением операций сложения, вычитания, умножения и деления, можно представить в виде, . . . , u
n
)/Q(u
1
, . . . , где P и Q — многочлены с рациональными коэффициентами, те. выражения, полученные без использования операции деления. В самом деле Для любого числа a
, выражающегося в квадратных радикалах, можно определить его
ранг как наибольшее число расположенных один внутри другого квадратных радикалов в выражении для числа a
. Это определение нужно сформулировать более аккуратно. Например, (1+

2)
2
= 3 + те. Тем самым, одно выражение числа +

2 имеет ранга другое выражение того же числа имеет ранг 2. Поэтому нужно сначала определить ранг выражения, а в качестве ранга самого числа взять наименьший из рангов всех его выражений.
Для числа ранга n можно определить его порядок следующим образом. Рассмотрим для числа все его выражения ранга n. В каждое такое выражение входит несколько радикалов вида, где ранг выражения R равен n
− пусть k — количество таких радикалов. Наименьшее из всех таких чисел k будем называть порядком числа Кубическое уравнение x
3
+ Ax
2
+ Bx + C = 0 имеет три корня x
1
, x
2
, необязательно различных, для которых
Дополнение выполняется соотношение x
1
)(x
x
2
)(x
x
3
)
= x
3
+ Ax
2
+ Bx + В частности, x
1
+ x
2
+ x
3
= Предположим, что один из корней этого кубического уравнения выражается в квадратных радикалах. Остальные корни могут выражаться в квадратных радикалах, а могут и не выражаться. Возьмём все корни, которые выражаются в квадратных радикалах, и выберем среди них все корни с наименьшим рангом. Затем среди этих корней выберем корни с наименьшим порядком. Если такой корень один, то выберем его, а если их несколько, то выберем любой из них.
Пусть при этом выбран корень с рангом n и порядком Требуется доказать, что n = 0, те. число x
1
рационально.
Предположим, что n>1. Рассмотрим для числа x
1
какое-ни- будь выражение ранга n и порядка k. Пусть — одно из выражений ранга n, входящих в это выражение. Тогда
x
1
можно представить в виде+ b

R
c
+ где выражения a, b, c и d содержат не более k − 1 радикалов ранга n и не содержат радикалов большего ранга. Докажем,
что c d

R
6= 0. Если d = 0, то c 6= 0. Если же d 6= 0, то из равенства c d

R
= 0 следовало бы, что c/d. Подставляя это значение числа в формулу (2), можно получить для выражение ранга не более n, содержащего небо- лее k − 1 радикалов ранга n. Это противоречит тому, что ранг числа равен n, а порядок равен k. Следовательно d

R
6= 0, а значит+ b

R)(c
d

R)
c
2
d
2
R
= p + Подставив значение x
1
= p + q

R в кубическое уравнение,
получим
0 = (p + q

R)
3
+ A(p + q

R)
2
+ B(p + q

R)
+ C = M + N

R,

5. Построения циркулем и линейкой
559
где выражения M и N содержат не более k − 1 радикалов ранга n и не содержат радикалов большего ранга. Если 0, то −M/N, а выше было показано, что такого быть не может. Следовательно, M = N = 0. Непосредственные вычисления показывают, что q

R)
3
+ A(p q

R)
2
+ B(p q

R)
+ C = M − те другой корень кубического уравнения.
А так как x
1
+ x
2
+ x
3
= −A, то x
3
= −A x
1
x
2
= −A − Наибольший ранг радикалов, входящих в это выражение числа x
3
, не превосходит n, причём радикалов ранга n небо- лее k−1. Это противоречит выбору корня как корня наименьшего ранга n и при этом наименьшего порядка С помощью теоремы 2 легко доказать, что число
3

2
нельзя выразить в радикалах. Действительно, рассмотрим кубическое уравнение x
3
− 2 = 0. У него есть лишь один вещественный корень, а именно. Число нерационально, поэтому уравнение x
3
− 2 = 0 не имеет рациональных корней. Следовательно, у этого уравнения нет корней,
выражающихся в квадратных радикалах.
Т рисе к ц и я угла Чтобы доказать, что не существует общего способа построений, позволяющего разделить натри равные части любой угол, достаточно доказать, что с помощью циркуля и линейки нельзя разделить натри равные части угол в 30

Введём систему координат Oxy, выбрав в качестве начала координат вершину данного угла AOB и направив ось по стороне OA. Можно считать, что точки A и B удалены от точки O на расстояние 1. Тогда в задаче трисекции угла требуется по точке с координатами (cos 3
f
, sin 3
f
) построить точку с координатами (cos f
, sin f
). В случае, когда f
= 10

, исходная точка имеет координаты 2
,
1 2

. Обе её координаты выражаются в квадратных радикалах. По
Дополнение этому достаточно доказать, что число sin не выражается в квадратных радикалах.
Так как sin 3
f
= sin(
f
+ 2
f
)
= sin f
cos 2
f
+ cos f
sin 2
f
=
= sin f
(1
− 2 sin
2
f
)
+ 2(1 − sin
2
f
) sin f
= 3 sin f
− 4 то число x = sin удовлетворяет кубическому уравнению
− 4x
3
= 1/2, те Согласно теореме 2 достаточно доказать, что у этого уравнения нет рациональных корней. Положим 2x = p/q, где и q — целые числа, не имеющие общих делителей. Тогда+ q
3
= 0, те. Следовательно, число делится на p, а значит, p = ±1. Поэтому ±1 ∓ 3q
2
+ q
3
= те. Число 1 делится на q, поэтому q = В итоге получаем, что x = ±1/2. Легко проверить, что значения не являются корнями уравнения (3). Получено противоречие, поэтому уравнение (3) не имеет рациональных корней, а значит, число sin не выражается в квадратных радикалах.
П острое ни е треугольника по биссектрисам Если заданы длины медиан треугольника или длины его высот, то треугольник можно построить циркулем и линейкой. Но если заданы длины биссектрис треугольника, тонет общего способа, позволяющего построить сам треугольник циркулем и линейкой. Чтобы это доказать, достаточно доказать, что треугольник, длины биссектрис которого равны, 1 и 1, нельзя построить циркулем и линейкой.
Нам потребуются два геометрических факта, доказательства которых можно найти в книге В. В. Пр ас о лов. Задачи по планиметрии. е изд. М МЦНМО, 2007. Прежде всего заметим, что треугольнику которого две биссектрисы равны, равнобедренный (задача 5.55 из указанной

6. Хроматический многочлен графа
561
книги), поэтому в рассматриваемом треугольнике те. Далее, согласно задаче 12.37 г) из указанной книги 4p sin(
b
/2) sin(
g
/2)/(sin b
+ sin g
),
l
b
= 4p sin(
a
/2) sin(
g
/2)/(sin a
+ sin Поэтому =
l
a
l
b
=
sin(
b
/2)
sin(
a
/2)
·
sin a
+ sin b
sin b
+ sin g
=
=
sin(
b
/2)
cos b
·
sin 2
b
+ sin b
4 sin(
b
/2) cos(
b
/2)
=
sin(3
b
/2)
2 cos Если рассматриваемый треугольник можно было бы построить циркулем и линейкой, то число x=sin(
b
/2) выражалось бы в квадратных радикалах. Ясно, что sin(3
b
/2)
= 3x − и cos b
= 1 − 2x
2
. Поэтому для x мы получаем уравнение 12x
2
− 3x + 6 = 0. После замены y = 2x − 2 перейдём к уравнению y
3
− 15y − 10 = 0. Согласно теореме 2 достаточно проверить, что это уравнение не имеет рациональных корней. Предположим, что число p/q, где p и q — взаимно простые целые числа, является корнем этого уравнения.
Тогда p
3
= 5q
2
(3p
+ 2q), поэтому p = 5r, где r — целое число.
В таком случае 25r
3
= q
2
(15r
+ 2q). Следовательно, число тоже делится на 5, чего не может быть. Хроматический многочлен графа

Рассмотрим в пространстве систему из нескольких точек и отрезков, соединяющих некоторые из этих точек. При этом нас будет интересовать лишь то, какие именно пары точек соединены отрезками. Более того, эти отрезки можно считать не прямолинейными, а криволинейными. Такую систему точек называют
графом; сами точки называют вершинами графа, а отрезки — рёбрами графа.
Граф называют
планарным, если его можно расположить на плоскости так, чтобы его рёбра попарно не пересе-
Дополнение кались. Например, граф, изображённый на рис. 1, не планарный. Это следует из решения известной задачи о трёх домах и трёх колодцах Можно ли каждый из трёх домов
Рис. соединить дорожкой с каждым из трёх колодцев так, чтобы эти дорожки не пересекались?».
В 1890 г. было доказано, что вершины любого планарного графа можно раскрасить в 5 цветов так, что концы любого ребра будут разноцветными. После этого долго была популярна задача четы- рёх красок Любой ли планарный граф можно раскрасить в 4 цвета. (Под раскраской графа здесь и далее подразумевается такая раскраска вершин графа, что концы любого ребра разноцветные) Лишь в 1977 г. было доказано, что любой планарный граф можно раскрасить в 4 цвета. Это доказательство опиралось на перебор огромного количества различных вариантов, выполненный с помощью компью- тера.
С раскрасками графов связано одно интересное явление,
которое мы сейчас обсудим. Пусть G — некоторый графа f(G, x) — количество раскрасок этого графа в x цветов.
Удивительным образом оказывается, что f(G, x) — многочлен степени n, где n — число вершин графа. Прежде чем доказывать это утверждение, разберём два простых при- мера.
Наиболее прост тот случай, когда у графа G нет вообще никаких рёбер, а есть только n вершин. В этом случае каждую вершину можно окрасить любым цветом, независимо от остальных вершин. Поэтому f(G, x) = Другой крайний случай — граф G с n вершинами, любые две из которых соединены ребром. В этом случае все вершины должны быть разноцветными, поэтому, x)
= x(x − 1) . . . (x n + 1).

6. Хроматический многочлен графа
563
В обоих случаях f(G, x) — многочлен степени n. Как мы сейчас убедимся, из этого уже следует, что f(G, x) — многочлен степени n для любого графа G с n вершинами.
Рассмотрим граф с n вершинами, в котором две вершины и B соединены ребром. Сопоставим ему граф в котором все вершины и рёбра те же самые, за исключением того, что в нём нет ребра, соединяющего вершины и B. Сопоставим графу также граф G
n
−1
, в котором все вершины и рёбра такие же, как у графов и G

n
, за исключением того, что в нём вершины A и B отождествлены друг с другом (при этом могут возникнуть двойные рёбра, номы их заменяем на обычные рёбра). Примеры графов, и приведены на рис. 2. При этом двойное = Рис. ребро, соединяющее вершины A = B и D, заменено на обычное (однократное) ребро.
Любая раскраска графа с одноцветными вершинами и B соответствует определённой раскраске графа а любая раскраска того же графа с разноцветными вершинами и B — раскраске графа G
+
n
. Поэтому, x) = f(G
+
n
, x) + f(G
n
−1
, С помощью формулы (1) несложно доказать, что если граф с n вершинами, то f(G
n
, x) — многочлен степени. Применим для этого индукцию по n. При n = 1 граф состоит из одной точки, поэтому f(G
1
, x) = x. Предполо-
Дополнение жим, что для любого графа с n − 1 вершиной функция) представляет собой многочлен степени n.
Возьмём произвольный граф с n вершинами. Применив несколько раз формулу (1), можно перейти от графа к графу с n вершинами, любые две из которых соединены ребром. Хроматический многочлен полученного графа равен, поэтому, x) = x(x − 1) . . . (x n + 1) + f
1
+ . . . + где f
1
, . . . , f
k
— хроматические многочлены графов с n − вершиной, те. многочлены степени n − При доказательстве мы воспользовались тем, что хроматический многочлен графа, все вершины которого соединены рёбрами, равен x(x − 1) . . . (x n + 1). Но можно воспользоваться и тем, что хроматический многочлен графа,
у которого вообще нет рёбер, равен x
n
. Для этого формулу) нужно записать в виде, x) = f(G

n
, x) f(G
n
−1
, Применив такую формулу несколько раз, можно перейти от графа к графу с n вершинами, у которого вообще нет рёбер. Поэтому, x) = x
n
g
1
. . . − где g
1
, . . . , g
l
— хроматические многочлены графов с n − 1
вершиной.
Второй способ доказательства имеет некоторые преимущества. Например, записав хроматический многочлен графа в виде (3), мы без труда докажем следующую теорему.
Т е орем а Хроматический многочлен графа с n вершинами имеет вид a
1
x
n
−1
+ a
2
x
n
−2
a
3
x
n
−3
+ . . . где Эту теорему сформулировали доказал в 1932 г. американский математик Хасслер Уитни.

7. Трансцендентность чисел e и p
565
1   ...   63   64   65   66   67   68   69   70   71


написать администратору сайта