命題1.の証明終わり命題1.は連結なグラフの性質のうちの1つで、頂点の部分集合を取ってきたとき、その部分集合内で点が全て辺で繋がっていれば、その部分集合のとり方は元々のグラフの頂点の集合を取るしか無い、ということです。次に、グラフ距離について説明します。metric)という。d(x,z)\)(三角不等式)である。「何を言っとるだ?」という感じかもしれませんが、最も馴染み深いと思われるユークリッド距離で考えるとイメージが湧きやすいと思います。x=y\)」という条件についてこれは、「距離は必ず\(0\)以上の値で、距離が\(0\)な点同士は同じ点しかありえない。」ということを表しています。「距離が負なんてことはありえないし、距離が\(0\)なのに点が違うってありえないでしょ」という直感に対応しています。「\(d(x,y)=d(y,x)\)」という条件についてこれはそのまんまです。「\(x\)と\(y\)の距離と\(y\)と\(x\)の距離は同じだよね?」という直感に対応しています。東京駅から新宿駅までの距離と新宿駅から東京駅の距離は同じ、ということです。d(x,z)\)(三角不等式)」という条件についてこれは、三角形で考えると分かりやすいと思います。要するに、「三角形の2辺の長さの和は他の1辺の長さより大きい」ということです。三角不等式を三角形で考えると、こうなる。ちなみに、\(\mathbb{R}^n\)の距離関数(つまり\(d:\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}\))は、ユークリッド距離だけではありません。先程の3つの条件を満たしさえすれば、距離と呼べる、という話だからです。\mathbb{R}^2\)に対して$$d(\boldsymbol{x},\boldsymbol{y})=\left|x_1-x_2\right|+\left|y_1-y_2\right|$$と定めても、\(d\)は先の3つの条件を満たします(この\(d\)をマンハッタン距離といいます)。距離空間に付随する重要な概念として、完備距離空間というものがあります。実数の連続性のシリーズで述べましたが、実数においてはコーシー列が収束します。実は、一般にはコーシー列が収束するとは限りません(コーシー列は必ず収束します)。実数の集合はユークリッド距離でもって距離空間となります。このようにコーシー列が収束するような距離空間を完備距離空間といいます。ちなみに、コーシー列が収束するように無理やり集合を”拡張”することを完備化といいますが、有理数の集合を完備化した集合が実数の集合です。これは実は実数の連続性を担保しているともいえる事実です。連結なグラフに対しても距離を考えることが出来ます。使われる(と筆者は思っています)がグラフ距離と呼ばれるものです。V\)のとき\(o(c)=x\)、\(t(c)=y\)となる路\(c\)全体を考え、その長さ\(\left|c\right|\)の最小値として\(d(x,y)\)を定める。V\)のとき\(d(x,y)=0\)と定める。この距離関数\(d\)をグラフ距離と呼ぶ。要するに、最短経路です。※注意※これは一般のグラフに対する距離ではなく、連結なグラフに対する距離ということです。距離関数の節でも述べましたが、距離関数というのは1つの集合に対して1つしか存在しないわけでは有りません。限定的になってはしまいますが、グラフに対する距離としてハミルトン距離という距離もあります。「グラフ距離を”定める”って言ったって、本当にそれって距離関数なんですか?」となると思います。そこで、先のグラフ距離が距離関数であることを証明します。命題2.グラフ距離は距離関数である。V\)のとき、\(|c|\)は\(x\)と\(y\)をつなぐ辺の個数なので正の値です。\(d(x,y)\)は\(|c|\)の最小値なので、\(d(x,y)>0\)です。V\)のときは\(d(x,y)=0\)と定めました。故に、\(d(x,y)\geq0\)です。2\(d(x,y)=d(y,x)\)の証明\(x\)と\(y\)をつなぐ辺の個数の最小値と\(y\)と\(x\)とをつなぐ辺の個数の最小値は一致しているため\(d(x,y)=d(y,x)\)です。d(x,z)\)とすると、少なくとも1点、\(y\)の他に\(x\)と点\(z\)をつなぐ路に点が存在することになります。これは路の長さの最小性に矛盾します。\(x=y\)のとき、\(d(x,y)+d(y,z)=0+d(y,z)=d(y,z)=d(x,z)\)により成り立ちます。\(x=z\)のとき、\(d(x,y)+d(y,z)\geq0=d(x,z)\)により成り立ちます。\(y=z\)のときは\(x=z\)と同じです。命題2.の証明終わり組み合わせグラフ本記事の最後に組み合わせグラフについて解説します。辺の始点と終点が一致しているときに、その辺をループ辺といいます。二点間に複数の辺が存在するときに、そのグラフは多重辺を持つと言われます。ループ辺、多重辺\(X=(V,E)\)をグラフとする。edges)を持つという。組み合わせグラフ簡単です。ループ辺も多重辺も持たないようなグラフを組み合わせグラフといいます。組み合わせグラフループ辺と多重辺を持たないグラフを組み合わせグラフという。モデルとして利用する多くのグラフは有限で連結な組み合わせグラフです。グラフを現象を表すモデルとして扱う場合、多くは有限で連結な組み合わせグラフ(これを助詞を除いて有限連結な組み合わせグラフといいます)です。インターネットのネットワークでは、いくら端末が多くてもそれらは有限です。世界中の端末を集めたとて、数は膨大ですが高々有限の個数しか存在しません。それらの端末をつなぐケーブルも有限個しか存在しません。故にインターネットのネットワークのモデルは有限グラフです。互いにケーブルで結ばれていない2つの部分に分けられるネットワークは考える必要がないので、対応するグラフは連結として良いわけです。ループ辺に当たるケーブルは情報伝達において意味をなさないし、多重辺に当たるケーブルは1つのケーブルとして考えても差し支えありません。故に、モデルになるグラフというのは組み合わせグラフということになります。同型なグラフ同型なグラフというのは「本質的には同じグラフ同士のこと」です。いうことかと言うと、それはグラフ理論の着眼点を考えると直ちに分かります。前々回にグラフ理論は、点と点の繋がり方にのみ着目した分野である。形が異なろうが、点と点の繋がり方が同じであれば、同じですよね、という話です。これを数学的に書くと以下です。グラフ同型\(X_1=(V_1,E_1)\)、\(X_2=(V_2,E_2)\)をグラフとする。f_E(e)\right)=f_V\left(t(e)\right)\)\(\overline{f_E(e)}=f_E(\bar{e})\)が成り立つことをいう。これらの条件はまさに2つのグラフの点の繋がり方が同じであることを表しています。E_1\)の始点に対応する\(X_2\)の始点と一致している、ということを述べています。E_1\)の終点に対応する\(X_2\)の終点と一致している、ということを述べています。E_1\)の逆向きの辺と対応する\(X_2\)の辺\(f_E(\bar{e})\)と一致している、ということを表しています。皆様のコメントを下さい!いきなり全く関係ない話をします。筆者は漫画をそこそこ読むのですが、中でもバイブルと言えるのはBLEACHです。何回読み直したか分かりません。来月の10日から千年血戦篇のアニメが始まりますし、ワクワクです。今回は、連結、グラフ距離、組み合わせグラフ、同型なグラフについて解説しました。それぞれ連結:グラフのどの2点も路で繋がっている状態。グラフ距離:グラフの2点間の最短経路。組み合わせグラフ:ループ辺も多重辺も無いグラフ。同型なグラフ:見てくれは違えど、点と点との繋がり方が一致しているグラフ同士。次回は有向グラフと隣接行列1ということで、それぞれを導入します。乞うご期待!質問、コメントなどお待ちしております!どんな些細なことでも構いませんし、「定理〇〇の△△が分からない!」などいただければ全てお答えします!お問い合わせの内容にもよりますが、ご質問はおおよそ3日以内にお答えします。回答が欲しければその旨もコメントでお知らせください。本記事は「有向グラフとは何か?」「隣接行列とは何か?」について解説する記事です。本記事を読むにあたり、グラフと路について知っている必要があるため、以下の記事も合わせて御覧ください。本記事は、レオンチェフ方程式を用いて、経済分析を行う方法について簡単に解説する記事です。本記事を読むにあたり、レオンチェフ方程式について知っている必要があるため、以下の記事も合わせてご覧ください。本記事はハミンググラフとハミング距離について解説する記事です。本記事を読むにあたり、距離関数とグラフについて知っている必要があるため、以下の記事も合わせてご覧ください。34コメントをキャンセルメールアドレスが公開されることはありません。その2ホーム幾何学グラフ理論お知らせ2023/5/20沢山のコメント、ありがとうございます。お返ししますので、今しばしお待ち頂ければ幸いです。2023年度から新社会人。2019年に博士前期課程修了(修士(数理科学))。