The four-color problem


 Proof of the 4-color theorem



Download 0,64 Mb.
Pdf ko'rish
bet7/8
Sana21.02.2022
Hajmi0,64 Mb.
#461495
1   2   3   4   5   6   7   8
Bog'liq
docsity-problema-chetyreh-krasok-1 (2)

2.2 Proof of the 4-color theorem
When coloring a map of Kamchatka consisting of 9 regions, in
in any form, without any system, each time there was a failure.
15
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev (lochchinbek1992@gmail.com)
Then it was decided to start with any area and around it by
clockwise to color adjacent adjacent areas (areas with a common border).
border), so each time expanding the circle to new areas. Then
you were able to colorize the map (see Appendix 1).
But this is not enough for such a statement. Now you need to
consider other map options as well.
You need to solve the following problem: How many countries can
touch each other directly so that all countries have a common border
borders? And, how many colors will it take to color them? "Form" of countries
it may differ from the examples given. The countries are contiguous.
Option 1: two countries can touch each other directly.
Obviously, you need 2 colors (fig. 4).
There are exactly 2 possibilities when 1 or 2 countries are located on
external border.
Figure 3-Two adjacent countries
Option 2: 3 countries can touch directly and converge in one
point.
Since all countries have 2 neighboring countries, 3 colors are needed
(Figure 5).
Figure 4-Three adjacent countries
16
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev (lochchinbek1992@gmail.com)
There are 3 different options for where on the outer border
there are 1, 2, or 3 countries located.


Option 3: It is also possible that 4 countries converge at the same point: in
in this case, you will need 2 colors, but there are only 2 options left. Because
each country has 3 neighboring countries, we need 4 colors.
Figure 5-4 related countries
Answering the question: how many countries are directly adjacent to each other
(i.e., each country shares a common border with the others), one can answer that
the maximum number of such countries is 4.
Then, for paints, the following pattern follows: (Fig. 7a) for n even colors,
3 colors are enough for splits (this is for maps formed by two colors).
concentric circles). And for maps with an odd number of countries
converging at a single point, for n odd partitions (Fig. 7b) - 4 colors
(for maps formed by two concentric circles). Here
note that for maps with an even number of countries (converging in
one point) 4 or more always need 2 colors.
Figure 6-Pattern of paint distribution
17
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev (lochchinbek1992@gmail.com)
Thus, we can draw the following conclusion: By coloring the maps
with a different number of adjacent countries, will meet mainly 2-
x, 3-color options. Sometimes you will need the 4th color. And the fifth - never. The 
theorem
proven.
18
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev (lochchinbek1992@gmail.com)

Download 0,64 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish