スキップしてメイン コンテンツに移動

グラフ理論

Introduction
sorry, this page is Japanese only.

いよいよ私も三回生になり、グラフ理論の授業が始まりました。ということで、グラフ理論の基本的な定義を書いていこうと思います。

最後に説明する隣接行列については実装を行いましたので、以下の記事もよろしければご覧ください。

隣接行列の実装

グラフのイメージ
グラフ理論のグラフとは高校数学で習う二次関数などとは違います。
例えば駅などを創造してください。各駅間に線路が通っていますね。このような、駅、線路の集まりのことをグラフといいます。次の絵で確認してもらえるとイメージしやすいかと思います。


このようなものをグラフといいます。グラフは二点間がどうつながっているかだけを保存し、実際の距離や位置関係は保存しません。

このような向きのない（各駅を行き来でき、一方通行ではない）グラフを無向グラフをいいます。反対に向きのある（一方通行しかできない）グラフを有向グラフといいます。

グラフの定義
グラフではある空でない集合E,Vを考えます。Eの要素をedge(辺）、Vの要素をvertex(頂点)といいます。
ここで以下のような写像を考えます。

$$g:E \rightarrow V \times V$$

この時(E,V,g)で定義される空でない空間のことをグラフといいます。

写像で捉えるグラフ
写像gというのは、Eの要素、つまり辺を対応する(始点、終点)というV×Vの集合の要素に送ります。gは写像ですので、写像の定義より、Eのどの要素の始点と終点が対応していることになります。つまり、辺がどこにもつながっていないということはあり得ません。反対にすべてのV×Vの要素がEの要素のどれかに対応しているのであればgは全射になります。

隣接行列
隣接行列とはどのvertexと、どのvertexがつながっているかを行列で表します。例を見るのが理解するのには早いと思うので、例を挙げて説明します。
上のグラフのイメージで出てきたグラフの例を考えましょう。隣接行列は以下のようになります。

$$　\[ 
adj = \left(
\begin{array}{cccccc}
0 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
$$

石山駅 -> 一列目
山科駅 -> 二列目
京都駅 -> 三列目
三条京阪 -> 四列目
米原駅 -> 五列目
大垣駅 -> 六列目

として、[n,m]ではnの駅からmの駅へ線路がつながているのであれば1、そうでなければ0をとります。これが隣接行列です。

Reference
https://ja.wikipedia.org/wiki/グラフ理論







Labels:

コメント

コメントを投稿

このブログの人気の投稿

MAP推定

Introduction English ver 今日はMAP推定（事後確率最大化法）について書きました。MAP推定ではベイズの定理を使います。データが少ないとき、最尤推定の結果をあまり信用できない話は、最尤推定の時に書きました。この時、MAP推定では自分の事前に持っている情報を取り入れることができます。 概要 ベイズの定理 MAP推定 共役分布 MAP推定の例 ベイズの定理 ベイズの定理は $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ です。 ただし、 $P(A|B)$ はBが起こった時のAの起こる確率です。 詳しくは  http://takutori.blogspot.com/2018/04/bayes-theorem.html  を見てください。 Map推定 MAP推定ではベイズの定理を使います。MAP推定は事後確率が最大になるようなパラメータを選びます。 いま、$x_1,x_2,...,x_n$というデータを$\theta$というパラメータを持つ分布から得られたとする。この時$P(\theta|x_1,x_2,...,x_n)$を求めたい。 ここで、ベイズの定理を使う。 $$P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}$$ ここで、$P(\theta)$は$\theta$の事前分布である。 $x_1,x_2,...,x_n$はそれぞれ独立であるので、 $$P(x_1,x_2,...,x_n | \theta ) = \Pi_{i=1}^n P(x_i|\theta)$$. よって、マップ推定は $$\theta^{\star} = \arg \max_{\theta} \frac{\Pi_{i=1}^n P(x_i|\theta) P(\theta)}{P(x_1,x_2,...,x_n)}$$ となる。 $P(x_1,x_2,...,x_n)$という値は$\theta$には依存しない。よって、定数であり、最適化に定数は関係ないので、排除すると、MAP推定は次のようになる。 $$\th...
コメントを投稿
続きを読む

ヒープ構造

Introduction English ver 今日はヒープ構造について書きます。ヒープ構造はデータ構造の一種です。ちょうど大学の自主ゼミグループのセミナー合宿に参加させてもらい、そこでグラフ理論を勉強したので、メモをしておこうと思います。   slide  はこんなのを使いました。 Overview データ構造 二分木 ヒープ 実装 ヒープソート データ構造 ヒープ構造の前に、データ構造について、説明します。データ構造とは、データを保存する手法であります。データ構造は、そのデータについてどのような操作を行いたいかによって、最適なものを選ぶことになります。 ヒープ構造はプライオリティキューと呼ばれれるデータ構造を表す方法です。プライオリティキューで行いたい操作は以下の二つです。 データの追加 最小値の抽出 二分木 まず、グラフを定義します。E と V は集合とし、 $e \in E$、つまりEの要素をedge(枝)と呼びます。また、$v \in V$、つまりVの要素をnodeと呼びます。 g:E->V×V をEからV × Vへの写像とします。この時、.(E,V,g)をグラフを言います。 例えば、次のようなものがあります。 丸いのがそれぞれのnodeで、矢印がedgeになります。 各edgeに対して、始点v1と始点v2を対応させるのが写像gの役目です。 根付き木とは次のような木のことです。 これはnode1からnodeが二つずつどんどん派生していっています。 特に、次のような木を 二分木 といいます。 特徴は、ノードが上からなおかつ左から敷き詰められています。一番上のノードを根といいます。また、例えば2を基準にすると、1は2の親、4,5は2の子、3は2の兄弟、8,9,10,11,12は葉と呼ばれます。 ヒープ ヒープ構造はプライオリティキューを二分木で表現したものです。プライオリティキューでやりたいことは次のことでした。 データの追加 最小値の抽出 . では、どのようにこの二つの操作を実現するのでしょうか。 初めにデータの追加について説明します。 1. 二分木の最後に追加す...
コメントを投稿
続きを読む

変分法の可視化

Introduction English ver 今日は、変分法の可視化を実装しました。変分法は、汎関数を最小化させるために使われます。汎関数とは、関数の関数のようなものです。変分法については、  [1] , [2] , [3] , [5] ,  [6] などを参考にしてください。 概要 汎関数 実装 可視化 汎関数 今回は、次のような汎関数を使います。 $$F(x) = \sqrt{1+(\frac{du}{dx}(x))^2}$$ $$l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx$$ l(u)はu(x)という曲線の長さです。.  $u(0)=a$ and $u(1)=b$という制約のもと、$l(u)$を最小化したいといます。 最適な$l(u)$は $$u(x) = (b-a)x+a$$ となります。 (0,a) から (1,b)への直線になっているのがわかります。 これは、$l(u)$は$u$の曲線の長さなので、これを最小化するためには直線が一番であることが直観的にわかります。 変分法での導出は、 [5] を参考にしてください。 実装 変分法における最適な曲線とそうでない曲線の違いを可視化する実装をしました。 $u_A$を $$u_A = (b-a)x+a + A sin(8t)$$ とします。 $A sin(8t)$ は$u$から話す役割を持ちます。. $A \in [0,0.5]$であり、もし$A=0$であれば、$u_A=u$です。 github でcodeを公開しています。 可視化 上側の画像は$u_A(x)$を表しています。下側の画像は$l(u_A)$の値を表しています。 $u_A(x)$が$u$に近づくほど、$l(u_A)$が小さくなることがわかります。 Reference [1] http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-4.pdf [2] http://hooktail.sub.jp/mathInPhys/brach...
コメントを投稿
続きを読む