شبکهٔ رنگیِ دو‌رنگ و قضیهٔ چهار رنگ

همسایگی یعنی ضلع مشترک

در این شبکه، دو ناحیه وقتی مجاور حساب می‌شن که یک ضلع کامل بینشان مشترک باشه. دو خانه‌ای که فقط در گوشه به هم می‌رسن، همسایه نیستن؛ پس می‌تونن یک رنگ داشته باشن.

چرا شبکه دو رنگ می‌خواد؟

k = (r+c) mod 2; C_grid = 2

خانه‌ها مثل صفحهٔ شطرنج یکی‌درمیون رنگ می‌گیرن. با هر حرکت افقی یا عمودی، رنگ عوض می‌شه؛ پس هیچ دو خانهٔ ضلع‌مشترکی هم‌رنگ نمی‌شن. دو رنگ برای این شبکه کافی است.

تعداد خانه‌ها با اندازهٔ شبکه

n = d+1; R = n*n

اگر در هر ردیف n خانه باشه و شبکه n ردیف داشته باشه، تعداد ناحیه‌ها n در n است. این ویجت برای پیچیدگی c، شبکه‌ای با c+1 خانه در هر ردیف و ستون می‌سازه.

عدد مرزها چی رو می‌شمره؟

B = 2*n*(n-1)

کارت مرزها فقط ضلع‌های مشترکِ دو ناحیه رو می‌شمره و هر ضلع مشترک رو یک بار حساب می‌کنه. دورِ بیرونی شبکه جزو این عدد نیست.

قضیهٔ چهار رنگ یک حد بالاست

C_planar <= 4

قضیهٔ چهار رنگ دربارهٔ همهٔ نقشه‌های مسطح می‌گه حداکثر چهار رنگ کافیه تا هر دو ناحیهٔ ضلع‌مشترک رنگ متفاوت داشته باشن. این شبکه فقط یک نمونهٔ ساده‌ست که با دو رنگ حل می‌شه؛ شکل‌های پیچیده‌تر در این ویجت قابل ساخت نیستن.