Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

同じ点の集まりに対して、最小全域木と巡回セールスマン問題という二つの問いがある。本稿が問うのは、なぜ片方だけが難しいのかである。答は、訪れる順序を要求するかどうかである。新しい数学定理も新しい法則も主張しない。

第一に、$n=20$ の巡回路は $6.0823\times10^{16}$ 通りで、一億通毎秒でも $\mathbf{19.2735}$ 年かかる（第2節）。

第二に、同じ $n=20$ の最小全域木は $n^2=400$ 程度の手間で解ける（第2節）。

第三に、これが本稿の芯である。差を作っているのは点の数ではなく、順序を要求するかどうかである（第3節）。

第四に、本体系の引用グラフで実際に測った。$337$ 編が $\mathbf{336}$ 本の辺で全部つながる（第4節）。

第五に、全 $2396$ 辺のうち骨格は $\mathbf{14.0234}$ パーセントで、残る $85.9766$ パーセントは木としては冗長である（第4節）。

第六に、分離子は「順序が要るか、繋がってさえいればよいか」である（第5節）。

射程（何を示さないか）

新しい数学定理も新しい法則も主張しない。巡回路の総数 $(n-1)!/2$、プリム法とクラスカル法、最小全域木の一意性、計算量の分類はいずれも標準的である。計算量理論を作らない。NP 困難性の証明や P と NP の関係には立ち入らない。触れるにとどめる。近似アルゴリズムを扱わない。クリストフィデス法などの近似比には入らない。総当たりの規模だけを見る。重み付きの最小全域木を扱わない。本体系のグラフは重みを持たないので、全域木は最小でも任意でも同じ本数である。重みのある場合の最適化には立ち入らない。体系の内容を評価しない。どの編が重要かという判断はしない。辺の有無だけを数える。大著の構成を決めない。巻分けの提案はしない。数を出すだけである。既刊との関係：論文324 は万能の探索が無いことは問題の数え方の帰結だと示した。そこでも困難さが問題の側ではなく数え方から出ていた。本稿では、同じ点の集まりに対して二つの数え方があり、片方だけが爆発する。論文316 は同じ整数を三つの別の数え方が返すと示した。そこでは数え方が違って答が同じだった。本稿では対象が同じで、要求の強さが違う。論文300 は同根か別根かは判定できると示した。二つの問いは、判定に掛ければ別根である。論文347 は「作図できない」が道具の性質だと示した。そこでは道具が壁を作り、ここでは要求が作る。どちらも困難さの出どころを対象の外に置いている。加えたのは巡回路の総数と全域木の手間を同じ表で並べたこと、本体系の引用グラフで全域木を実際に構成して $336$ 本と測ったこと、辺を半分に減らすと連結でなくなることを確かめて冗長さの意味を限定したこと、分離子を「順序を要求するか」に置いたことである。

1. 記法と問い

設定：$n$ 個の点と、それらを結ぶ辺が与えられている。二つの問いを立てる。

観察 1.1　入力は同じである。同じ点、同じ辺、同じ重み、違うのは、答に何を要求するかだけである。

観察 1.2　そして片方だけが実用的に解ける。最小全域木は $n$ が数万でも解けるが、巡回セールスマンは $n$ が数十で総当たりが破綻する。同じ入力に対する二つの問いが、実行可能性で分かれている。

観察 1.3　本稿の測り方を先に固定する。巡回路の総数は $(n-1)!/2$（出発点の回転と向きの反転を同一視）とし、計算機は一秒に一億通を調べるとする。これは総当たりの規模を測る値であって、実際の最良のアルゴリズムの速さではない。

問い：同じ入力で、なぜ片方だけが難しいのか。

2. $n=20$ で、片方は $400$ 手、もう片方は $19.2735$ 年

検算 2.1：巡回路の総数と、一億通毎秒での所要時間（本稿で計算）。

観察 2.2　自己検査を二つ置く。（a）$n=5$ で巡回路が $12$ 本になり、教科書の値と一致する。（b）$n=10$ で $181440$ 本になり、$9!/2$ と一致する。既知の二件で数え方を確かめてから表を読む。

観察 2.3　$n=15$ から $n=20$ へ、点を五つ足しただけで $435.8915$ 秒が $19.2735$ 年になる。$1.4$ 倍の点数で、時間が $\mathbf{1395360}$ 倍、階乗は、そういう増え方をする。

観察 2.4　$n=30$ では $1.4009\times10^{15}$ 年で、宇宙の年齢の $10$ 万倍である。点が $30$ 個である。紙に描ける規模で、総当たりが宇宙の寿命を超える。

検算 2.5：同じ $n$ で、最小全域木の手間を並べる（プリム法は $n^2$ 程度・本稿で計算）。

観察 2.6　$n$ を $3$ 倍にすると、全域木の手間は $9$ 倍にしかならない。$100$ から $900$ へ、同じ $3$ 倍で、巡回路の総数は $2.4\times10^{25}$ 倍になる。

3. 芯：差を作っているのは、順序を要求するかどうかである

観察 3.1　これが本稿の芯である。最小全域木は「どの辺を使うか」だけを決める。選んだ辺の集合が答であり、辺に順番は付いていない。

観察 3.2　巡回セールスマンは「どの順に訪れるか」を決める。同じ辺の集合でも、辿る順序が違えば別の答である。答が集合ではなく列だから、数え上げが階乗になる。

観察 3.3　そして順序の要求は、貪欲法を壊す。全域木では「今いちばん軽い辺を取る」を繰り返せば最適が出る（クラスカル法）、巡回路では、今いちばん近い点へ行く方針が最適にならない。後で困るからである。

観察 3.4　ここが計算量の分かれ目になっている。全域木は多項式時間で解け、巡回セールスマンは NP 困難である。本稿はその証明には立ち入らないが、分かれ目の位置が「順序」にあることは、総当たりの数え方から見える。

観察 3.5　論文300 の基準に当てる。

観察 3.6　三行とも別根を指している。同じ入力を共有していても、要求の強さが違うだけで、別の問題である。

観察 3.7　論文347 との対をなす。347 は「作図できない」が道具の性質だと書いた。そこでは道具が壁を作り、ここでは要求が作る。どちらも、困難さの出どころを対象の外に置いている。

4. 本体系のグラフで、実際に測る

設定：抽象で終わらせず、実在するグラフで測る。本体系の内部引用グラフを使う。節点は論文、辺は引用である。

検算 4.1：引用グラフを構成し、全域木を作る（本稿で計算）。

観察 4.2　自己検査を三つ置く。（a）全域木の辺数 $336$ が「節点数 $-$ 成分数」$=337-1$ に一致する。（b）連結成分が $1$ 個で、孤立した編が無い。（c）辺を半分に減らすと成分が $79$ 個に割れる。三つ目が効いている。冗長だからといって、どの辺でも捨ててよいわけではない。

観察 4.3　$336$ 本で $337$ 編が全部つながる。全 $2396$ 辺のうち $14.0234$ パーセントである。体系を一つにまとめるだけなら、引用の七分の一で足りる。

観察 4.4　ところが同じ $337$ 点を並べる巡回路は $10^{704.3}$ 通りある。繋ぐのに $336$ 本、並べるのに $10^{704.3}$ 通り、同じ体系に対する二つの問いが、これだけ離れている。

観察 4.5　これは大著の構成という実際の問いに触れている。「どの編とどの編を隣に置くか」は全域木の問いに近く、「全編をどの順に並べるか」は巡回路の問いに近い。前者は計算で出せ、後者は出せない。本稿は巻分けを提案しないが、二つの問いの値段が違うことは数で言える。

観察 4.6　正直に書くべき点、本体系のグラフには重みが無い。だから「最小」全域木と任意の全域木は、辺数において同じである。$336$ という数は連結性から出る数であって、最適化の結果ではない。重みを入れれば、どの $336$ 本を選ぶかが問題になる。

観察 4.7　そして冗長な $85.9766$ パーセントは、無駄ではない。辺を半分に減らしただけで $79$ 個に割れたことがそれを言っている。木として冗長であることと、無くてよいことは別である。冗長さは、どの $336$ 本を選ぶかの自由度になっている。

5. 分離子：順序が要るか、繋がってさえいればよいか

観察 5.1　分離子、答が辺の集合でよいのか、点の列でなければならないのか。

観察 5.2　分離子は、グラフの側にはない。同じ点、同じ辺、同じ重みである。差を作っているのは、答に何を要求したかだけである。

観察 5.3　分離子は動かせる。「一度ずつ訪れる」という条件を外し、同じ点を何度通ってもよいことにすれば、全域木を二度なぞる路が作れる。最短にはならないが、実行可能な答が多項式時間で出る。要求を一つ緩めると、階乗が消える。

観察 5.4　そしてその路の長さは、全域木の二倍を超えない。最適な巡回路は全域木の長さ以上なので、この方法は最適の二倍以内に収まる。難しい問いに答えられなくても、易しい問いの答が保証を与える。

観察 5.5　論文324 との位置関係。324 は万能の探索が無いことは問題の数え方の帰結だと書いた。そこでは困難さが問題の側ではなく数え方から出ていた。本稿では、同じ対象に対して二つの数え方があり、片方だけが爆発する。

観察 5.6　最後に一つ、$336$ と $10^{704.3}$ は、同じ体系についての二つの数である。片方は数秒で出て、もう片方は原理的に数え上げられない。難しさは体系にあるのではなく、こちらが何を要求したかにある。

6. 点呼と結び

1. $n=20$ で $19.2735$ 年（検算2.1）：一億通毎秒で。
2. $n=5$ で $12$ 本、$n=10$ で $181440$ 本（観察2.2）：教科書値と一致。
3. 点を五つ足すと時間が $1395360$ 倍（観察2.3）：階乗の増え方。
4. $n=30$ で $1.4009\times10^{15}$ 年（検算2.1）：宇宙の年齢の $10$ 万倍。
5. 全域木は $n$ を $3$ 倍で手間 $9$ 倍（観察2.6）：巡回路は $2.4\times10^{25}$ 倍。
6. 答が集合か列か（観察3.2）：列だから階乗になる。
7. 本体系 $337$ 編が $336$ 本でつながる（検算4.1）：全 $2396$ 辺の $14.0234$ パーセント。
8. 同じ $337$ 点の巡回路は $10^{704.3}$ 通り（観察4.4）：同じ体系への二つの問い。
9. 辺を半分にすると $79$ 個に割れる（観察4.2）：冗長でも無駄ではない。
10. 一度ずつの条件を外すと階乗が消える（観察5.3）：要求を一つ緩めるだけ。

結び：同じ点と同じ辺に対して、最小全域木と巡回セールスマンという二つの問いがあり、入力は完全に同じで、答に何を要求するかだけが違う。そして片方だけが実用的に解ける。$n=20$ の巡回路は $6.0823\times10^{16}$ 通りで、一億通毎秒でも $\mathbf{19.2735}$ 年かかる。$n=15$ の $435.8915$ 秒から、点を五つ足しただけで $1395360$ 倍である。$n=30$ では $1.4009\times10^{15}$ 年、宇宙の年齢の $10$ 万倍になる。紙に描ける規模で、総当たりが宇宙の寿命を超える。同じ $n=30$ の全域木は $n^2=900$ 程度で済む。差を作っているのは点の数ではない。最小全域木は「どの辺を使うか」だけを決め、答は辺の集合であって順番を持たない。巡回セールスマンは「どの順に訪れるか」を決め、答が列だから数え上げが階乗になる。そして順序の要求は貪欲法を壊す。全域木では今いちばん軽い辺を取り続ければ最適が出るが、巡回路では今いちばん近い点へ行く方針が最適にならない。抽象で終わらせず、実在するグラフで測った。本体系の内部引用グラフは $\mathbf{337}$ 節点・$\mathbf{2396}$ 無向辺で、連結成分は $1$ 個。全域木は $\mathbf{336}$ 本の辺で、全体の $\mathbf{14.0234}$ パーセントである。体系を一つにまとめるだけなら、引用の七分の一で足りる。ところが同じ $337$ 点を並べる巡回路は $\mathbf{10^{704.3}}$ 通りある。これは大著の構成という実際の問いに触れている。「どの編とどの編を隣に置くか」は全域木の問いに近く、「全編をどの順に並べるか」は巡回路の問いに近い。前者は計算で出せ、後者は出せない。分けるものは一つ、答が辺の集合でよいのか、点の列でなければならないのか。分離子はグラフの側にはない。同じ点、同じ辺、同じ重みで、差を作っているのは答に何を要求したかだけである。そして分離子は動かせる。「一度ずつ訪れる」を外して同じ点を何度通ってもよいことにすれば、全域木を二度なぞる路が多項式時間で作れる。最適にはならないが、最適な巡回路は全域木の長さ以上なので、二倍以内に収まることが保証される。難しい問いに答えられなくても、易しい問いの答が保証を与える。正直に書いておく。本体系のグラフには重みが無いので、「最小」全域木と任意の全域木は辺数において同じである。$336$ は連結性から出る数であって、最適化の結果ではない。そして冗長な $85.9766$ パーセントは無駄ではない。辺を半分に減らしただけで成分が $79$ 個に割れた。木として冗長であることと、無くてよいことは別である。最後に一つ、$336$ と $10^{704.3}$ は、同じ体系についての二つの数である。片方は数秒で出て、もう片方は原理的に数え上げられない。難しさは体系にあるのではなく、こちらが何を要求したかにある。

参考文献

1. Boruvka, O. (1926). O jistém problému minimálním. Práce Moravské Přírodovědecké Společnosti, 3.
2. Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1).
3. Prim, R. C. (1957). Shortest Connection Networks and Some Generalizations. Bell System Technical Journal, 36(6).
4. Karp, R. M. (1972). Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations. New York: Plenum.
5. Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Carnegie Mellon University, Management Sciences Research Report 388.
6. 山岸勇輝 (2026). 三百本目の点呼、同根か別根かは、判定できる [論文300]. Zenodo. 10.5281/zenodo.22171914
7. 山岸勇輝 (2026). 同じ整数を、三つの別の数え方が返す [論文316]. Zenodo. 10.5281/zenodo.22208229
8. 山岸勇輝 (2026). 万能の探索が無いことは、問題をどう数えるかの帰結である [論文324]. Zenodo. 10.5281/zenodo.22209395
9. 山岸勇輝 (2026). 「作図できない」は図形の性質ではなく、道具の性質である [論文347]. Zenodo. 10.5281/zenodo.22682365

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「同じグラフで、繋ぐのは安く、並べるのは高い」［論文348］. Zenodo.
DOI: 10.5281/zenodo.22683555

@misc{yamagishi2026yoi348,
  author = {Yamagishi, Yuuki},
  title = {On the Same Graph, Connecting Is Cheap and Ordering Is Not},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/348},
  doi = {10.5281/zenodo.22683555},
  note = {Preprint, edition 1}
}