もう一つ、グラフ理論ネタにお付き合いを。 連結で、閉路を持たないグラフを木(tree)と言います。 あるグラフが木かどうかを判定する方法はいくつか知られていますが、その一つに「連結かつ辺の数が (頂点の個数) - 1」というものがあります。 さて、分子式 …

以下、奇数次の頂点を「奇点」と言うことにします。 (半)オイラー・グラフとなるための必要条件 G をオイラー・グラフ、または半オイラー・グラフとします。条件を満たすような小道をとり、その始点となる頂点を 、終点となる頂点を とします。G がオイラー…

オイラー・グラフと半オイラー・グラフ さて、グラフ G は連結であるとします(連結の定義は既に述べました)。 このとき、G の全ての辺を含むような閉じた小道があれば、G をオイラー・グラフ(Eulerian graph)と言います。また、そのような小道をオイラー小道…

頂点の次数と握手補題 グラフ の各頂点 に対して、その次数を と定義します。要するに、v から伸びる辺の数なのですが、ループに関しては二重にカウントすることに注意してください。 なる頂点を孤立点、 なる頂点を端点と言います。 頂点の次数に関して、握…

久しぶりの日記は、一筆書きを「数学」してみます。 ある種の同値関係 空集合ではない集合 V に対し、 上の同値関係を と定義します。これは同値関係になります。ところでこれは一体どういった同値関係なのでしょうか。 の同値類は です。実際 とすると、 で…