gm learning

完全グラフの辺数

　完全グラフ K_n の辺数は次の式で表すことができます．

n(n-1)/2

この式は n 個の中から 2 個を取り出す方法の総数と一致しています．順列・組合せを勉強したことのある人には当たり前のことですが，そういう知識を仮定せずに考えてみましょう．

　とにかく実験をして，頂点数と辺数の関係を調べてみましょう．

　実験結果を表にまとめると，次のとおりです．

頂点数	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
辺数	0	1	3	6	10	15	21	28	36	45	55	66	78	91	105

　この表を見て，何がわかるでしょうか？勘のよい人なら，0 から始めて1, 2, 3, 4, ... と足してくと，辺数に並ぶ数が順に得られることに気づくでしょう．では，どうしてそうなっているのでしょうか？

　それは完全グラフの描き方を考えればわかります．正多角形の形にこだわらず，完全グラフの頂点数を１つずつ増やしていってみましょう．

　まず，頂点が１個だけなら，辺は全然ありません．それに頂点を１つ加えて，すでにある頂点と辺で結べば K₂ のでき上がりです．このとき，辺は１本追加されました． K₃ を作るには，さらに，頂点を１つ増やして，すでにある２個の頂点と辺で結びます．

　要するに，すでに完成している完全グラフに１つ頂点を追加して，残りの頂点のすべてと辺で結ぶという作業を繰り返していくわけです．その際に追加される辺の本数は，当然，初めからあった頂点の個数と一致します．つまり，K_n が完成するときには， K_n-1 の頂点に向かって伸びる n-1 本の辺が追加されます．

　ということは，K_n の辺数は，

1 + 2 + 3 + … + (n-2) + (n-1)

になると思いませんか．例えば，K₅ の場合には，

1 + 2 + 3 + 4 = 10

となっているわけです．

　それなら，K₁₀₁ の辺数は， 1 から 100 までの整数をすべて足した値に等しいことになりますね．暗算の得意な人なら，その値が 5050 にあることすぐにわかでしょう．でも，何かうまい計算方法はないでしょうか？

実は，暗算が得意ではない人でも簡単に暗算で求められる方法があります．

1 + 2 + 3 + … + 98 + 99 + 100

まず，両端の 1 と 100 を足してみましょう．もちろん，101 です．続いて，その隣の 2 と 99 を足すと 101, さらに 3 と 98 を足しても 101 という具合に，左からは 1 ずつ増えるけれど，右から 1 ずつ減っていくので，その和はいつも 101 になります．そういう数の組は 100 の半分の 50 組ですね．ということは，

1 + 2 + 3 + … + 98 + 99 + 100 = 101×100/2 = 101×50 = 5050

という計算ができるわけです．　この理屈がわかれば， 1 から n までの整数を順に足した値が次のようなることも理解できるでしょう．

1 + 2 + 3 + … + (n-2) + (n-1) + n = (n+1)n/2

　ここまでわかれば，K_n の辺数を理解するのは簡単です．要するに，1 から n-1 まで足せばよいのです．つまり，上の等式の右辺の n を n-1 で置き換えた式が答えです．

((n-1)+1) (n-1)/2 = n(n-1)/2