gm learning

グラフの裏返し

　まず，下のアプレットの中で，グラフを描いてみましょう．そして，[補グラフ]ボタンをクリックしてみましょう．すると，グラフがパッと変身します．いったい，何が起こったのでしょうか？

　試しに，もう一度，[補グラフ]をクリックしてみましょう．今度は，最初のグラフに戻ります．

　実は，[補グラフ]をクリックすると，今まであった辺をすべて消して，今まで辺で結ばれていなかった頂点を辺で結んだものが現れるのです．そういうグラフをもとのグラフの補グラフと呼びます．

　つまり，補グラフはもとのグラフの頂点の隣接関係を反転したものですね．だから，補グラフの補グラフは，反転の反転だから，もとに戻ってしまうわけです．

　さて，そこで問題です．補グラフがもとのグラフと同じになってしまうようなグラフを作ってください．

　例えば，長さ３の道（頂点は４個です）を作ってください．その頂点を動かして，Ｎのようにしておきましょう．そこで，[補グラフ]をクリックすると，Ｚのようになりますね．Ｚも頂点を動かして，まっすぐにすれば，道になります．ということは，長さ３の道の補グラフもそれと同じ長さ３の道になっていたわけです．

　このように，補グラフと自分自身が同じになっているグラフを 自己補グラフと呼びます．

　もう１つ簡単な自己補グラフの例は，長さ５の閉路です．まず，五角形を作ってください．そして，[補グラフ]をクリック．すると，星形が現れます．その頂点を動かして変形すると，五角形になりますね．つまり，長さ５の閉路の補グラフも長さ５の閉路だったわけです．

　他にもまだまだ自己補グラフが作れるのですが，あなたは何個作れましたか？