مبرهنة الألوان الأربعة

مبرهنة الألوان الأربعة
تلوين رباعي لخريطة حقيقية لولايات الولايات المتحدة تتجاهل ألوان الماء والبلدان الأخرى والكتابة).

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

مبرهنة الألوان الأربعة

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

Example of a map of Azerbaijan with non-contiguous regions
4CT Inadequacy Example.svg


Four Colour Planar Graph.svg


برهان منطقي

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

البرهنة

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

Suppose v, e, and f are the number of vertices, edges, and regions. Euler's formula states ve + 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 vn is the number of vertices of degree n and D is the maximum degree of any vertex,

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


Recall the formula above:


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

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

مخطط مرتبط بالخريطة

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

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

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

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

نقوض خاطئة

4CT Non-Counterexample 1.svg
4CT Non-Counterexample 2.svg
This map has been colored with five colors... ...and it is necessary to change at least four of the ten regions to obtain a coloring with only four colors.


تعميمات

By joining the single arrows together and the double arrows together, one obtains a torus with seven mutually touching regions; therefore seven colors are necessary
This construction shows the torus divided into the maximum of seven regions, every one of which touches every other.


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

(Weisstein).

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 6 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 7 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

المراجع


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

وصلات خارجية