KENの構成⑨

テーマ:

またまた、間が空いてしまいましたm(_ _)m

気を取り直して、進んでいきましょう。

さて前回では、CKETでのノード配置をしてみたら、
一筆書きができる配置と、そうでない配置が出てきました。
どちらの場合も同じ頂点数で、ノードの本数も同じです。
それにもかかわらず、違いができてしまいました。
配置のルールも違えてはいないですし、
どうやって考えていけばよいのでしょうか?
というか、たまたま一筆書きができただけで、
全部の配置が一筆書きになる保証なんて、
今のところありませんし、それにこだわる必要あるの?
って感じです。
しかし、こういう特殊なケースに着目するというのは、
定石と言えば定石なので、このまま捨て置くわけにはいきません。
そんなわけで、まずは、
一筆書きが可能であるための条件!
について、調べる必要がありますよね。
それがわかれば、違いを明確にできるかもしれませんし。
ではでは、一筆書きについて、少し考えてみるわけですが、
数学では一筆書きに関する概念があって、
そいつがグラフ理論と呼ばれている概念です。
せっかく用意されているので、使わない手はありません。
まずは、グラフって何?ってところからいきましょう。

グラフって聞くと、たぶんsin関数のグラフだとか、
月ごとの降水量のグラフというように、
ある数と、それに対応する数の関係を図にしたもの
って感じのイメージだと思います。

 

でも、ここで言うグラフとは、具体的なイメージでいくと、
地下鉄の路線図とか、分子構造の図とかですね。


ですから、数と数の関係というよりも、
点と辺のつながり方の関係を図で表したものって感じで、
幾何学的な対象となります。
では、路線図を具体例として、用語の準備をしていきましょう。
まずは、路線図でいう所の駅名に相当するのが点で、
桜通り線(赤)とか、名城線(紫)とかの各路線が、辺に相当します。
そうすると、ある駅から、目的の駅まで行くには、
どの路線でいけばいいのか?
ということを調べるために、路線図を見るわけですが、
これこそが、点と辺のつながり方の関係ですよね。
つまり、名古屋駅(点)から名古屋大学駅(点)まで行こうとすると、
桜通り線(辺)で久屋大通(点)まで行って、
名城線(辺)に乗り換えて、名古屋大学駅(点)まで行く
といった感じで、点と辺のつながり方を見ているというわけです。


では次に、目的の駅まで行く時に気になるのが、
路線の乗り換えとなる駅ですよね。
乗り換えできるできる駅と、そうでない駅の違いは何でしょう?
名古屋駅は、国際センター、中村区役所、伏見、亀島の4つの駅に行けますが、
亀島駅は、名古屋と本陣の2つの駅にしか行けませんよね。
つまり、名古屋駅という点は4つの辺をもつのに対して、
亀島駅という点は、2つの辺しか持ちません。
ですから、ある点に対して、辺が何本あるか?というのは、
グラフにとって重要な情報と言えるでしょう。
このように、ある点に対する辺の本数のことを次数と呼びます。
(※正確に言うと、ある点を端点とする辺の本数)
路線図で言うと、次数が2より大きい駅では、
他の路線に乗り換えができる駅ということになります。


ここで、一つ注意点があります。
幾何学的な対象と言いましたが、あくまで、
点と辺のつながり方の表現としてグラフを考えています。
従って、距離的な性質とは無関係です。
具体的に見るために、路線図の赤枠の部分をピックアップして、
模式化したしてみましょう。
<>

それでは、次の二つのグラフを見比べてみましょう。


上の二つのグラフは、青の辺の長さが全然違いますよね。
また、青の辺の位置については、
左のグラフは内側にあるのに対して、右のグラフは外側にあります。
しかし、点と辺のつながり方という点においては、
両者とも、青の辺は同じ点とつながっていますよね。
ですから、二つのグラフは、同じグラフであるということが言えます。

最後に、もう一つだけ付け足しときます。
路線図を見ると、名城線以外は、始発の駅と終点の駅となっていますが、
名城線だけは、ぐるっと回って一周したら同じ駅に帰ってきますよね。
いわゆる、環状線というやつです。
名城線のように、出発点から辺を通って、
出発点に戻ってこれるようなグラフを閉路グラフと言います。
厳密には、もう少し付け足さないといけませんが、
おいおい肉付けしていくことにします。

さてさて、とりあえずの準備はできたので、
本題に入っていきましょう。
ここまでの段階で、今まで見てきたKENの図というのは、
グラフとして考えることができますよね。
実際に、頂点となる音と、ノードとなる音をつないで、
KENの図を作ってきました。
そして、興味があるのは、KENグラフは一筆書きできるのか?
ということです。
KENグラフは、どんなグラフで、どのような条件があれば、
一筆書きできるのでしょうか?
そんなわけで、次回は本題に入りつつ、
一筆書き可能な条件について、考えていきましょう。
ではでは、次回に続きます~