本記事の内容
本記事は有限グラフ、正則グラフ、路について解説する記事です。
本記事を読むにあたり、「グラフとは何か？」について知っている必要があるため、以下の記事も合わせてご覧ください。
グラフの軽い復習
「グラフって何？」ということを軽く復習します。
直感的には、グラフとは
でした。
これを集合と写像の言葉を使って数学的に表すと
グラフ
集合\(V,E\)に対して、\(V\)と\(E\)の対\(X=(V,E)\)が以下を満たすとき\(X\)はグラフであるという。- \(V\cap E=\emptyset\)
- 次の性質を満たす写像\(i:E\to V\times V\)、\(\iota:E\to E\)が存在する。
- \(\iota^2\left(=\iota\circ\iota \right)={\rm id}_E\quad\)(ただし、\({\rm id}_E\)は\(E\)の恒等写像)
- 任意の\(e\in E\)に対して以下が成り立つ。 $$ \iota(e)\neq e,\quad i\left(\iota(e)\right)=\tau\left(i(e)\right) $$ ただし、\(\tau:V\times V\to V\times V\)は\(\tau(x,y)=(y,x)\)により定まる写像である。
でした。
そしてグラフ理論というのは
ということが出来る、という話でした。
詳しくは【幾何学の基礎シリーズ】グラフ理論編 その1を御覧ください。
有限グラフ
この章では有限グラフというものを解説します。
前回の復習
まずは、前回の復習から始めます。
\(X=(V,E)\)をグラフとします。
このとき、\(E_x\)により、点\(x\in V\)を始点とする有向辺\(e\)の全体の集合を表すことにしました。
つまり、
$$
E_x=\left\{e\in E\middle|o(e)=x\right\}
$$
でした。
このとき、以下が成り立つのでした。
命題1.
\(X=(V,E)\)をグラフとする。このとき\(x\neq y\)ならば、\(E_x\cap E_y=\emptyset\)である。すなわち、頂点が異なれば、その頂点を始点とする有向辺も異なる。命題1.の証明は【幾何学の基礎シリーズ】グラフ理論編 その1を御覧ください。
命題1.により、グラフ\(X=\left(V,E \right)\)に対して
$$
E=\coprod_{x\in V}E_x
$$
(ただし、\(\coprod\)は交わらない和集合)が成り立ったのでした。
有限グラフって何ですか？
シンプルです。
有限グラフを一言で述べると
です。
これを数学的に表現すると以下です。
有限グラフ
グラフ\(X=\left(V,E\right)\)に対して、\(V\)、\(E\)が共に有限集合のとき、\(X=\left(V,E\right)\)を有限グラフという。有限グラフでないようなグラフを無限グラフということもあります。
有限グラフの辺の数のちょっとした性質
一般に、有限集合\(A\)に対して、\(\left|A\right|\)により、\(A\)の要素の個数を表すことにします。
このとき、命題1.により、
$$
\left|E\right|=\sum_{x\in V}\left|E_x\right|\cdots①
$$
が成り立ちます。
さらに、①は
$$
\sum_{e\in E}1=\sum_{x\in V}\sum_{e\in E_x}1\cdots②
$$
と書き換えることが出来ます。
というのも、
- ②の左辺
\(e\in E\)であるような\(e\)に対して、\(1\)を足し合わせるということなので、②の左辺は\(e\in E\)という\(e\)の個数を表しています。
故に
$$
\left|E\right|=\sum_{e\in E}1
$$
となるわけです。 - ②の右辺
左辺と同様にして、\(e\in E_x\)であるような\(e\)に対して、\(1\)を足し合わせるということなので、\(\displaystyle\sum_{e\in E_x}1\)は\(e\in E_x\)という\(e\)の個数を表しています。
故に
$$
\sum_{x\in V}\left|E_x\right|=\sum_{x\in V}\sum_{e\in E_x}1
$$
となるわけです。
要するに、何が言いたいかと言うと、
ということです。
！注意！
ただし、ここで注意があります。
前回、「各辺はちょうど2つの向きを持つ」ということを述べました。
この意味について言及します。
これはどういうことかというと、有向グラフは、各辺の2つの向きのうち、どちらか一方のみを選んでいるということで、無向グラフはどちらか一方を選ぶということはせず、各辺に2つの向きがあるということです。
つまり、
- 有向グラフ：各辺の向きが1つ。
- 無向グラフ：各辺の向きが2つ。
ということです。
故に、平たく言うと、無向グラフ\(X=(V,E)\)において、\(E^\prime\subset E\)という\(E^\prime\)をとることで有向グラフ\(X^\prime=(V,E^\prime)\)が得られるということになります。
従って、この場合\(\left|E\right|=2\left|E^\prime\right|\)が成り立ちます。
正則グラフ
この章では次数と正則グラフについて解説します。
次数
次数については、前回の記事でサラッと解説しましたが、ここで厳密に数学的は話をしようと思います。
とはいえ、なんてことありません。
次数というのは前回述べたとおりで、
です。
これを数学的に述べると以下です。
次数
\(X=(V,E)\)をグラフとする。頂点\(x\in V\)に対して、\(\left|E_x\right|\)を頂点\(x\)の次数(degree)といい、\(\deg x\)で表す。ちなみに、JR東京駅は
- 東北新幹線（分岐する山形新幹線、秋田新幹線、直通する北海道新幹線、上越新幹線、北陸新幹線を含む）
- 東海道新幹線（直通する山陽新幹線を含む）
- 東海道線/宇都宮線(+上野東京ライン)・高崎線/常磐線
- 京浜東北線
- 山手線
- 中央線（快速）
- 横須賀線・総武線（快速）
の6種類の線路があるようです。
京葉線は常磐線と武蔵野線と線路を共有しているそうです。
(そもそも京葉線のホームがめちゃくちゃ遠いので省いても良いんじゃないかと勝手に思っています。)
故に、JR東京駅の次数は6と言えるでしょう。
\(k\)-正則グラフ
任意の\(x\in V\)に対して\(\deg x\leq k\)であるとき、すなわち全ての頂点につながる辺の個数が\(k\)個以下であるとき、\(\left|E_x\right|\leq k\)が成り立つので、①により、
$$
\left|E\right|=\sum_{x\in V}\left|E_x\right|\leq \sum_{x\in V} k=k\cdot\left|V\right|
$$
すなわち、
$$
\left|E\right|\leq k\cdot\left|V\right|
$$
が成り立ちます。
また、全ての頂点の次数が\(k^\prime\)以上であるとき、同様にして
$$
\left|E\right|\geq k^\prime\cdot\left|V\right|
$$
が成り立ちます。
特に、\(\left|E_x\right|\)が\(x\)に依存しない定数\(k\)であるとき、すなわち、どの頂点の次数も定数\(k\)である場合(どの頂点からも同じ数の辺が繋がっている場合)は、\(\left|E\right|=k\cdot\left|V\right|\)が成り立ちます。
このようなグラフを\(k\)-正則グラフといいます。
これをまとめると、以下です。
\(k\)-正則グラフ
\(X=(V,E)\)をグラフとする。任意の\(x\in V\)に対して\(\left|E_x\right|=k\ \)(ただし\(k\)は\(x\)に依存しない定数)であるとき、\(X\)を\(k\)-正則グラフ(\(k\)-regular graph)という。路(path)
本記事の最後に路(path)について解説します。
まずは路のイメージから
次のような状況を考えてみましょう。
丸の内のオフィスに勤務しているオノ君は、午後半休を取り、高尾山に登る予定を立てました。
午後になり、勤務しているオフィスの最寄り駅であるJR東京駅から京王高尾山口駅に電車で向かいます。
このとき、駅から出ることなく東京駅から高尾山口駅まで行くことが出来ます。
(※もしかしたらJRから京王に乗り換えるときに一度改札を出る必要があるかもしれませんが、それには目をつぶって下さい。)
このように、出発点と目的地の間の全てに辺が存在するとき、そのすべての辺の列を路と言います。
数学的な路の説明
以上のことを数学手に表現すると、以下です。
路(path)
グラフ\(X=(V,E)\)において、有向辺の列\(c=\left( e_1,\dots,e_n\right)\)が $$ o(e_{i+1})=t(e_i)\quad (i=1,\dots,n-1) $$ を満たすとき、\(c\)を長さ(length)が\(n\)の路(path)という。\(c\)の長さを、\(|c|\)により表し、\(o(e_1)\)を\(c\)の始点、\(t(e_n)\)を終点といい、それぞれ\(o(c)\)、\(t(c)\)で表す。路は1つではありません。
「路は1つではありません。」というとえらく前向きでカッコいいセリフになりますね。
でも、グラフ理論的には事実です。
厳密に言うと、「路は1つとは限らない。」ですが。
どういうことかを説明します。
先の例を思い出してみましょう。
先の例は要するに、電車で東京駅から高尾山口駅まで行く、ということです。
先に列挙した例は中央線で高尾まで行き、その後高尾で京王高尾線特急・高尾山口行に乗り換える、という路です。
この路の他に、東京駅からJR特急おうめ3号で立川まで行き、立川でJR中央線・高尾行に乗り換え、高尾駅で京王高尾線・高尾山口行に乗り換えて高尾山口駅に行くという路もあります。
このように、必ずしも路は１つではありません。
勿論、路が1つしか無い場合もあります。
つないだ路
グラフ\(X=(V,E)\)に対して、2つの路\(c_1=\left(e_1,\dots,e_m\right)\)、\(c_2=\left(e_1^\prime,\dots,e_n^\prime\right)\)に対して、\(t(c_1)=o(c_2)\)のとき、すなわち、1つ目の路の終点が2つ目の路の始点と一致していれば、路\(c_1\)と路\(c_2\)をつないで得られる路\(\left(e_1,\dots,e_m,\ e_1^\prime,\dots,e_n^\prime \right)\)が得られます。
これを\(c_1\cdot c_2\)で表します。
逆路
路\(c=\left(e_1,\dots,e_n\right)\)に対して、すべての辺の向きを逆向きにした\(\bar{c}=\left(\bar{e}_n,\dots,\bar{e}_1 \right)\)もまた路です。
要するに復路ということで、帰り道のことです。
逆路
グラフ\(X=(V,E)\)の頂点\(x,y\in V\)に\(o(c)=x\)、\(t(c)=y\)となる路\(c=\left(e_1,\dots,e_n\right)\)が存在したとする。このとき、\(\bar{c}=\left(\bar{e}_n,\dots,\bar{e}_1 \right)\)を路\(c\)の逆路という。皆様のコメントを下さい！
皆様も一度は”徹夜せざるを得ない”という状況になったことがあるのではないでしょうか。
勿論、「”徹夜せざるを得ない状況”はつくらない」ということが最も良いのですが、一度は徹夜の経験があるのではないでしょうか。
皆様はどうやって眠気を覚ましていますか？是非コメントで教えて下さい！
(こんなこと聞いて良いんだろうか…)
結
今回は、有限グラフ、正則グラフ、路について解説しました。
それぞれ
- 有限グラフ：頂点と辺の数が有限なグラフ。
- 正則グラフ：全ての頂点につながる辺の個数が一定なグラフ。
- 路：出発点から目的地までつないだ辺の列。
です。
次回は連結、グラフ距離、ループ辺、多重辺、組み合わせグラフについて解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。
この記事の内容をより詳しく知りたい方は以下のリンクの本を参照してください！
コメントをする
路の数学的表現に疑問があります。
o(e_i)=t(e_i+1) (i=1,…,n)
とありますが、e_1の始点とe_2の終点は一致しないかと思います。逆ではないでしょうか？さらに、e_n+1が未定義なのでi=nまでと注釈なく表記するには問題があるかと思います。
加えて、逆路の表現においてc=(e_1,…,e_n),c*=(e_1*,…,e_n*)とありますが、括弧内の要素の順序は関係ないのでしょうか？c*=(e_n*,…,e_1*)とするのが自然なように感じました。(￣の代わりに*をつけることで逆路,逆向き有向辺を表しました)
名無し様
コメントありがとうごさいます！
また、ご指摘ありがとうごさいます。
名無し様のご指摘の通り、
o(e_i)=t(e_i+1) (i=1,…,n-1)
ではなく、
o(e_{i+1})=t(e_i) (i=1,…,n-1)
でした。訂正いたしました。
また、逆路の表現についても、ご指摘の通り
c=(e_1,…,e_n),c*=(e_1*,…,e_n*)
ではなく、
c=(e_1,…,e_n),c*=(e_n*,…,e_1*)
(逆向きの有効辺の記号は名無し様の記号に準じています)でした。
訂正いたしました。
ご指摘ありがとうございました。