Lüğət

Soldakı açar sözlərdən birini seçin ...

Qrafiklər və ŞəbəkələrXəritə Boyama

Oxumaq vaxtı: ~15 min

Artıq müəyyən xəritələrlə qrafik nəzəriyyəsindən istifadə etmişik. Böyüdükcə fərdi yollar və körpülər yox olur və əvəzində bütün ölkələrin konturlarını görürük.

Xəritəni rəngləyərkən - və ya ayrı bölgələrdən ibarət hər hansı bir rəsm - qonşu ölkələr eyni rəngə sahib ola bilməzlər. Mümkün qədər az fərqli rənglərdən istifadə etmək istəyə bilərik.

Şahmat taxtası kimi bəzi sadə "xəritələrə" yalnız iki rəng (qara və ağ) lazımdır, lakin mürəkkəb xəritələrin daha çoxuna ehtiyac var.

ABŞ ştatlarının xəritəsini rənglədikdə 50 rəng açıqca kifayətdir, lakin daha az sayda zəruridir. Aşağıdakı xəritələri mümkün qədər az rənglə rəngləməyə çalışın:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

Bu xəritələrin hamısı cəmi dörd fərqli rəng ilə rənglənə bilər, lakin digər, çox mürəkkəb xəritələrin daha çox rəngə ehtiyacı olacağını təsəvvür etmək çətin deyil. Əslində, bəzi xəritələrdə bir-birinə bağlı dörd ölkə olduqda ən az dörd rəng lazımdır.

Əvvəllər olduğu kimi, ölkələr və sərhədlər ilə bir xəritəni planar qrafikə çevirə bilərik: hər ölkə olur ölkələr bir kənar ilə bağlanır:

İndi bir grafiğin uclarını rəngləndirmək istəyirik və iki ucu bir kənar ilə bağlanarsa fərqli rəngə sahib olmalıdır.

1852-ci ildə botanika tələbəsi Francis Guthrie İngiltərədəki ölkələrin xəritəsini rəngləməli oldu. Dörd rəngin cəhd etdiyi hər bir xəritə üçün kifayət qədər göründüyünü müşahidə etdi, lakin bütün xəritələr üçün işləyən bir sübut tapa bilmədi. Bu son dərəcə çətin bir problem oldu və dörd rəng teoremi kimi tanındı.

Sonrakı 100 il ərzində bir çox riyaziyyatçı dörd rəng teoreminə yalnız "sonradan tapılan səhvlər üçün" sübutlar nəşr etdi. Bu etibarsız sübutlardan bəziləri o qədər inandırıcı idi ki, səhvləri tapmaq üçün 10 ildən çox vaxt lazım idi.

Uzun müddət riyaziyyatçılar ya dörd rəngin kifayət olduğunu sübut edə bilmədi, ya da dörd rəngdən çox ehtiyacı olan bir xəritə tapa bilmədilər.

1976-cı ilədək Wolfgang HakenKenneth Appel bir kompüterdən nəhayət onu həll etmək üçün istifadə etdikdə dörd rəng problemi üzərində az irəliləyiş əldə edildi. 1936 xüsusi xəritəyə sonsuz sayda xəritəni azaltdılar, bunların hər biri bir kompüter tərəfindən cəmi 1000 saatdan çox çəkdi.

Dörd rəng teoremi, kompüter istifadə edərək sübut edilmiş ilk məşhur riyazi teoremdir, bu gündən bəri daha çox yayılmış və daha az mübahisəli bir şeydir. Daha sürətli kompüterlər və daha səmərəli bir alqoritm deməkdir ki, bu gün dörd rəng teoremini noutbukda bir neçə saat ərzində sübut edə bilərsiniz.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

Dörd rəng teoremi yalnız düz bir müstəvidə və ya bir sahədəki xəritələr üçün işləyir və bütün ölkələrin vahid bir ərazidən ibarət olduğu yerdir.

Bununla birlikdə riyaziyyatçılar, ölkələrin çoxlu bir-birindən ayrılan komponentlərdən ibarət ola biləcəyi imperiyaların xəritələrinə və torus (donut forması) kimi fərqli formalı planetlərin xəritələrinə də baxdılar. Bu hallarda dörddən çox rəngə ehtiyacınız ola bilər və sübutlar daha da çətinləşir.

This map on a torus requires seven colours.