你好，我是米田寬峻（square1001）！

這是我自上一則文章〈直覺就能懂的啟發式問題羅盤 ～從貪婪法到爬山法～〉以來，睽違 4 年在 Qiita 發文。

我也已經成為研究所碩士二年級生，開始投入最前沿的研究，主要從事演算法領域的研究。因此，在本文中，我想讓大家也能感受到 演算法最前沿研究的世界到底是什麼樣子？ 的一部分風貌。

也許有人會覺得，像演算法這樣偏理論的研究很難，普通人根本無法理解，但

• 本文介紹的研究主題屬於容易說明的類型
• 一般的 IT 工程師，甚至喜歡程式設計或數學的高中生，也能在沒有特別前置知識的情況下充分理解

所以希望大家能輕鬆閱讀。

目次

章**標題**1研究成果的介紹2與現實世界相關的圖結構3四色定理的歷史4"平衡版" 四色定理與演算法5結語1. 研究成果的介紹

本文要介紹的是我於 2026 年 7 月投稿的論文 The Balanced Four-Color Theorem。這是與米田優峻氏 (@e869120)1 以及指導教授河原林健一老師 2 的共同著作。

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda. "The Balanced Four-Color Theorem". To appear at ACM-SIAM Symposium on Discrete Algorithms (SODA 2027). https://arxiv.org/abs/2607.13025

前幾天，這篇論文已被演算法領域的頂尖國際會議 SODA 2027 接收了！

關於四色定理

大家有聽過四色定理嗎？這個定理說的是「任何地圖都能用 4 種顏色區分塗色」，是數學上最有名的成果之一。為了讓大家有感，我們來試著看看日本地圖是否能用 4 色塗色。

（日本地圖取自パワポでデザイン的網頁）

答案：日本地圖用 4 色塗色的一個例子如下。

補充：為什麼不能用 3 色？埼玉、東京、神奈川、山梨、長野、靜岡這 6 個都縣的相鄰關係如下圖所示，形成了 1 個都縣周圍被 5 個都縣像環一樣包圍的形狀。

如果想用紅、藍、綠 3 色塗地圖，那麼若把山梨縣塗成紅色，其他 5 個都縣就必須用藍、綠 2 色來塗。這 5 個都縣必須交錯使用藍與綠，但因為 5 是奇數，所以這是不可能的。這就是無論如何都需要 4 色的原因。

四色定理是在 1976 年（正好 50 年前！）由 Appel 與 Haken 證明的。關於一路走到這裡的漫長而深遠的歷史，我會在本文第 3 章說明。

不過，我認為這樣還不夠。雖然四色定理告訴我們地圖可以用 4 色塗色，但我想在其中找到更「順手」的塗法！特別是，我們研究的是能找到多麼 顏色分配均衡的塗法。

研究成果的介紹

本研究得到的主要結果，嚴格表述如下。

本研究的主結果：「平衡版」四色定理

對於任意具有 $n \geq 3$ 個頂點的平面圖，必定存在一種 4 著色，使得任何顏色使用的頂點數都不到 $n/2$。而且可以用計算量 $O(n \log n)$ 求出這種 4 著色。

換句話說，以地圖來說就是：任何至少有 3 個區域的地圖，都可以用 4 色塗分，而且每種顏色所使用的區域數都不到全部的一半；此外，還有能快速求出這種塗法的演算法。

另一方面，對任何 4 色塗法，都存在某些地圖會讓某一種顏色幾乎用到一半。例如，若以下這樣的地圖要用紅、藍、綠、黃 4 色塗分，當把區域 1 塗成紅色、區域 2 塗成藍色時，其他區域就必須交錯塗成綠與黃，因此某一種顏色所使用的區域數會是：

• 當 $n$ 是偶數時，$(n-2)/2$ 個
• 當 $n$ 是奇數時，$(n-1)/2$ 個

因此，前述的「平衡版四色定理」也同時給出了對所有 $n \geq 3$，地圖能被塗得多麼均衡的 完整極限。3

2. 與現實世界相關的圖結構

到目前為止我們一直在談地圖，但在資訊科學中，更一般地會把事物之間的連結以 圖結構 來思考。不只地圖，例如鐵路路線圖、SNS 的朋友關係、分子結構等等，很多事物都可以用圖來表示。

在圖結構的世界裡，我們如下圖所示，把事物簡化為 頂點（vertex），把事物之間的連結簡化為 邊（edge）。依用途不同，也可能像鐵路路線的例子一樣，在邊上加上表示所需時間的長度值等額外資訊。

之所以把前面那些例子以及更多東西視為「圖」這種抽象結構很方便，是因為利用圖，我們可以用電腦解出在 2.1、2.2 節中會提到的各種問題，而每一個問題都有各式各樣的應用。

2-1. 用圖來解的問題

這裡為了讓大家對圖能用在哪些問題上有個概念，介紹 3 個問題。

例 1. 最短路徑問題

最短路徑問題是要找出圖中兩個頂點之間的最短路徑。比如前面鐵路路線的例子中，從 A 站到 F 站的最短路徑是 A → B → C → D → F，所需時間為 41 分鐘。

另外，大家之中或許有人會在意：鐵路路線的例子中似乎沒有把轉乘時間考慮進去吧？但即使要考慮轉乘時間，也可以用最短路徑問題求出。

補充：要怎麼考慮轉乘？如果想考慮同一車站間兩條路線的轉乘時間，可以把那兩條路線的車站視為「不同的車站（= 不同的頂點）」，然後在那兩個頂點之間加入長度等於轉乘時間的邊即可。

以上面的例子來說，如果山手線與中央線在 B 站轉乘要 4 分鐘、在 D 站轉乘要 8 分鐘，則可用下圖的圖來建模。在這種情況下，從 A 站到 F 站的最短路徑變成 A → B1 → B2 → E → F，所需時間為 47 分鐘。你可以看到，和剛才不同的路徑變成了最短路徑。

最短路徑問題在有 $n$ 個頂點、$m$ 條邊的圖上，已知有能以計算量 $O(m \log n)$ 快速求解的 Dijkstra 演算法。擅長程式設計的人，或上過演算法課程的人，應該有些人聽過。

例 2. 配對問題

配對問題是：在圖中最多能選出多少條邊，且任兩條邊都不能相鄰（= 不能共用同一個頂點）。直觀來說，就是把前面那個朋友關係圖中的朋友兩兩配成一對時，最多可以配出多少對，這是一樣的問題。

這不只適用於朋友關係，更能用在更一般的實務場景。例如，學生求職時向多家公司投遞履歷，而每家公司只能錄取 1 名學生時，最多能有多少人進入公司，就會變成配對問題。以下圖的例子來說，可以配對 6 條邊，因此可以讓沒有成功就職的學生為零。

配對問題在有 $n$ 個頂點、$m$ 條邊的圖上，已知有可用計算量 $O(m \sqrt{n})$ 快速求解的演算法。4

例 3. 圖著色問題

圖著色問題是：請將圖中的每個頂點塗色，使得每一條邊連接到的兩個頂點顏色都不同，並且盡量使用較少的顏色。作為例子，下面這兩個圖各自可以用幾種顏色塗呢？

答案：能用幾色塗？左圖可以用 3 色，右圖可以用 2 色。

2-2. 關於圖著色問題

圖著色問題是演算法領域最前沿中研究特別多的問題之一。原因在於，和最短路徑問題或配對問題不同，目前還不知道有高效率的演算法。即使是現在已知最快的演算法，計算量也要 $O(2^n)$。也就是說，就算是 $n = 100$ 頂點這種相對不大的圖，也無法在實際可行的計算時間內求得最佳答案。因此，還有很多事情尚未明朗，是很重要的研究對象。5

應用上的重要性

另一方面，圖著色問題也有許多應用。代表性的就是排程。比如有一些工作，而其中某兩項工作因為時間重疊等原因不能分配給同一個人時，我們想找出用最少人力完成全部工作的方式。這就會變成圖著色問題：把每個工作視為頂點，把不能分配給同一個人的兩個工作用邊連起來。

例如，上圖的例子中，最少需要 3 人。也就是讓員工 A 做工作 1、4，員工 B 做工作 3、6，員工 C 做工作 2、5、7 即可。

"平衡" 的想法

在圖著色的應用中，不只是得到一個最佳塗法而已，還需要在其中找出「比較合適」的方案。比如在排程問題中，如果某一個人做了太多工作就不好，因此安排 平衡的排程 很重要。

也就是說，要讓各種顏色的頂點數盡量沒有差距的圖著色。本篇文章解說的是「平衡版」四色定理，但我希望大家也能理解，從應用的角度來看，考慮平衡也是很重要的。

3. 四色定理的歷史

本章將說明四色定理的歷史，以及它是如何被證明的背景。

四色定理如前所述，是「所有地圖都能用 4 色塗色」；若用圖的語言來表達，就是 所有平面圖都能用 4 色著色。這裡所謂的 平面圖，是指可以在平面上畫出且邊彼此不相交的圖。

因此，它和 2.2 節介紹的圖著色問題有關；事實上，圖著色問題本身就源自四色問題（19 世紀時尚未被證明，因此當時還不叫四色定理）。

3-1. 四色定理的源頭

1852 年，英國倫敦。當時日本仍是江戶時代，實施鎖國政策（這還比黑船來航早 1 年！），而英國則正值產業革命開始、握有世界霸權的時代。

（圖片來自 https://www.thehistoryoflondon.co.uk/in-brief-late-victorian-london/）

英國數學家 De Morgan（高中一年級數學會學到的「德摩根定律」的那位！）以及他的學生 Guthrie，在為英國地圖分區塗色時想到：「是不是所有地圖都能用 4 色塗分？」四色問題就此誕生。

3-2. 6 色的塗法

四色定理雖然有名又有點惡名昭彰，讓人覺得非常困難，但如果不是 4 色而是允許用 6 色，那就沒那麼難了。先來說明這件事。

Step 1. 平面圖的邊數

首先，作為前提，平面圖不可能有太多邊。實際上，對於頂點數 $n = 3, 4, 5, 6, \dots$ 來試，即使一直增加邊直到不能再加為止，如下圖所示，也只能到 $3, 6, 9, 12, \dots$ 條邊。一般而言，平面圖最多只能有 $3n-6$ 條邊。

定理 1. 任何具有 $n \geq 3$ 個頂點的平面圖，邊數都不超過 $3n-6$。

關於為什麼最多是 $3n-6$ 條邊（證明稍微有點難），要用到 歐拉多面體公式。它說的是，對於畫在平面上且邊不交叉的連通圖，滿足以下等式：

V - E + F = 2

其中，$V$ 是頂點數、$E$ 是邊數、$F$ 是包括「外側」在內的面數（也就是圖內部的面數再加 1）。以剛才那張 6 頂點的圖為例實際數數看，會得到 $V = 6, E = 12, F = 8$，因此可知滿足 $V - E + F = 2$。

這裡，讓我們用兩種方式來數「邊與其相鄰的面」的組數 $c$（這和「面與其所屬的邊」的組數是一樣的！）。

• 每條邊都恰好接觸 2 個面，所以 $c = 2E$。
• 每個面都至少由 3 條邊構成，所以 $c \geq 3F$。

因此可得 $3F \leq 2E$，也就是 $F \leq \frac{2}{3}E$。所以

2 = V - E + F \leq V - E + \frac{2}{3} E = V - \frac{1}{3} E

因為 $V = n$，所以 $n - \frac{1}{3} E \geq 2$，整理後即可得到 $E \leq 3n-6$。

Step 2. 著眼於頂點的度數

圖中與某個頂點相連的邊數，稱為該頂點的 度數（degree）。例如，前面那個 5 頂點 9 邊的圖中，有 2 個度數為 3 的頂點，以及 3 個度數為 4 的頂點。圖的度數有以下性質。

定理 2. 所有頂點度數的總和，等於邊數的 2 倍。

這之所以成立，是因為用一條邊連接頂點 $x, y$ 時，$x, y$ 的度數各自增加 1，所以也就是說「每一條邊都讓度數總和增加 2」。這個性質也因為像兩個頂點握手一樣，所以稱為 握手引理。

接著，將這兩個定理結合起來看看。

定理 3. 任意平面圖一定存在一個度數不超過 5 的頂點。

當 $n \leq 2$ 時顯然成立，因此以下假設 $n \geq 3$。由定理 1 可知平面圖最多只有 $3n-6$ 條邊，因此由定理 2 可知，度數總和最多為 $6n-12$。但如果所有頂點的度數都至少為 6，那麼度數總和就會至少為 $6n$，這就矛盾了。因此一定存在度數不超過 5 的頂點。

Step 3. 平面圖的建構方法

既然知道平面圖一定存在度數不超過 5 的頂點，就可以如下面的圖那樣，反覆刪除度數不超過 5 的頂點（以及連接的邊），直到把所有頂點刪光。

（頂點上寫的數字表示該頂點的度數）

那麼，反過來看呢？如果從空圖開始，每次加入一個新頂點，並把它與不超過 5 條邊連接，如此反覆，就一定能構造出想要的平面圖。

Step 4. 一個一個塗上顏色

考慮依照這種「依序加入新頂點」的順序來決定顏色。

這裡，新加入頂點的度數不超過 5，因此在 6 種顏色中一定會剩下一種可用的顏色（= 與相鄰頂點不同的顏色），所以可以從中選一種喜歡的顏色來塗。如此便知任何平面圖都能用 6 色著色。

定理 4. 任意平面圖都可以用 6 色著色。

3-3. Kempe 的新點子與「五色定理」

自 1860 年代起，許多數學家都嘗試證明四色問題，但全都失敗了。其中，英國數學家 Kempe 在 1879 年想到的新點子 Kempe Chain，使得平面圖可以用 5 色著色的「五色定理」得以證明。

順帶一提，這個 Kempe Chain 的想法，1 個世紀後也被用來證明四色定理。

Step 1. 用 5 色會失敗的情況

首先，前面我們說明了如何把平面圖用 6 色著色，那麼若用同樣的方法改成 5 色，會怎麼樣呢？

• 當新加入的頂點度數不超過 4 時，5 色之中一定會剩下可用顏色
• 就算新加入頂點的度數是 5，只要相鄰頂點的顏色不是「顏色 1、2、3、4、5 各一個」，5 色之中也一定會有可用顏色

因此，所有 5 色失敗的原因，都可歸結為下圖那種特殊情況：相鄰頂點的顏色剛好是「顏色 1、2、3、4、5 各一個」。

Step 2. 用來避開這種情況的 Kempe Chain

為了解決這種狀況，Kempe 想出了一個新點子：透過巧妙改變著色，把「顏色 1、2、3、4、5 各一個」的狀況打破。

例如，若想把新頂點 X 鄰接的一個顏色 1 的頂點 Y 改成顏色 3，但如果 Y 又鄰接著一個顏色 3 的頂點 Z，那就不能直接改。這時就把 Z 改成顏色 1；若 Z 又鄰接一個顏色 1 的頂點 W，就把 W 改成顏色 3，依此類推。

也就是說，把由顏色 1 與顏色 3 的頂點連成的一整個連通部分中的顏色 1 和顏色 3 互換。

不過，若做了這個操作，可能會像下圖那樣，導致與新頂點相鄰的顏色 3 頂點變成顏色 1，結果還是無法解決問題。

這種情況下，就改試著對顏色 2 與顏色 4 做同樣的事。此時，因為與新頂點相鄰的顏色 2 頂點被色 1、3 的「鎖鏈」（Kempe Chain）包住，所以進行操作後，不會發生與新頂點相鄰的顏色 4 頂點變成顏色 2 的情況（也可參考下圖）。如此一來，就知道任何平面圖都能用 5 色著色了。

定理 5.（Kempe 1879） 任意平面圖都可以用 5 色著色。

實際上，Kempe 當時相信自己已經證明了四色問題，周圍的數學家也接受了這個想法。然而 11 年後的 1890 年，數學家 Heawood 指出了 Kempe 證明中的錯誤，才揭示出其實只證到了 5 色而已。

3-4. 通往四色定理的道路

進入 20 世紀後，仍有許多數學家持續研究四色問題。雖然細節略去不談，但過程中出現了以下重要想法：

• 讓證明可歸結到小案例的「可約性（reducibility）」
• 用勢能來討論整個圖性質的「放電法」

基於這些想法，最後在 1976 年真正解開四色問題的是美國伊利諾大學的數學家 Appel 與 Haken。

定理 6.（Appel & Haken 1976） 任意平面圖都可以用 4 色著色。

然而，他們所做的是一個 以電腦進行、包含超過 1000 種龐大分類情形的證明。當時電腦在數學家之間還不算普遍，基於大量程式運算的證明讓全世界都為之震驚。另一方面，也因為這種分類多到人類無法一一驗證，而且如此優美的定理證明卻不夠「優雅」，引起了許多批評，成為 震撼數學界的爭議焦點。

至今 50 年過去，仍然沒有發現不依賴電腦分類的四色定理證明。

4. 「平衡版」四色定理與演算法

這次的研究，針對 50 年前證明的四色定理，探討了下面這個問題。

自然的疑問：有多均衡的 4 色塗法存在？

然而，四色定理的證明複雜得惡名昭彰，因此一開始就想證明與四色定理相關的事實，看起來也非常困難。本章將介紹我們是如何採取方法得到結果的。

4-1. 整體策略

這次研究採取的策略，不是直接深入四色定理那份艱澀的證明，而是 把四色定理當作黑盒使用。具體而言，策略如下：

1. 利用四色定理，先求出任意一種平面圖的 4 色著色
2. 再從這個著色出發，把最大顏色的頂點數量逐步減少，改善著色

在第 1 點方面，已經有 2026 年 3 月由河原林健一教授，以及他的指導學生井上裕太氏、宮下敦行氏等共 6 位研究者發表的論文 論文，提出了在計算量 $O(n \log n)$ 內求出平面圖 4 色著色的演算法，因此我們直接使用那個結果。至於他們的突破，也刊登在以下 Quanta Magazine 文章中，有興趣的話也很推薦閱讀：

Quanta Magazine, "The Four-Color Theorem Gets a Rare New Proof", 2026 年 9 月 10 日
https://www.quantamagazine.org/the-four-color-theorem-gets-a-rare-new-proof-20260910/

4-2. 「3 分之 2」的證明

一開始就想求出「每種顏色都不到全部一半」的塗法或許有點難，但如果不是一半，而是「3 分之 2」，那就相對簡單。因此先介紹這個方法。

Step 1. 改善部分要怎麼做？

設平面圖已用色 1、色 2、色 3、色 4 這 4 色著色，且使用最廣的顏色是色 1。此時，考慮不斷重複以下改善操作，直到無法繼續為止。

• 操作： 選一個色 1 的頂點 $v$，把它改成色 1 以外的某個顏色（記為色 $i$）。但這個操作只能在 $v$ 沒有與色 $i$ 的頂點相鄰時進行。

重要觀察是：在再也無法改善的圖中，所有色 1 頂點都會分別與色 2、3、4 的頂點相鄰。

Step 2. 著眼於二分圖結構！

在前面的觀察中，我們只在意色 1 頂點與色 2、3、4 頂點之間的關係，因此考慮只保留連到色 1 頂點的邊所形成的圖（稱為圖 $H$）。它會像下圖這樣。

這個新圖 $H$ 會是 二分圖。所謂二分圖，是指當把頂點分成兩群 A、B 時，每一條邊都能連接 A 與 B 兩群的圖。

• 具體例子來說，2.1 節中的學生與公司配對圖，以及表示男女之間朋友關係的圖，都是二分圖。
• 圖 $H$ 只要把色 1 頂點當作群組 A、色 2、3、4 頂點當作群組 B，就會形成所有邊都連接 A 與 B 的圖，因此是二分圖。

這裡，平面二分圖能容納的邊比一般平面圖更少。如下圖所示，最多只能有 $2n-4$ 條邊。原因是平面二分圖中不能存在三角形面，所以每個面至少要由 4 個頂點構成。

定理 7. 任何具有 $n \geq 3$ 個頂點的平面二分圖，邊數都不超過 $2n-4$。

關於為什麼最多是 $2n-4$ 條邊（證明稍微有點難），這裡沿著 3.2 節中說明平面圖最多只有 $3n-6$ 條邊的方式來說明。

首先，平面二分圖不存在三角形面。因為三角形不是二分圖。所以所有面至少由 4 條邊構成，因此（相對於一般平面圖的 $3F \leq 2E$），有 $4F \leq 2E$。也就是 $F \leq \frac{1}{2}E$。因此

2 = V - E + F \leq V - E + \frac{1}{2} E = V - \frac{1}{2} E

由於 $V = n$，所以 $n - \frac{1}{2} E \geq 2$，整理後就得到 $E \leq 2n-4$。

Step 3. 最後一步

那麼，既然準備到這裡了，就開始證明「3 分之 2」吧！

先令色 1 頂點的個數為 $k$。若已經無法再進行改善操作，那麼每個色 1 頂點都連到色 2、3、4 的頂點，因此在圖 $H$ 中它們的度數也都至少是 3。於是圖 $H$ 的邊至少有 $3k$ 條。

另一方面，由定理 7 可知，圖 $H$ 的邊最多只有 $2n-4$ 條。因此有 $3k \leq 2n-4$。整理後得到 $k \leq \frac{2}{3} n - \frac{4}{3}$，因此可以知道，在無法再改善的狀態下，色 1 的頂點數不到總數的 3 分之 2。

定理 8. 對於任意具有 $n \geq 3$ 個頂點的平面圖，必定存在一種 4 著色，使得任何顏色使用的頂點數都不超過 $\frac{2}{3} n - \frac{4}{3}$。

然而很遺憾，這個方法最多就只能到 3 分之 2。像下面這樣的圖著色狀態中，色 1 佔了幾乎總數的 3 分之 2，但卻沒有任何頂點可以改成別的顏色。

4-3. Kempe Chain 再度登場

到這裡已經很清楚，單純把色 1 頂點改成其他顏色來改善的方法有極限。因此，必須想出更好的改善方式。特別是，必須做到 透過改變別的頂點顏色，讓色 1 頂點可以改成其他顏色。

那麼，我們考慮以下新的改善方式：

• 選取由色 1 與色 $i \ (\neq 1)$ 的頂點連成的一個連通部分。
• 對這些頂點，交換色 1 與色 $i$。

仔細一看，這正是 3.3 節用來證明五色定理的 Kempe Chain 想法再次出現了。借用這個名稱，我們把這種改善方式稱為 Kempe Change。

4-4. 為什麼可以改善？

其實，若反覆使用這種方法，可以證明當無法再改善時，任何顏色都只會使用少於全部一半的頂點。本節將直觀說明原因。

什麼情況下會「無法改善」？

首先，Kempe Change 無法改善的代表性情況是，色 1 與色 $i$ 的所有頂點本來就已經連成一個連通部分。在這種情況下，就算做 Kempe Change，也只是讓所有色 1 頂點變成色 $i$、所有色 $i$ 頂點變成色 1，所以最大顏色的頂點數不會改變。

把這件事更數學化地寫出來。如下定義圖 $H_2, H_3, H_4$。

• $H_i \ (i = 2, 3, 4)$：由色 1 與色 $i$ 的頂點及其連接邊構成的圖

此時，如果 $H_2, H_3, H_4$ 全部都是 連通6 的，就無法改善。（以下圖的例子中，$H_2, H_3, H_4$ 都不是連通的，因此可以透過 Kempe Change 改善）

圖的連通性

對於有 $k$ 個頂點的圖，要使其連通，至少需要 $k-1$ 條邊。原因是，在完全沒有邊的狀態下，會有 $k$ 個塊（數學上稱為「連通分量」）；而每加入一條邊，就能把兩個塊合併成一個，使塊的數量減少 1。連通圖只有一個塊，所以需要 $k-1$ 條邊。

定理 9. 任何具有 $k \geq 1$ 個頂點的連通圖，邊數都至少為 $k-1$。

來計算看看吧

那麼，這種情況到底在色 1 頂點有多少個時可能發生呢？我們實際算算看。

• 設色 1、2、3、4 的頂點數分別為 $c_1, c_2, c_3, c_4$。
• 那麼，$H_2, H_3, H_4$ 的頂點數分別為 $c_1 + c_2, c_1 + c_3, c_1 + c_4$。
• 由於 $H_2, H_3, H_4$ 都是連通的，所以依定理 9，其邊數分別至少為 $c_1 + c_2 - 1, c_1 + c_3 - 1, c_1 + c_4 - 1$。
• 圖 $H$ 是由圖 $H_2, H_3, H_4$ 組合而成，所以它的邊數等於 $H_2, H_3, H_4$ 的邊數總和。因此，$H$ 的邊數至少為：

\begin{align*}
(\text{$H$ 的邊數}) \geq \ & (c_1 + c_2 - 1) + (c_1 + c_3 - 1) + (c_1 + c_4 - 1) \\
= \ & 2c_1 + (c_1 + c_2 + c_3 + c_4) - 3 \\
= \ & 2c_1 + n - 3
\end{align*}

• 另一方面，由於 $H$ 是平面二分圖，所以依定理 7，邊數最多只有 $2n-4$。
• 綜合以上，可得 $2c_1 + n - 3 \leq 2n-4$。整理後得到 $c_1 \leq \frac{n-1}{2}$。

因此已證明：當色 1 佔總數的一半以上時，$H_2, H_3, H_4$ 全部都連通的情況 根本不可能發生。這就是「平衡版」四色定理成立的直觀理由。

此外，即使其中某個圖不是連通，也仍然存在 Kempe Change 無法改善的情況，但那時會因為另一種理由而吃虧。這比較難，不過用專業但簡單的方式來說，就是對某個 $H_i \ (i = 2, 3, 4)$ 的某個連通分量 $C$，會出現「色 1 頂點數不超過色 $i$ 頂點數」這種反轉現象。如此一來，不是 $C$ 中出現環導致邊被浪費，就是 $H$ 中出現度數 1 的頂點導致能放進整個 $H$ 的邊數變少，無論哪一種都會因此吃虧。至於具體證明，請參考論文。

4-5. 高速的演算法

最後來看，要多快才能求出足夠平衡的 4 色塗法，也就是演算法的時間複雜度。

首先，每一次改善都至少會讓最大顏色的頂點數減少 1，因此最多經過 $n/2$ 次改善，就能讓最大顏色的頂點數少於 $n/2$。另外，每次改善可以在 $O(n)$ 時間內完成（細節略去，但只要建立圖 $H_2, H_3, H_4$ 並找出所有連通塊即可，可用深度優先搜尋（DFS）等方法實現）。因此整體時間複雜度為 $O(n^2)$。

那麼，還能不能更快呢？

想法：最大顏色的頂點越多越有利

重點在於，即使最大顏色的頂點數 $c_1$ 接近 $n/2$，$H_2, H_3, H_4$ 其中之一也不會是連通的。此外，若 $c_1$ 遠遠超過 $n/2$，那麼 $H_2, H_3, H_4$ 會被分成大量連通塊。在這種情況下，對幾個連通塊同時做 Kempe Change，就可以把兩種顏色的頂點數調得更平均。

指數式改善

利用這個想法，每次改善都可以把 $c_1 - n/2$ 變成前一個的 $\frac{3}{4}$。於是如下圖所示，經過 2 次變成 $\frac{9}{16}$ 倍、3 次變成 $\frac{27}{64}$ 倍，……會 指數式地減少，大約經過 $\log n$ 次改善後，最大顏色的頂點數就會小於 $n/2$。

如此一來，就把改善著色部分的時間複雜度降到 $O(n \log n)$。而求出最初的 4 色著色，正如 4.1 節所述，已有既有研究可做到 $O(n \log n)$，所以整體而言也能在 $O(n \log n)$ 的時間內求得答案。

以上就是本研究的主要結果——「平衡版」四色定理的介紹。

5. 結語

感謝大家閱讀本文！

希望透過這篇文章，能讓大家對演算法領域最前沿研究在做些什麼有一點印象。也許有人原本以為這類理論研究很難，甚至連研究內容都看不懂；但其實像「平衡版」四色定理這樣讓人感到親近的主題，也確實存在於最前沿的理論研究之中。

話說回來，這個「地圖能多均衡地用 4 色塗？」的問題，我覺得是非常自然的疑問，但現實上，過去的研究者似乎並沒有把它當作「未解問題」提出或思考。7

由於方法與證明在演算法領域中算是相對簡單，如果四色定理在 1980 年左右就已被解開，那我認為這個問題大概在 1990 年左右就會被解決了。我體會到，即使是這樣自然的疑問，其中也可能隱藏著我們尚未發現的有趣性質與演算法。對我來說，研究活動不只是解題，能夠找到這樣的問題本身也是很有趣的。

1. 米田優峻氏 (@e869120) 也在 Qiita 上發表了許多熱門文章，例如〈紅色程式設計師教你，競技程式設計・AtCoder 成長指南〉等，同時也以書籍《為解決問題打下扎實基礎的「演算法 × 數學」入門書》、《競技程式設計的鐵則》、《150 分鐘搞懂高中數學基礎》[等]而廣為人知。 ↩
2. 河原林健一教授是演算法領域日本最傑出的研究者之一。包括發現 最小割問題的準線性時間演算法（獲得 2021 年 Fulkerson Prize）在內，創造了許多重大突破。 ↩
3. 在這個圖的例子中，當 $n = 3, 4, 5, 6, 7, 8, 9, 10, \dots$ 時，某一種顏色會分別占據 1, 1, 2, 2, 3, 3, 4, 4, ... 個區域。另一方面，平衡版四色定理則指出，可以用 4 色塗色，使某一種顏色只會用在 1, 1, 2, 2, 3, 3, 4, 4, ... 個區域上。也就是說，對所有 $n \geq 3$，上界（= 演算法的性能）與下界（= 演算法的極限）是一致的。 ↩
4. 配對問題中著名的是增廣路徑演算法，而對於時間複雜度為 $O(m \sqrt{n})$ 的快速演算法，二分圖有 Hopcroft-Karp 演算法，一般圖則有 Micali-Vazirani 演算法。 ↩
5. 對於像圖著色這樣尚無法有效率地（= 多項式時間內）求解的問題，也可以研究：哪些圖可以有效率地解，或是即使不要求完全最佳答案，也能高效率地得到某種不錯的近似解等，各種研究主題都會出現。 ↩
6. 圖是連通的，意思是從任一頂點都能沿著邊到達任一其他頂點。 ↩
7. 至少就我查到的範圍內，沒有任何論文在思考一般平面圖究竟可以被多均衡地著色。 ↩

原文出處：https://qiita.com/square1001/items/4714dd9e2ddb97c32057