隣接行列とグラフ:ケーニヒスベルクの橋問題         



6n-graf.svg



グラフを表現するのに、図ではなく、隣接行列を用いることがあります。

無向グラフの隣接行列は、対称行列となり、例えば、上のグラフは、次の隣接行列で表現できます。

行(横段)(始点)は主体となる数字で、上から1、2、3、4、5、6となります。

列(縦列)(終点)は主体となる数字と繋がっている数字部分のみが「1」と表示されています。

最上段では、左から2番目、5番目のみが「1」と表示されています。 つまり、①は②、⑤と繋がっていることを示しています。

ただし、その相互間では方向性がないため、「無向グラフ」となっています。

相互間では方向性がある場合は「有向グラフ」となります。

ケーニヒスベルクの橋の問題

Konigsberg bridges.png 7 bridges.svg

緑の陸地部分を「緑の点」四つとし、橋での繋がりを図示すると、以下のようになります。

「緑の点」四つそれぞれが、他の「緑の点」と繋がっている数は「5:3:3:3」なっています。

「ケーニヒスベルクの橋の問題」とは「プレーゲル川にかかる七つの橋を2度通らずに,すべて渡る経路が存在するか」というものです。

1735年にスイスの数学者レオンハルト・オイラーは,このような経路は存在しないことを証明して,問題を解決しました。

一般に,連結したグラフが一筆書きできるためには次の条件のいずれかが満たされていなければならないと言われています。

(1) すべての頂点について,集まる辺の本数が偶数であること。

(2) 集まる辺の本数が奇数であるような頂点が二つ存在し,ほかの頂点について、集まる辺の本数が偶数であること。

(1)の場合は閉じた経路になり,(2)の場合は始点と終点が異なる経路になります。

Königsberg graph.svg



★ ケーニヒスベルクの橋





★ 1と3の土地を橋渡しすると・・・。



連結したグラフが一筆書きできるための条件

(2) 集まる辺の本数が奇数であるような頂点が二つ存在し,ほかの頂点について、集まる辺の本数が偶数であること。

(2)の場合は始点と終点が異なる経路になる。





★ 関係行列とループを持つ完全有向グラフ




★ 始点=終点が3個の場合





inserted by FC2 system