مبرهنة الألوان الأربعة تنص على أنه يمكن لأي مستوى مقسّم إلى عدّة مناطق حتى يلّون فقط بأربعة ألوان على أكثر تقدير, بحيث لا تلون منطقتان متجاورتان (لهما نفس الحدود) بنفس اللون، إلا في حالة تشاركهما في نقطة واحدة.

صياغة دقيقة للمبرهنة

برهان منطقي

• الفكرة العامة هوحتى أي منطقة إذا كانت محاطة بعدد زوجي من المناطق فإننا نحتاج فقط لعدد ثلاثة ألوان لتلوين المنطقة والمناطق المحيطة بها مباشرة - لون 1 للمنطقة نفسها - لون 2 لأول منطقة من المناطق المحيطة بها ثم لون ثلاثة للمنطقة التالية من المناطق المحيطة إلى غير ذلك بالتبادل 2 ثم ثلاثة وتنتهي أخر منطقة باللون ثلاثة دون وجود منطقتين متجاورتين لهما نفس اللون .
• أم إذا كانت المنطقة محاطة بعدد فردي من المناطق فنحتاج لأربعة ألوان فقط واللون الرابع لتلوين المنطقة الأخيرة والتي ترتيبها فردي حيث تليها المنطقة الأولي والتي ترتيبها فردي أيضا ومن ثم فإن أقصي عدد من الألوان المتنوعة والتي تلزم لتلوين خريطة تضم عددا من المناطق هوأربعة ألوان فقط

البرهنة

ملخص أفكار البرهنة

Suppose v, e, and f are the number of vertices, edges, and regions. Euler's formula states v − e + f = 2. This together with the fact that each edge is shared by two regions, 2e = 3f, can be used to show 6v − 2e = 12. Now, the degree of a vertex is the number of edges abutting it. If v_n is the number of vertices of degree n and D is the maximum degree of any vertex,

${\displaystyle 6v-2e=6\sum _{i=1 ^{D v_{i -\sum _{i=1 ^{D iv_{i =\sum _{i=1 ^{D (6-i)v_{i =12.$

But since 12 > 0 andستة − i ≤ 0 for all i ≥ 6, this demonstrates that there is at least one vertex of degreeخمسة or less.

Recall the formula above:

${\displaystyle \sum _{i=1 ^{D (6-i)v_{i =12.$

من الممكن، ربط مأزق الألوان الأربعة، بمشكلة تلوين المخطط

نربط جميع رسم, بمخطط عادي جميع رأس يمثل منطقة, ويتم ربط الرؤوس التي تمثل مناطق لها نفس الحدود.

هذا يعني حتى تلوين الخريطة مرتبط بتلوين المخطط المستوي المرتبط بالخريطة. وهكذا تكون خوارزمية التلوين كما يلي:

خوارزمية التلوين

ملاحظة: نستعمل الأرقام 1، 2، ثلاثة وأربعة للتعبير عن الألوان الأربعة.

1. رسم المخطط المستوي المرتبط بالخريطة.
2. نأخد مثلثا ونلون رؤوسه بالألوان 1، 2 و3.
3. انطلاقا من هذا المثلث نحاول تلوين القمم باستعمال الألوان الثلاث الأولى.(سيكون التلوين في هذه الحالة إجباريا).
4. نأخد مثلثا آخر غير ملون ونعيد المرحلتين رقم 2 و3.
5. نستعمل اللون الرابع فقط في الحالة التي تكون فيها قمة ما مرتبطة في آن واحد بثلاثة قمم ذات ثلاثة ألوان مختلفة.
6. نعود للخريطة ونلونها حسب الألوان المحصل عليها.

نقوض خاطئة

تعميمات

Alternatively, for an orientable surface the formula can be given in terms of the genus of a surface, g:

${\displaystyle p=\lfloor \frac{7+\sqrt{1+48g}}{2}\rfloor }$

This formula, the Heawood conjecture, was conjectured by P.J. Heawood in 1890 and proven by Gerhard Ringel and J. T. W. Youngs in 1968. The only exception to the formula is the Klein bottle, which has Euler characteristic 0 (hence the formula gives p = 7) and requiresستة colors, as shown by P. Franklin in 1934 (Weisstein).

For example, the torus has Euler characteristic χ = 0 (and genus g = 1) and thus p = 7, so no more thanسبعة colors are required to color any map on a torus. The Szilassi polyhedron is an example that require seven colors.

A Möbius strip also requires six colors (Weisstein).

انظر أيضاً

Graph coloring

the problem of finding optimal colorings of graphs that are not necessarily planar.

Grötzsch's theorem

triangle-free planar graphs are 3-colorable.

Hadwiger–Nelson problem

how many colors are needed to color the plane so that no two points at unit distance apart have the same color?

List of sets of four countries that border one another

Contemporary examples of national maps requiring four colors

المراجع

• Allaire, F. (1997), "Another proof of the four colour theorem—Part I", Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer. 20: 3–72 
• Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable", Illinois Journal of Mathematics 21: 439–567 
• Appel, Kenneth; Haken, Wolfgang (October 1977), "Solution of the Four Color Map Problem", Scientific American 237 (4): 108–121, doi:10.1038/scientificamerican1077-108 
• Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Providence, RI: American Mathematical Society, ISBN 0821851039 
• Cayley, Arthur (1879), "On the colourings of maps", Proc. Royal Geographical Society (Blackwell Publishing) 1 (4): 259–261, doi:10.2307/1799998, http://jstor.org/stable/1799998 
• Gonthier, Georges (2008), "Formal Proof--The Four-Color Theorem", Notices of the American Mathematical Society 55 (11): 1382–1393, http://www.ams.org/notices/200811/tx081101382p.pdf 
• Gonthier, Georges (2005), A computer-checked proof of the four colour theorem, unpublished, http://research.microsoft.com/~gonthier/4colproof.pdf 
• Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich 88: 133–143 .
• Heawood, P. J. (1890), "Map-Colour Theorem", Quarterly Journal of Mathematics, Oxford 24: 332–338 
• O'Connor; Robertson (1996), The Four Colour Theorem, MacTutor archive, http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html 
• Pegg, Ed, Jr. (2002), "Book Review: The Colossal Book of Mathematics", Notices of the American Mathematical Society 49 (9): 1084–1086, http://www.ams.org/notices/200209/rev-pegg.pdf 
• Ringel, G.; Youngs, J.W.T. (1968), "Solution of the Heawood Map-Coloring Problem", Proc. Nat. Acad. Sci. USA 60: 438–445, doi:10.1073/pnas.60.2.438 
• Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1996), "Efficiently four-coloring planar graphs", Efficiently four-coloring planar graphs, STOC'96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM Press, pp. 571–575, doi:10.1145/237814.238005 
• Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), "The Four-Colour Theorem", J. Combin. Theory Ser. B 70 (1): 2–44, doi:10.1006/jctb.1997.1750 
• Saaty, Thomas; Kainen, Paul (1986), The Four Color Problem: Assaults and Conquest, New York: Dover Publications, ISBN 0-486-65092-8 
• Swart, ER (1980), "The philosophical implications of the four-color problem", American Mathematical Monthly (Mathematical Association of America) 87 (9): 697–702, doi:10.2307/2321855, http://www.joma.org/images/upload_library/22/Ford/Swart697-707.pdf 
• Thomas, Robin (1998), "An Update on the Four-Color Theorem", Notices of the American Mathematical Society 45 (7): 848–859, http://www.ams.org/notices/199807/thomas.pdf 
• Thomas, Robin (1995), The Four Color Theorem, http://www.math.gatech.edu/~thomas/FC/fourcolor.html 
• Thomas, Robin, Recent Excluded Minor Theorems for Graphs, p. 14, http://people.math.gatech.edu/~thomas/PAP/bcc.pdf 
• Eric W. Weisstein, Blanuša snarks at MathWorld.
• Eric W. Weisstein, Map coloring at MathWorld.
• Wilson, Robin (2002), Four Colors Suffice, London: Penguin Books, ISBN 0-691-11533-8 

وصلات خارجية

• The Four Color Problem Gets a Sharp New Hue
• Four color theorem at Citizendium