グラフ理論における「木」とは、連結で閉路を持たないグラフのことを指します。頂点数が5の場合、同じ形を回転や頂点名の変更で一致するものは同一視し、異なる構造をすべて列挙する問題がよく出題されます。
この記事では、頂点数5の木を同型を除いて分類する方法と、それぞれの形を図示しながら分かりやすく解説します。
木グラフの基本的な性質
木とは、すべての頂点がつながっていて、かつ閉路（輪になった経路）を持たないグラフです。
木には重要な性質があり、頂点数をnとすると辺の数は必ずn-1本になります。
したがって、頂点数5の木では、辺の数は4本になります。この条件を利用すると、作れる形を整理しやすくなります。
頂点数5の木を分類する考え方
頂点数5の木を考えるときは、各頂点につながっている辺の数である「次数」に注目します。
頂点数5の木では、次数の合計は辺の数の2倍なので、4本の辺から次数の合計は8になります。
この条件を満たす次数の組み合わせを考えることで、同型でない木の形を漏れなく探すことができます。
頂点数5の木のすべての形
頂点数5の木は、同型を除くと全部で3種類あります。
1. 5つの頂点が一直線につながる木（パス型）
図で表すと次のようになります。
●―●―●―●―●
この木では、両端の頂点の次数は1、中央の3つの頂点のうち両端寄りの頂点の次数は2、中心の頂点の次数も2になります。
頂点を順番につないだだけの最も基本的な形で、グラフ理論ではパスグラフとして扱われます。
2. 1つの中心から4方向に枝分かれする木（星型）
図で表すと次のようになります。
●
│
●―●―●
│
●
中央の頂点の次数は4で、残り4つの頂点の次数はすべて1です。
この形は完全な星型グラフであり、頂点数5の場合は最も枝分かれが大きい木になります。
3. 途中の頂点から枝が出る木（T字型）
図で表すと次のようになります。
●
│
●―●―●―●
中心付近の頂点の1つが3本の辺を持ち、そこから枝が分かれる形です。
次数の並びは、次数3の頂点が1つ、次数2の頂点が1つ、次数1の頂点が3つになります。
なぜ頂点数5の木は3種類だけなのか
頂点数5の木では辺が4本しかないため、複雑な形を作ることはできません。
次数の最大値によって分類すると、中心となる頂点の次数が4の場合は星型、次数が3の場合は枝分かれ型、最大次数が2の場合は一直線型になります。
これ以外の形を作ろうとしても、頂点数5の条件では必ず上記3種類のどれかと同型になります。
同型を除くという意味
グラフ理論で「同型を除く」とは、頂点の名前や配置方法が違っていても、辺のつながり方が同じなら同じグラフとして扱うという意味です。
例えば、A-B-C-D-Eという名前の付け方と、1-3-5-2-4という名前の付け方で同じ一直線状の構造なら、これらは同じ木と考えます。
そのため、図を描く位置や向きが違っていても、接続関係が同じものは一つにまとめます。
まとめ：頂点数5の木は3種類に分類できる
頂点数5の木を同型を除いて列挙すると、全部で3種類になります。
1つ目は一直線につながるパス型、2つ目は中心から4本の枝が伸びる星型、3つ目は途中の頂点から枝分かれするT字型の木です。
木の分類問題では、辺の数や次数の合計に注目すると、同型を除いた形を効率よく見つけることができます。
コメント