Научный журнал

ВОПРОСЫ МАТЕМАТИКИ, ТЕХНИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ 
 
 
Вестник
 
КАСУ
 
220 
няло  более  столетия.  Однако  на  первый 
взгляд  чуть  более  слабое  утверждение  о 
правильной 5-раскраске доказать достаточ-
но просто. Для доказательства понадобится 
формула  Эйлера,  связывающая  число  вер-
шин,  ребер  и  областей.  Пусть 
M
 обозна-
чает число элементов конечного множества 
M. 
Теорема Эйлера. Для любого плоского 
графа 
( )
( )
( )
G
R
G
D
G
V
+
=
+
2
. 
Теорема  2 .   Любой  плоский  граф  до-
пускает правильную 5-раскраску. 
Доказательство.  Сначала  упро-
стим  граф.  Если  есть  несколько  ребер, 
соединяющих  некоторую  пару  вершин 
(такая  ситуация  может  возникнуть,  если 
две  страны  имеют  несколько  несвязанных 
между  собой  кусков  границы,  например 
как  у  России  и  Китая),  то  оставим  только 
одно ребро: правильность раскраски такого 
уменьшенного графа все равно гарантирует 
шенного  графа  все  равно  гарантирует  пра-
вильную раскраску исходного. 
Проведем теперь индукцию по числу 
вершин графа. Для графа с тремя вершина-
ми  утверждение  теоремы  очевидно.  Пусть 
оно  справедливо  для  всех  графов  с 
1
−
n
 
вершиной. 
Пусть 
m
D
D
D
,...,
,
2
1
 –  полный  набор 
всех 
)
(G
D
m
=
 областей графа, а 
)
(
i
D
N
 – 
число  ребер,  составляющих  границу 
i
-й 
области  графа.  При  этом 
3
)
(
>
D
N
 для 
любого 
i
. Любое ребро входит в границу в 
точности двух областей, поэтому 
 
)
(
2
)
(
...
)
(
)
(
2
1
G
R
D
N
D
N
D
N
m
=
+
+
+
. 
 
Вследствие  неравенств 
3
)
(
≥
i
D
N
 
имеем 
 
)
(
3
3
)
(
...
)
(
)
(
)
(
2
2
1
G
D
m
D
N
D
N
D
N
G
R
m
=
≥
+
+
+
=
, откуда 
)
(
3
)
(
2
G
D
G
R
≥
. 
 
По формуле Эйлера 
( )
( )
( )
G
R
G
D
G
V
=
+
−
2
, откуда 
 
( )
( )
( )
( )
( )
G
R
G
V
G
D
G
V
G
R
2
6
3
3
6
3
3
+
−
≤
+
−
=
 и, следовательно, 
( )
6
3
)
(
−
≤
G
V
G
R
                    (1) 
 
Заметим,  что  удвоенное  число  ребер 
можно отождествить и с другой характери-
стикой  графа.  Пусть 
n
α
α
α
,...,
,
2
1
 есть 
полный  набор 
)
(G
V
n
=
 вершин  графа,  а 
)
(
j
M
α
 –  число  ребер,  сходящихся  в  вер-
шине  с  номером 
j
.  Но  каждое  ребро  за-
канчивается двумя вершинами, поэтому 
 
)
(
...
)
(
)
(
)
(
2
2
1
n
M
M
M
G
R
α
α
α
+
+
+
=
. 
 
Кроме того,  как это следует из нера-
венства (1), 
( )
12
6
)
(
2
−
≤
G
V
G
R
.  
Следовательно, 
 
12
)
(
6
)
(
...
)
(
)
(
2
1
−
≤
+
+
+
G
V
M
M
M
n
α
α
α
        (2) 
 
Из  последнего  неравенства  можно 
вывести, что существует, по крайней мере, 
одна вершина, в которой сходится не более 
пяти  ребер.  Действительно,  предположим 
противное, то есть 
j
∀
 
6
)
(
≥
j
M
α
.  Тогда 
)
(
6
6
)
(
...
)
(
)
(
2
1
G
V
n
M
M
M
n
=
≥
+
+
+
α
α
α
, что противоречит (2). 
 
Перенумеруем  вершины  так,  что  в  вершине 
n
α
α =
 сходится  не  более  пяти 

ВОПРОСЫ МАТЕМАТИКИ, ТЕХНИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ 
 
 
Вестник
 
КАСУ
 
221 
ребер. 
Если в вершине 
α
 сходятся не более 
четырех  ребер,  то  рассмотрим  граф 
α
\
G
, 
который  получается  из 
G
 устранением 
вершины 
α
 и  всех  оканчивающихся  в  ней 
ребер.  Граф 
α
\
G
 допускает  правильную 
5-раскраску  по  предположению  индукции. 
А  так  как  ребра  соединяют  вершину,  а  не 
более  чем  с  четырьмя  вершинами  этого 
меньшего  графа,  то  для  правильной  рас-
краски 
α
 остается,  по  крайней  мере,  один 
цвет (из пяти). 
Пусть  теперь  в 
α
 сходится  ровно 
пять  ребер.  Рассмотрим  граф 
G
H
⊂
,  со-
стоящий  из  тех  пяти  вершин,  куда  прихо-
дят  ребра,  выходящие  из 
α
 и  соединяю-
щих  их  (в 
G
)  ребер.  В  графе 
H
 обяза-
тельно  найдутся  две  вершины,  не  соеди-
ненные  ребром.  Действительно  в  против-
ном  случае  в  пятиугольнике 
H
 будет 
10
2
5
=
C
 ребер  (это  нетрудно  посчитать  и 
непосредственно). Однако, в силу (1) 
 
( )
9
6
5
3
6
3
)
(
=
−
⋅
=
−
≤
H
V
H
R
, 
 
и мы приходим к противоречию. 
Пусть 
β
 и 
γ
 суть  те  вершины 
H
, 
которые  не  соединены  между  собой.  Не 
соединены они и в 
α
\
G
. Рассмотрим граф 
G
′
,  который  получается  из 
α
\
G
 при  по-
мощи  деформации,  которая  отождествляет 
β
 и 
γ
. 
Граф 
G
 –  это  плоский  граф,  так  как 
при  отождествлении  вершин  в  этой  ситуа-
ции не может возникнуть петли. Но для 
G
′
 
справедливо  предположение  индукции,  и 
существует  некоторая  его  правильная  5-
раскраска 
ϕ
.  Разъединим  в  этом  раскра-
шенном графе вершины 
β
 и 
γ
. Тогда пра-
вильную  5-раскраску  получает  и  граф 
α
\
G
,  причем  такую,  что 
)
(
)
(
γ
ϕ
β
ϕ
=
. 
Иными  словами, 
β
 и 
γ
 раскрашены  оди-
наково  и,  следовательно,  раскраска  пяти 
соседних с 
α
 вершин графа 
H
 использует 
не более четырех цветов. 
Используем  оставшийся  цвет  для 
раскраски вершины 
α
 и получим правиль-
ную 5-раскраску 
G
. 
Проблема четырех красок кажется на 
первый  взгляд  изолированной  задачей,  ма-
ло связанной с другими разделами матема-
тики и практическими задачами.  На самом 
деле это не так. Известно более 20 ее пере-
формулировок,  которые  связывают  эту 
проблему  с  задачами  алгебры,  статистиче-
ской механики и задачами планирования. И 
это  тоже  характерно  для  математики:  ре-
шение задачи, изучаемой из чистого любо-
пытства, оказывается полезным в описании 
реальных и совершенно различных по сво-
ей природе объектов и процессов. 
О  доказательстве  теоремы  че-
тырех красок. 
Доказательство К. Аппеля и У. Хаке-
на,  в  целом,  хотя  и  принятое  математиче-
ским  сообществом,  вызывает  до  сих  пор 
определенный  скептицизм.  Для  читателя, 
поверхностно  знакомого  с  математикой, 
предыдущая  фраза  должна  вызвать  изум-
ление:  а  как  же  обязательный  для  матема-
тики  принцип  исключенного  третьего,  в 
соответствии с которым утверждение либо 
справедливо,  либо  нет?  Дело  обстоит  не 
так просто. Вот что пишут сами авторы до-
казательства: «Читатель должен разобрать-
ся  в  50  страницах  текста  и  диаграмм,  85 
страницах  с  почти  2500  дополнительными 
диаграммами,  400  страницами  микрофи-
шей,  содержащими  еще  диаграммы,  а  так-
же  тысячи  отдельных  проверок  утвержде-
ний, сделанных в 24 леммах основного тек-
ста. Вдобавок читатель узнает, что провер-
ка некоторых фактов потребовала 1200 ча-
сов компьютерного времени, а при провер-
ке  вручную  потребовалось  бы  гораздо 
больше.  Статьи  устрашающи  по  стилю  и 
длине,  и  немногие  математики  прочли  их 
сколько-нибудь подробно». 
Говоря  прямо,  компьютерную  часть 
доказательства 
невозможно 
проверить 
вручную, а традиционная часть доказатель-
ства длинна и сложна настолько, что ее ни-
кто целиком и не проверял. Между тем до-
казательство,  не  поддающееся  проверке, 
есть  нонсенс.  Согласиться  с  подобным  до-
казательством  означает  примерно  то  же, 
что  просто  поверить  авторам.  Но  и  здесь 
все сложнее. 
Долгое  время  идеалом  математиче-
ской  строгости  были  формулировки  и  до-
казательства Евклида, в которых осуществ-
лялась программа вывода теорем из аксиом 

ВОПРОСЫ МАТЕМАТИКИ, ТЕХНИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ 
 
 
Вестник
 
КАСУ
 
222 
по  определенным  правилам  (метод  дедук-
ции,  позволяющий  получать  неочевидные 
утверждения  из  очевидных).  Этот  образец 
строгости  и  в  наше  время  недостижим  в 
курсе школьной математики, но для совре-
менной чистой математики стандарты Евк-
лида  недостаточны.  Евклид,  по-видимому, 
не  задумывался  над  тем,  почему  прямая 
делит  плоскость  на  две  части  (и  что  это 
значит), он не определял понятия "между", 
считая это понятие очевидным и т.д. Боль-
шая  часть  соответствующих  утверждений 
доказана или включена в аксиоматику гео-
метрии  только  в  последнюю  сотню  лет. 
Формальные выводы из новой системы ак-
сиом  стали  гораздо  длиннее,  чем  в  антич-
ные времена. 
Трудно  даже  вообразить  длину  пол-
ного  вывода  теоремы  о  пяти  красках  в  со-
ответствии  с  современными  стандартами 
математической  логики  и  системы  аксиом 
геометрии. Но совершенно точно, что такое 
рассуждение никто никогда не проделывал 
из-за  бесполезности  этого  занятия:  фор-
мальные  выводы  практически не  поддают-
ся  проверке  в  силу  свойств  человеческой 
психики: помимо их гораздо большей дли-
ны  их  сознательное  усвоение  идет  гораздо 
медленнее.  Поэтому  обычно  удовлетворя-
ются уверенностью в том, что формальный 
вывод возможен в принципе. 
Таким образом, вопрос о доказатель-
стве  теоремы  четырех  красок  с  точки  зре-
ния чистой математики остается открытым. 
 
ЛИТЕРАТУРА 
1. Радемахер Г., Теплиц О. Числа и фигуры. 
Опыты  математического  мышления.  - 
М.: «Наука», 1966. - 264 с. 
2. Самохин А.В. Проблема четырех красок: 
неоконченная  история  доказательства// 
СОЖ, 2000, №7, с. 91-96. 
 
 
 
УДК 002 
ТЕҢДЕУЛЕР ТАҚЫРЫБЫНА ОЛИМПИАДАЛЫҚ ЕСЕПТЕР 
Нуризинов М.К. 
 
Қазіргі 
динамикалық 
өзгергіш 
қоғамның  дамуына  интеллектуалдық  по-
тенциалды  жетілдіру  жəне  сақтау  негізгі 
шарттарының 
бірі 
болып 
табылады. 
Көптеген  оқытушылар  олимпиадаға  тиімді 
дайындайтын  есептерді  таңдауда  қиын-
дықтарға  кездеседі.  Бірқатар  мектептер 
оқушыларды олимпиадаға авторлық əдісте-
мелер  арқылы  дайындайды.  Бірақ,  əр 
мектептің оқушысы өзін көрсете білуі тиіс. 
Мектеп  оқушыларын  олимпиадаға 
дайындау жүйесі қажет, бұл мақсатты маз-
мұны,  формасы,  əдіс,  тəсілдері  қарасты-
рылған бағдарлама түрінде болуы тиіс. 
Пəндік  олимпиада  жəне  оған  дай-
ындау туралы көптеген  əдебиеттер бар, бі-
рақ  белгілі  тақырып  бойынша  дайын-дау-
дың  арнайы  жүйесі  жоқ,  атап  айтқанда 
теңдеулер тақырыбы бойынша. 
Барлық  авторлар  олимпиаданы  оқу-
шылардың  интеллектуалдық  деңгейін  же-
тілдіру  құралы  ретінде  бір  ауыздан  қол-
дайды. 
Математика 
пəнінен 
олимпиада 
өткізудің  қарама  –  қайшылықтары  мен  қа-
жетті  құралдарымен  жабдықталмау  мəсе-
лесі барлық мектептерде кездеседі. 
Қарастырған  проблеманың  аспектісі 
көп  зерттелмеген  немесе  педагогикалық 
əдебиеттерде  көп  қарастырылмағандығын 
ескеруіміз қажет. 
Математикадан  олимпиадалық  есеп-
тердің  жүйелік  əдісі  алғаш  рет  қолда-
нылуы. 
Теңдеуді  шешуге  тригонометриялық 
көрсеткіш əдісін қолдану. 
Тригонометриялық  көрсеткіш  ауыс-
палыны  алмасытырудың  бірден  бір  тəсілі 
болып  саналады  жəне  шыққан  теңдеуді 
анықтау саласының тригонометриялық фу-
нкция мəнімен сəйкес келген жағдайда қол-
данылады. 
Мұндайда  қандайда  бір  функцияны 
таңдау теңдеу түріне, теңсіздігіне, олардың 
жүйесіне  немесе  алгебралық  формуласына 
байланысты. 
 

ВОПРОСЫ МАТЕМАТИКИ, ТЕХНИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ 
 
 
Вестник
 
КАСУ
 
223 
Егер 
есептің 
шарты 
бойынша 
ауыспалы 
x
 тиісті 
мəні 
1
≤
x
 
теңсіздігімен  анықталады,  онда 
α
sin
=
x
 
немесе 
α
cos
=
x
.ауысады. 
Бірінші 
жағдайда  мынаны 



−
∈
2
;
2
π
π
α
 қарас-
тырамыз,  өйткені  осы  аралықта  үздіксіз 
функция 
x
y
sin
=
 артады,  сондықтан  əр 
мəні бір нүктегі сəйкес келеді. 
x
сos
y
=
 үздіксіз  аралықта 
[ ]
π
;
0
 
функциясын  азайтады,  сондықтан  əр  мəні 
бір  нүктеге  тең.  Сондықтан 
α
cos
=
x
 
ауыпалы. Ауыспалы кез-келген нақты мəн-
ді 
қабылдаған 
жағдайда 





−
∈
=
2
;
2
,
π
π
α
α
tg
x
 қолданылады  не-
месе 
( )
π
α
α
;
0
,
∈
=
ctg
x
, 
өйткені 
tgx
y
=
 и 
ctgx
y
=
 функциясының  мəні 
көптеген нақты сандарға сəйкес келеді. 
Ауыспалы 
α
sin
r
x
=
 сирек  қолда-
нылады  немесе 
α
cos
r
x
=
, 
мұнда 
0
,
≥
∈
r
R
r
, 
α
 мəнін  таңдау  тағы  да 
нақты жағдайға байланысты. 
Егер 
x
 и 
y
,  өрнегінің мəні екі ауыс-
палыға 
байланысты 
болса, 
онда 
α
cos
r
x
=
, 
α
sin
r
y
=
қолданылады, 
мұнда 
)
[
π
α
2
;
0
,
0
,
∈
≥
∈
r
R
r
.  Бұл 
заңды. Кез келген 
x
 ж 
y
 үшін 
0
≥
r
, 
мұнда 
2
2
2
r
y
x
=
+
. 
Онда 
0
≠
r
 болса 
1
1
2
2
2
2
2
2
=






+






⇔
=
+
r
y
r
x
r
y
r
x
. 
Квадраты  бірге  тең  сан  модуль 
бойынша бірге айналмайды, оларды кейбір 
бұрыштардың  синус  жəне  косинусы  ретін-
де қарастыруға болады. Геометриялық мəні 
келесідей:  əрбір 
( )
y
x;
 
r
 қашықтығын 
( )
y
x;
 қиғаш  векторы  мен  абсцисс  осі  оң 
бағытына дейін анықтайды. 
Соңғы  ескерту.  Мұндай  көрсеткіші 
қолдану  аса  қиын  емес,  маңыздысы  оны 
көре  білу.  Сондықтан  да  оқушыларға 
тригонометриялық  көрсеткіш  «белгілерін» 
тани білуге үйрету қажет. Келесі тараудың 
мазмұны  мынадай  шеберлікті  қажет  етеді. 
Иррационал теңдеулер. 
Мысал 1. Теңдеуді шешу. 
1
2
2
1
2
1
2
2
=
+
−
+
x
x
x
. 
Тригонометриялық  көрсеткіш  көме-
гімен шешу 
Егер 
0
1
2
≥
−
x
,  онда 
1
≤
х
.  Сон-
дықтан 



−
∈
=
2
;
2
,
sin
π
π
α
α
х
. 
Теңдеу өзгереді. 
 
α
π
α
α
α
α
α
α
α
2
cos
4
sin
2
cos
2
cos
sin
sin
2
1
2
cos
sin
2
1
2
=





 +
⇔
=
+
⇔
−
=
+
. 
 
Егер 
u
=
+
4
π
α
, мұнда 



−
∈
4
3
;
4
π
π
u
, онда 
 

жүктеу/скачать 2,36 Mb.

Достарыңызбен бөлісу: