Wait a moment...

【数学】この図形に覚えあり

nem11.78xem (7)
600
8
2019-04-03 17:59:09
【数学】この図形に覚えあり


次の図形をご覧ください:



これらの図形、何を表していると思いますか?

正解は、いろいろなものを表しています!

例えば!

水は化学式で H2O と書かれますね。
一つの 酸素 O に 二つの水素 H がくっついて、

という形をしています。O, H という記号を取り払うと、

という図形が現れます。

 

他の例として、上のような、教習所みたいな道路があったとしましょう。
(絵心・・・。)


十字路、T字路、曲がり角を「丸」、道路を「線」で表すと、

という図形が現れます。

 

このように、
・いくつかの 〇 (丸)を書いて、
・〇と〇を結ぶ線をいくつか書き込む
ことで完成する図形のことをグラフといいます。

※)小学校から高校の間に習うグラフ (比例反比例のグラフ、1次関数のグラフ等)とは別物です。

最初に書く 〇 のことを 頂点 、〇と〇を結ぶ線のことを といいます。
グラフは他にも、いろいろなところに現れます!


例えば、上の相関図(?)において、を全て頂点と見なし、点線・線を全てと見なすと、
複雑な グラフ になっていることがわかります。


他にも、Google で「インターネット」とか「ブロックチェーン」とか
画像検索すると、グラフっぽい画像がたっくさん出てきます。

 

こんな風に、グラフは僕たちの身の回りにあふれています。

 

繰り返しますが、いくつかの 〇 (丸)を書いて、〇と〇を結ぶ線をいくつか書き込むことで完成する
図形がグラフです。なので、誰でも簡単に、自分オリジナルのグラフをいくらでも作ることができます。

例えば、次の三つの図形は全てグラフです:


ね、簡単に作れるでしょ。二つの頂点の間に、二本線や三本線があってもOKです。

ただし、次のようなものはダメ:

辺は、頂点と頂点の間に引かれるものなので、一つの頂点から、線がでっぱなしになっているものは、
グラフと呼びません。

先ほども言いましたが、グラフは、水などの分子の構造を表していたり、街の地図を表していたり、
人と人との相関図、あるいはインターネットやブロックチェーン技術を表していたりと、
いろいろな場面で姿を現します。


「じゃあ、グラフの性質を明らかにしようではないか!」と言って、作られた理論のことを、
グラフ理論といいます。

 

 

せっかくなので、グラフ理論の定理を一つご紹介します。


僕はこの定理を初めて知ったとき、「えーっ、うそだー!」と思いました。
こんな定理が成り立つなんて、ちょっと信じられませんでした。

 

その定理を紹介するために、グラフ理論で使われる簡単な言葉をいくつかチェックしておきましょう。

 

まず、各頂点にくっついている辺の本数を、その頂点の次数と言います。

 

上の例ですと、一番左の 〇 (頂点)には、辺が右に1本くっついてますね。だから、次数1です。
左から二番目の 〇 (頂点)には、辺が左右に1本ずつくっついているので、次数2です。

次数が偶数である頂点のことを偶点、奇数である頂点のことを奇点と言います。



さて、準備が整いました。約束の定理をご紹介します:

 

定理どんなグラフでも、奇点の個数は偶数である。

 


本当?本当なの?奇点の個数が奇数のグラフだってあるでしょ!



そう思っていろいろなグラフを書いてみても、そのようなグラフは絶対に見つかりません。


先ほどの例で確認してみましょう。



上の例の場合、奇点は全部で個あります。つまり、奇点の個数は偶数です。


他のグラフも見てみましょう。下図では、各頂点の隣に、その頂点の次数を
書いてみました。また、奇点青色で塗ってみました。


ほら、奇点の個数は偶数でしょ?一番最初のグラフでも

やっぱり奇点は偶数個です。

先ほども言いましたが、グラフってすごい定義が簡単で、無数に作り出すことができます。
でも、どんなにがんばっても、奇点が奇数個のグラフって作れないんです。んー、信じられん!


定理の証明が気になる方のために、今回から新しく設ける `あぺんでぃくす' の欄に、証明を載せておきました。
こちらは詳しいことが知りたい 数学マニアの方 向けの欄でございます。


ということで、グラフ理論の紹介と、不思議な定理の紹介でした。


今日はここまで!

 

あぺんでぃくす


定理の証明】


証明のカギは2つありまして、1つは「全ての頂点の次数を足したもの」を考えることです。

例えば上の例だと、それぞれの頂点の次数は1、2、2、1なので、
全ての頂点の次数を足したもの」は、

1+2+2+1=6

です。どのような頂点も、偶点奇点かのどちらかなので、


全ての頂点の次数を足したもの
=「全ての偶点の次数を足したもの」+「全ての奇点の次数を足したもの」

と分けることができます。偶点というのは、次数が偶数になる点のことでしたね。

なので、「全ての偶点の次数を足したもの」は、偶数になります。


次に、


全ての頂点の次数を足したもの」=2×「全ての辺の本数」


という関係式が成り立ちます。特に、「全ての頂点の次数を足したもの」は偶数です。これが証明のカギ2つ目です。
この関係式を確かめるために、先ほどの例を見てみましょう。各頂点に、A、B、C、Dと名前を付けます:

上のグラフだと、
頂点Aには、辺AB
頂点Bには 辺AB, 辺BC
頂点Cには、辺BC, 辺CD
頂点Dには、辺CD

くっついています。色分けしてみましたが、辺AB, 辺BC, 辺CDという
全ての辺が、それぞれ2回ずつ現れていますね。


全ての頂点の次数を足したもの」=「頂点Aの次数」+「頂点Bの次数」+「頂点Cの次数」+「頂点Dの次数」


ですが、「頂点A (B,C,D)の次数」の意味は、「頂点A (B,C,D) にくっついている辺の数」でしたね。
なので、


全ての頂点の次数を足したもの」=2×「全ての辺の本数」


となります。他のグラフについても、同じように考えます。

 

グラフは、一本の辺に対して、その両端に1つずつ、合計2個の頂点がくっついています。
全ての頂点の次数を足したもの」を計算する際、各頂点 (上の例だと、頂点A~D)
にくっついている辺の数をカウントしていくわけです。


頂点 A の次数をカウントするときに、それにくっついてる辺AB を一回カウントし、
頂点 B の次数をカウントするときに、それにくっついてる辺AB をもう一回カウントするので、

全ての頂点の次数を足したもの」を数える過程で、
各辺は合計二回ずつカウントされることになります。そのため、

全ての頂点の次数を足したもの」=2×「全ての辺の本数」

となるのです。やや複雑な議論になりましたが、

全ての頂点の次数を足したもの
=「全ての偶点の次数を足したもの」+「全ての奇点の次数を足したもの」


という式から初めて、「全ての頂点の次数を足したもの
と、「全ての偶点の次数を足したもの」がともに偶数となることがわかりました。
これらのことから、「全ての奇点の次数を足したもの」も偶数になることがわかります。

奇点の次数は奇数でしたね。奇数を奇数回足すと、奇数になります。奇数を偶数回足すと、偶数になります。
なので、「全ての奇点の次数を足したもの」が偶数になることから、奇点の個数は偶数個、ということになります。

(証明終)


注意
・今回の記事では、頂点の個数が有限個しかないグラフのみを考えておりますが、
頂点の個数が無限にあるグラフも考えられます。その場合、上の定理は一般に成り立たなくなります。
・また、簡単のため、グラフには、次の図のような
「ある頂点から、またその頂点に戻ってくるような辺」はないものと仮定しております。


Comment
やってみよう
やってみよう
2019-04-03 23:26:11ID:95965

>>目指せ北海道::さん

アウトリンクマトリックスの記事を拝見しました(https://nemlog.nem.social/blog/13907)。
自分には、とても難しい話ですね!申し訳ないです。
アウトリンクマトリックス、NEMトランザクショングラフというキーワードだけでも覚えておこうと思います。
コメントをありがとうございました。

目指せ北海道
目指せ北海道
2019-04-03 22:27:59ID:95924

NEM技術勉強会で、アウトリンクマトリックスを作ったところでグラフ理論出てきました。今のPoIでは、その計算がアカウント数の増大によって膨大な量になるのが問題のようなので、NEMトランザクショングラフを簡単に計算できる方法が見つかれば解決するらしいです。僕の知識では無理ですが、、、、

やってみよう
やってみよう
2019-04-03 21:51:20ID:95884

>>やそ::さん

仰る通り、グラフと言ったら、そういうグラフを思い浮かべますよね。
今回の記事のようなグラフについて話したいときは「グラフ理論のグラフの話です!」
て最初に宣言した方がいいですね!

>>7zoesan::さん

絵が・・・描けません!(笑)
実際の道路っぽくするためにフリーハンドで描いたら、あの結果です(泣)

やってみよう
やってみよう
2019-04-03 21:42:34ID:95873

>>YUTO::さん

不思議ですよね!実は僕も、この定理を応用する話は知らなくて、「グラフの基本性質」ぐらいに
理解しています。ネットワークや、分子の構造にどんな影響を与えるのか、興味がわきますね!

>>えっさん&小梅ちゃん🎉nemlogコメンテーター&投げNEM学者::さん

ありがとうございます。
二酸化炭素CO2 や 酸素O2 も、グラフで表されちゃいますね!
「化学式の構造を調べる」というのも、グラフ理論が作られたきっかけの一つに
なっていると思います(^^)

やそ
やそ
2019-04-03 20:59:05ID:95844

こういうのをグラフっていうんですね!
グラフと言えば折れ線グラフとか棒グラフとかそういうものかと思ってました。

7zoesan
7zoesan
2019-04-03 20:20:12ID:95822

メモメモ📝
絵心…笑

YUTO
YUTO
2019-04-03 20:16:30ID:95819

奇点となっているノードの数は偶数になっているのは、何か不思議さを感じます。
これがネットワークにどう影響を及ぼしているのか、難しそうだけど知りたいものです。

大魔王えっさん🐾🌎👣
大魔王えっさん🐾🌎👣
2019-04-03 19:05:27ID:95787

面白かったうぇ~い (● ˃̶͈̀ロ˂̶͈́)੭ꠥ⁾⁾
H2O、言われなかったらわからなかったうぇ~い (● ˃̶͈̀ロ˂̶͈́)੭ꠥ⁾⁾

この記事を書いた人
数学関連の記事が多めです。