Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

グラフの点を同じ数ずつ二つに分け、間を切る辺をなるべく少なくしたいとき、ラプラシアンの二番目の固有ベクトルの値の大小で分ける方法がよく使われる。本稿は、首の細いグラフ・格子・はしごの横木を後ろ半分だけにした「尾の付いたはしご」で、固有ベクトルの値の中央で分けた切る辺の数を、総当たりで探した最小の二等分と比べる。新しい定理も法則も主張しない。

第一に、首の細いグラフと格子では、固有ベクトルの分け方は最小に当たる。点 $8$ 個の完全グラフ二つを辺 $2$ 本でつないだグラフ（二番目の固有値 $0.417424$）では $2$ 本、$4\times4$ の格子（$0.585786$）では $4$ 本を切り、どちらも最小と同じだった（第2節）。

第二に、尾の付いたはしごでは、最小より多く切る。上下の道が $8$ 点ずつ（二番目の固有値 $0.103300$）なら $4$ 本、$10$ 点ずつ（$0.071278$）なら $5$ 本を切り、最小はどちらも $2$ 本で、比は $\mathbf{2.000000}$・$\mathbf{2.500000}$ だった（第2節）。

第三に、固有ベクトルの分け方は、上の道と下の道を分けていた。二つの大きさとも、中央で分けた二組はちょうど上の道と下の道で、切ったのは横木だった。最小の二等分は、二本の道を尾とはしごの境で左右に切る $2$ 本である（第3節）。

第四に、丸める前と後で、上下と左右の順が入れ替わる。値の差の二乗の和を値の二乗の和で割った量は、固有ベクトルそのもの（丸める前）で $0.103300$・$0.071278$ と最も小さいが、二つの値に丸めると上下の分け方は $1.000000$、左右の分け方は $0.500000$・$0.400000$ で、左右のほうが小さかった（第3節）。

第五に、分離子は、二つの値に丸める前の揺れで比べるか、丸めた後の本数で比べるかである。固有ベクトルは丸める前の量を最小にする。切る辺の本数は丸めた後の量で、二つの最小は同じ分け方を指すとは限らない（第4節）。

キーワード：スペクトル分割、フィードラーのベクトル、ラプラシアン、最小の二等分、レイリー商、グラフの分割。

射程（何を示さないか）

新しい定理も法則も主張しない。ラプラシアンの二番目の固有ベクトル（フィードラーのベクトル）でグラフを分ける方法、その値の差の二乗の和の商を最小にする性質、はしごに尾を付けた形がこの分け方の苦手な例として知られていること（Guattery と Miller）は、いずれも既知である。小さなグラフだけを扱う。点 $16$ と $20$ の四つのグラフだけで、尾の長さを伸ばしたときの本数の増え方は、二つの大きさから言わない。ほかの分け方に入らない。中央以外のしきい値、固有ベクトルを何本も使う分け方、流れを使う分け方、多段の分け方は扱わない。実在のネットワークを扱わない。回路や計算機の割り付けなど、応用の場面は論じない。既刊との関係：論文880 の射程注記は、算法に入らず、固有値を使ってグラフを分ける方法には入らないと書いた。本稿はその席に座る（先客なし）。論文880 は、ラプラシアンの二番目の固有値が点で切る数を超えず、同じ数で切れるグラフの首の細さを測り分けることを示した。ここでは、固有値ではなく固有ベクトルで実際に分けたとき、切る辺の数が最小に当たるかを数える。加えたのは、四つのグラフで固有ベクトルの分け方と総当たりの最小を比べたこと、尾の付いたはしごで最小の $2.000000$ 倍・$2.500000$ 倍を切ることを出したこと、その分け方が上の道と下の道を分けることを確かめたこと、丸める前と後の商を並べたこと、分離子を「丸める前の揺れか、丸めた後の本数か」に置いたことである。

1. 記法と問い

設定：点 $n$ 個のグラフのラプラシアンを $L$ とし、二番目に小さい固有値を $\lambda_2$、その固有ベクトル（フィードラーのベクトル）を $f$ とする。点に値 $x_i$ を置いたとき、次の商（レイリー商）を考える。

$$R(x)=\frac{\sum_{\text{辺 }uv}(x_u-x_v)^2}{\sum_i x_i^2},\qquad \lambda_2=\min_{x\perp\mathbf{1}}R(x)=R(f)$$

値を $+1$ と $-1$ の二つに丸めて $n/2$ 個ずつにすると、$R(x)=4\times(\text{切る辺の数})/n$ になる。スペクトル分割は、$f$ の値の中央で点を $n/2$ 個ずつに分ける。これを、すべての二等分を総当たりで調べた最小の切る辺の数と比べる。

グラフ：①点 $8$ 個の完全グラフ二つを辺 $2$ 本でつないだもの（点 $16$・辺 $58$）②$4\times4$ の格子（点 $16$・辺 $24$）③④尾の付いたはしご：上の道と下の道がそれぞれ $2k$ 点の道で、横木は後ろ半分の $k$ 本だけ（$k=4$ で点 $16$・辺 $18$、$k=5$ で点 $20$・辺 $23$）。

問い：固有ベクトルの値の中央で分けると、切る辺の数は最小に当たるか。

2. 四つのグラフで比べる

計算 2.1：固有ベクトルの分け方と総当たりの最小。

観察 2.2　首の細いグラフと格子では最小に当たり、尾の付いたはしごでは最小より多く切る。首の細いグラフでは、固有ベクトルは二つの塊を分け、つなぐ $2$ 本だけを切った。尾の付いたはしごでは $k=4$ で $4$ 本、$k=5$ で $5$ 本を切り、最小の $2$ 本の $2.000000$ 倍・$2.500000$ 倍だった。二つの大きさで切る本数は $k$ に等しかったが、それより先は数えていない。

3. 何を切ったのか、丸める前と後

計算 3.1：尾の付いたはしごで、固有ベクトルの分け方と左右の分け方（二本の道を尾とはしごの境で切る）。

観察 3.2　固有ベクトルの分け方は上の道と下の道を分け、横木を切っていた。二つの大きさとも、中央で分けた二組はちょうど上の道と下の道だった。横木は $k$ 本あるので、切る本数は $k$ になる。最小の二等分は二本の道を左右に切る $2$ 本である。

観察 3.3　丸める前と後で、上下と左右の順が入れ替わる。固有ベクトルそのものの商は $0.103300$・$0.071278$ で、どの二つの値の分け方よりも小さい。しかし二つの値に丸めると、固有ベクトルが指した上下の分け方は $1.000000$、左右の分け方は $0.500000$・$0.400000$ で、左右のほうが小さかった。丸める前に最小だった形が、丸めた後の最小を指さなかった。

4. 分離子

観察 4.1　分離子は、二つの値に丸める前の揺れで比べるか、丸めた後の本数で比べるかである。固有ベクトルは、値を自由に置いてよいときの商を最小にする。切る辺の本数は、値を二つに丸めたときの商に等しい。首の細いグラフでは二つの最小が同じ分け方を指し、尾の付いたはしごでは別の分け方を指した。

観察 4.2　言わないこと。固有ベクトルが上下に分かれる仕組み、尾を伸ばしたときの本数の増え方、中央以外のしきい値、ほかの分け方、実在のネットワークは扱わない。示したのは、四つの小さなグラフで、固有ベクトルの分け方が最小に当たる場合と当たらない場合があり、当たらない場合には丸める前と後で順が入れ替わっていたことである。

5. 点呼と結び

1. 商 $R$ と $\lambda_2$、丸めた商は切る辺の数（第1節）：二つの最小。
2. 首の細いグラフ・格子で比 $1.000000$（計算 2.1）：最小に当たる。
3. 尾の付いたはしごで比 $\mathbf{2.000000}$・$\mathbf{2.500000}$（計算 2.1）：最小より多く切る。
4. 上の道と下の道を分けた（計算 3.1）：横木を切った。
5. 丸めた後は上下 $1.000000$、左右 $0.500000$・$0.400000$（観察 3.3）：順が入れ替わる。
6. 丸める前か、後か（観察 4.1）：分離子・論文880 の射程注記。

結び：固有ベクトルで二等分すると、首の細いグラフは最小に当たり、尾の付いたはしごは上下に切れる。点 $8$ 個の完全グラフ二つをつないだグラフと格子では、固有ベクトルの値の中央で分けると最小の二等分と同じ本数を切った。尾の付いたはしごでは上の道と下の道を分けて横木を切り、最小の $2.000000$ 倍・$2.500000$ 倍になった。二つの値に丸めると、左右に分けるほうが商は小さかった。分離子は、二つの値に丸める前の揺れで比べるか、丸めた後の本数で比べるかである。既刊との位置：論文880 が固有値で測り分けた首の細さを、固有ベクトルで実際に分けたときの本数で数えた。正直に言えば、大きなグラフでの外れ方や、上下に分かれる仕組みは言わない。四つの小さなグラフで、当たる場合と当たらない場合を並べた、そこまでである。

参考文献

1. Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal.
2. Guattery, S., & Miller, G. L. (1998). On the quality of spectral separators. SIAM Journal on Matrix Analysis and Applications.
3. 山岸勇輝 (2026). 『ラプラシアンの二番目の固有値は点で切る数を超えず、同じ数で切れるグラフの首の細さを測り分ける』[論文880]. YOI: https://www.yamagishiyuuki.com/yoi/880

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

書誌

山岸勇輝（2026）「固有ベクトルで二等分すると、首の細いグラフは最小に当たり、尾の付いたはしごは上下に切れる」［論文940］. YOI: https://www.yamagishiyuuki.com/yoi/940

@misc{yamagishi2026yoi940,
  author = {Yamagishi, Yuuki},
  title = {Bisecting by the Eigenvector Hits the Minimum for a Thin Neck but Splits a Ladder with a Tail Top from Bottom},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/940},
  note = {Preprint, edition 1}
}