四色定理に約30年ぶりの新証明、地図を4色で塗り分けるアルゴリズムが大幅に高速化 [すらいむ★]

四色定理に約30年ぶりの新証明、地図を4色で塗り分けるアルゴリズムが大幅に高速化

　どんな地図でも隣り合う地域を同じ色にしないように4色だけで塗り分けられるという「四色定理」について、日本やデンマークなどの研究者からなるチームが新たな証明を発表しました。
　今回もコンピューターを利用した証明ですが、従来とは異なる場所に着目することで、多数の処理をまとめて行えるようになり、実際にグラフを4色で塗り分けるアルゴリズムも大幅に高速化されていると、科学系メディアのQuanta Magazineが解説しています。

（以下略、続きはソースでご確認ください）

Gigazine 2026年09月11日 14時18分
https://gigazine.net/news/20260911-four-color-theory-new-proof/

AIにやらせたの？
それでも構わんけど。

このネタ
笑わない数学で特集してたな

海の色はカウントしないの？

それは証明として不十分ではないのか？
ロジックの積み重ねで証明をして欲しい

ダークマターがカメラ出観測できない理由も解明されるのですか？

>>5
それは最終目標
今回の研究者はやりたいと明言してる

FMラジオの周波数もこれの原理使って、ワイド領域使わなくても元AM放送をFM化すりゃよかったのによ

わざわざワイド用のラジオかわせようとするアホ経産省はほんと老害

>>5
改善したと言ってるだけで
証明したとは何処にも書いてないぞ？

>>5
人間より計算機のほうがはるかにロジックの積み重ねでしょ

>この違いによって、1回の処理でグラフから一定割合の頂点を減らせるようになります。例えば、毎回数個だけ減らす場合はグラフが空に
>なるまで大量の繰り返しが必要ですが、毎回一定割合ずつ減らせるなら、1000個、500個、250個というように急速に問題を小さくできます。

8202種類のパターンの最大サイズは有限だから、それより遥かに大きなグラフでは「毎回一定割合ずつ減らせる」なんてことは有り得ない
わけで、この主張は間違い

>その結果、4色で塗り分けるための計算量は従来のO(n2)からO(nlog_n)へと改善されました。

最大サイズがmとして、頂点数n=m^kのグラフの頂点数をm^(k-1)にする手間はn^2/m程度、つまりO(n^2)だから、改善になってねーじゃん

>>11
え、なに言ってるの？

>>12
見ての通りだけど？

クレペリン検査と

>>14
医療と司法任せらしい
今は浮世絵と鍛え方と回復衰えない充実の時代だけれど
様々な例があるのだろう

プレプリントじゃねえか
読む価値なし
Gigazineソース(笑)