gm learning

完全２部グラフ

　決定ボタンをクリックすると， 黒い頂点が５個，白い頂点が５個，それぞれ水平に並んだグラフが現れます． さらに，黒と白の値をいろいろと変えて，決定ボタンをクリックしてみましょう． そこに登場するグラフが完全２部グラフです．

　つまり，頂点全体が２つの部分に分かれていて， それぞれの部分の中には全然辺がないけれど， ２つの部分にまたがる辺はすべてあるグラフが完全２部グラフです． そういう辺が何本か欠けていれば，“完全”とは言わないで， 単に２部グラフと呼びます．

　ということは， ３部グラフ，４部グラフというのもあるわけです． 例えば，３部グラフは頂点全体を３つの部分に分けてみると， それぞれの部分の中には全然辺がなく， 辺があるとすると，異なる部分に属している頂点を結ぶものだけという グラフです． そして，その部分のことを部集合と呼びます． ４部グラフでも，５部グラフでも，考え方が同じです．

　完全２部グラフならば， 黒頂点の個数の n と白頂点の個数の m を添えて， K_n,m と書きます． 例えば，最初にお目にかかったグラフ は K_5,5 ですね．

　一般的に，完全 k 部グラフならば， k 個の部集合に含まれる頂点の個数を K （クラトウスキーの K です）の右下に並べて書きます． 例えば，K_1,2,3と書けば， それぞれ１個，２個，３個からなる３つの部集合を持つ完全３部グラフを 表しています．

• 完全２部グラフの頂点数と辺数の関係を考える．
• 完全 k 部グラフの姿が見たい．

最初に戻る