有向グラフ至上主義

個人的なアウトプットの統合管理を目的としたブログです。

有向グラフからみる行列

ふと有向グラフを起点として数学をやるとどうなるかを疑問に思った。そこでまず基本となる線形代数をやることにして、その中から必須事項の行列をやってみることにした。今回は行列の基本ぐらいは知っていることを前提として話を進めることにする。

今回使うグラフの定義

まず、有向グラフを定義する。今回は 有向グラフの諸定義 - 有向グラフ至上主義 の定義(i)を少し改造した定義を採用する。  \mathbb{K} は体とする。

定義: 重み付き(単方向)弱完全2部有向グラフ
 S T を共通を持たない集合とする。  w: S \times T \to \mathbb{K}写像とする。
この時  G := (S, T, w) を重み付き(単方向)弱完全2部有向グラフと呼ぶことにする。

上の定義だけ見るとグラフっぽく見えないと思う。しかし、次のように考えることで自然と見えてくると思う。

定理:
先のグラフの定義は次で定義されるグラフと同一視できる。
 S Tを共通を持たない集合とし、集合  V E V := S \sqcup T E := S \times T \subset V \times V と定義する。そして  w: E \to \mathbb{K}写像とする。この時重み付きグラフ  G G := (V, E, w) と定義する。

ここで例を挙げてみる。
 S = \{s_1, s_2, s_3\} T = \{t_1, t_2\} とし、写像  w (s_i, t_j) \in S \times T w_{i j} \in \mathbb{K} に移すものとする。これを図示すると次のようになる。
f:id:ogata-k:20190923110950p:plain
(弱)完全2部有向グラフの形になっていることがわかると思う。

この例のグラフを  3 -  2 グラフとこの記事では呼ぶことにする。
これを一般化して  m -  n グラフとできることは自明である。また、  m -  n グラフの全体を  G(m, n, \mathbb{K}) とする。ただし、  S T G(m, n, \mathbb{K}) の中ではそれぞれ  \{s_1, s_2, \ldots , s_m\} \{t_1, t_2, \ldots , t_n\} で共通していることに注意したい。以下この  S T S_m T_n と略記する。

グラフの連結

さて  m -  n グラフを定義したので加法と定数倍、連結を定義する。
定義: 加法
加法(演算子)とは次で定義される写像  +: G(m, n, \mathbb{K}) \times G(m, n, \mathbb{K}) \to G(m, n, \mathbb{K}) のことである。
すなわち  G_1=(S_m, T_n, w_1), G_2=(S_m, T_n, w_2) \in G(m, n, \mathbb{K}) に対して   G_1 + G_2 := (S_m, T_n, w_1 + w_2) と定義する。
これはつまり対応する重みの和である。次に定数倍を定義する。
定義: 定数倍
定数  \lambda による定数倍とは次で定義される写像  \lambda \in \mathbb{K} に対し  \lambda \cdot : G(m, n, \mathbb{K}) \to G(m, n, \mathbb{K}) のことである。
すなわち  G=(S_m, T_n, w) \in G(m, n, \mathbb{K}) に対して   \lambda \cdot G := (S_m, T_n, \lambda \cdot w) と定義する。
これはつまり重みの定数倍である。しばしば  \cdot は省略される。
少し先の内容だがこの加法と定数倍によって  (G(m, n, \mathbb{K}), +,  \cdot, (S_m, T_n, 0)) は(  \mathbb{K} -)線形空間になっている。
次に連結を定義する。
定義: 連結
連結(演算子)とは次で定義される写像  *: G(m, n, \mathbb{K}) \times G(m, n, \mathbb{K}) \to G(m, n, \mathbb{K}) のことである。
すなわち  G_1=(S_l, T_m, w_1)  \in G(l, m, \mathbb{K}), G_2=(S_m, T_n, w_2) \in G(m, n, \mathbb{K})に対して  G_1 * G_2 := (S_l, T_n, w) と定義する。ただし  w(i, j) := \Sigma_{k=1}^m w_1(i, k) * w_2(k, j) と定義する。
この連結のイメージは次である。

f:id:ogata-k:20190923203520p:plain
G_1とG_2
この例では位置が混ざっているが G_1 T_2 G_2 S_2の添え字が一致しているため連結できることがわかる。
そして G_1と[tex G_2]の連結 G_1 * G_2
f:id:ogata-k:20190923203550p:plain
G_1*G_2
である。
つまり G_1の始点から G_2の終点へと考えられる経路で重みの積のすべての和で表現できることがわかる。

以上で必要な道具はそろった。

グラフと行列の関係

 G \in G(m, n, \mathbb{K})を考える。 s_i \in S_mから t_i \in T_nへの有向辺においてその重みは w_i jである。
そしてこの重み w_i jを第 (i, j)成分にする行列 W \in Mat(m, n, \mathbb{K})を考える。そしてこの G Wは一対一対応することは定義と作り方から自明である。
ゆえにこの対応で G(m, n, \mathbb{K})の元が Mat(m, n, \mathbb{K})の元に対応する。さらに上記で定義した加法と結合はそれぞれ行列の加法と積に対応する。
ちなみにグラフの反対グラフを作る操作は行列の転置をとる操作に対応することも簡単にわかるので、対称行列は反対グラフと元のグラフが一致するグラフに対応する行列とみなすこともできる。

応用例

行列の可視化以外にも次のような応用例がある。

ニューラルネットワーク
ニューラルネットワークではこのグラフ表現をより一般化したものを利用する。線形的な行列だけでなく定数項や非線形な計算も扱えるようにしたり、結合した状態で3列になっていたりする。しまいにはニューラルネットワークの応用の
ボルツマンマシン - Wikipediaのように両方向を考えることができるようになったりする。

・代数的グラフ理論
ある多重辺を許さない有向(または無向)グラフ Hに対して、 S Tをともに V(H) Hの頂点集合とするが共通を持たない集合として考える。このとき各成分が0か1である隣接行列 K |V(H)|次正方行列となる。そこで K l(>0)回かけた K^lは説明したグラフと行列の対応から簡単に第 (i, j)成分が「辺を最大 l回利用可能という条件のもとで iに対応する頂点から jに対応する頂点へ考えうる経路の本数」を表す。
このように代数的な計算によってグラフを解析する分野を代数的グラフ理論と呼ぶ。

まだまだあるが残りは読者が探してほしい(自分ではすぐに思いつかなかった)。

むすび

最初にも書いた通り大学で学んだ数学をグラフを起点にやってみると面白いかもという興味が発端でやってみた内容なので、探してみると先駆者はいくらでもいると思う。しかし、あえて先駆者のは参考にしなかった。(なのでこんな妄言より先駆者の理論を見るべきである。)だが、グラフと行列の世界を行ったり来たりと遊べたのでとても楽しく、数学は勉強や研究の対象ではなく遊びのおもちゃと再認識させてくれた。
やはり二つの世界を行ったり来たりするのは楽しい。
その関係を表現する矢印、つまり有向グラフはどこにでも出てくる。

有向グラフ基本用語の統一案

はじめに

有向グラフは工学や数学、情報、物理などの多種多様な分野で現れるため、数学のほかの分野以上に用語や定義が一つに定まっていません。以前書いた有向グラフの諸定義において定義が複数あることからもわかると思います。
そこで有向グラフの諸定義の定義(i)、定義(iv)の多重辺を持たない有向グラフを中心にみて用語をわかりやすくまとめてみるとどうなるかを少し考えてみました。今回は混ざりがちの辺とそれをつなげたものをまとめていきます。

辺 (edge)

無向グラフでは辺に向きがないので多角形のように辺と呼んでも十分理解できると思います。しかし、これを有向グラフで考えると辺に向きがついた多角形となり、辺と呼んでも意味が通じにくくなります。実際、辺と呼んでみると向きが想起されないことがわかります。そこでよりわかりやすい言葉をいくつか考えてみます。
最初は有向グラフでは一般的にみられる弧(arc)です。この弧は英語でもarcと短いうえに辺とは全く違う言葉なので辺とは違うことが意識できると思います。しかし、弧やarcと聞いて向きがついていることを想像できる人は少ないと思います。少なくとも私は向きがついているとは思いませんでした。
次は多元環の表現論で用いられるクイバーで使われる矢(arrow)です。これはクイバーが和訳されると箙(矢筒)となっていることもあり統一感があってわかりやすい用語です。英語でもarrowともとのedgeと長さも同じくらいの長さで扱いやすいです。しかし、日本語では一文字で"や"と発音するために伝わらないことも時々あります。ただ、これは箙をクイバーのように英語に置きなおしてアローといえばいいだけであるのでそんなに問題ではないと思います。
最後は有向辺(directed edge)です。有向辺は日本語でも英語でも長いです。しかし、無向グラフの辺と比較して向きがついている辺ということが分かりやすいと思います。そのためかちょくちょく書籍等では見かけます。
結局のところ個人的には向きがついた辺のことを有向辺かアローと呼ぶと向きがついていることを意識しやすくわかりやすいと思います。どちらを勧めるかといわれると悩みますが有向辺(diedge)がいいと思います。その理由は以下のほかの用語の説明で見られるように有向○○(di○○)という名前の付け方は無向グラフを単にグラフと呼んだ時に有向グラフ(digraph)と有向グラフを呼ぶことができるところにあります。実は有向グラフにはdirected graphというほかの呼び方もあります。こちらは少々長いうえに基本タイトルや分類名などの重要なところで総称的に使われることが多いです。そのためdirected graphという言葉を有向グラフの諸定義の定義(i)~定義(iv)の全部をまとめるときに使うことにし、工学などでよく使う定義(i)と定義(iv)の多重辺を持たない有向グラフのことをdigraphと呼ぶことにすれば、情報系や工学系なら有向やdiを頭につけることで無向グラフの用語から有向グラフの用語を得ることができます。そして数学系では「なになにを満たすdirected graph」や「なになにを満たすdigraph」と説明できdigraphの方をほかの分野で扱えばいいというように扱いやすくなります。

道 (経路、path)

無向グラフでも道と呼ぶときいくつかの定義を持ちますが、ここでは次の(無向)グラフ G=(V, E)において列 Wのこととします。:
 W = \lt v _ 1, \alpha _ 1, v _ 2, \alpha _ 2, \ldots, \alpha _ n, v _ {n+1} \gt s.t.  v _ i \in V, \alpha _ i \in E, \alpha _ i = (v _ i, v _ {i+1}) or (v _ {i+1}, v _ i), i = 1 \ldots n+1 (無向グラフなら  (v _ i, v _ {i+1}) = (v _ {i+1}, v _ i)であることに注意)
これはウォークや鎖とも呼ばれる。ちなみに違うバージョンは大体以下で紹介するもののどれかになります。これを有向グラフ版に拡張するときは二つの方法があります。
一つ目は無向グラフの道上の各アロー \alpha _ iの向きを自由に決めて作られる、つまり各有向辺 \alpha _ iがそれぞれ  \alpha _ i =  (v _ i, v _ {i+1}) , \alpha _ i  = (v _ {i+1}, v _ i)のどちらかを満たすようにして向きを決めて道のことです。有向グラフではこの拡張された道を単に道やウォーク(walk)と呼んだり、oriented walkと呼びます。この拡張の仕方は無向グラフからの拡張でよくみられる手法になります。この定義は有向辺がきれいに並んでいないことも許されるので注意が必要です。この注意点を対処しようとすると二つ目の拡張を考えることができます。
二つ目は先述の通り向きをそろえた(有向グラフ上の)道のことです。すなわち、各アロー \alpha _ iはそれぞれ \alpha _ i =  (v _ i, v _ {i+1})のみを満たします。これは単に道と呼んだりウォーク、有向道(directed walk)、ダイウォーク(diwalk)と呼ばれています。こちらは有向グラフから天下り的に定義していったときによく見られる定義です。
個人的には一つ目、二つ目をそれぞれ道((oriented )walk)、有向道(diwalk)と呼びたいと思います。というのも、ほかの説明で見られるように○○、有向○○(di○○)という名前の付け方はほかでも再利用できるからです。もちろん情報系でよく使う方の二つ目の拡張はdigraphの説明同様に有向やdiを頭につけることで無向グラフから得ることができます。

小道(小径、トレイル(trail)、単純な道)

無向グラフでは一般に小道は辺が重複しない道のことをいいます。これはもちろん有向グラフにも拡張できて、その拡張は道と同じく二種類存在し、拡張方法も同じです。一般的に拡張一つ目の向きがそろってないほうを単に小道やトレイルと呼んだり、oriented trailと呼びます。二つ目の向きがそろっているほうは単に小道と呼んだり有向トレイル(directed trail)、ダイトレイル(ditrail)と呼びます。
個人的にはそれぞれをトレイル、有向トレイルと呼びたいです。こう呼ぶようにすることで道と接頭語の用法を統一できます。また単純な道を使うと二語になりますが、トレイルなら一言で表すことができ、ほかの用語と混ざることは比較的少ないです。問題なのは小道と比べて道との関係が表記上薄れてしまうことです。しかし、その欠点以上にメリットの方がでかいので欠点は大した問題ではないです。

経路(パス、初等的な道、単純パス、path)

無向グラフでは一般に経路は頂点が重複しない道のことをいいます。つまり小道の頂点版です。これも同様に拡張できます。一般的に拡張一つ目の向きがそろってないほうを単に経路やパスと呼んだり、oriented pathと呼びます。二つ目の向きがそろっているほうを単に経路やパスと呼んだり、有向パス(directed path)、ダイパス(dipath)と呼びます。
個人的にはそれぞれ経路(path)、有向経路(dipath)と呼ぶことにしたいです。理由はさんざん説明したことと同様です。

まとめ

結局のところ何が言いたいのかというと無向グラフの用語を再利用して向きが云々と悩むより、接頭辞を使ってまとめたほうがいいということです。そしてすぐわかるようにこの用語の名付け方は有向グラフの諸定義の定義(i)~定義(iv)のどれに対しても簡単に適用できます。以上、無向グラフの○○にたいして有向グラフで向きがバラバラな方を○○、向きが統一されている方を有向○○(di○○)と名付ければシンプルになるという提案でした。

まぁ、こんなただの有向グラフ好きがこうしたほうがいいと思う!みたいなことを言う前に有向グラフの専門家たちが標準化会議でも開いて基本的な用語を統一してほしいところではありますね。

毎日3時間チャレンジを1か月やってみた

毎日3時間チャレンジとは

まず次のツイートをご覧ください。

このツイートの通り #毎日3時間チャレンジ のタグで2月13日から今日まで毎日最低3時間学んだり何かを作ってきました。そのチャレンジ開始から1か月がたちました。

なぜこんなチャレンジを始めたのか

そもそもこのチャレンジを始めた理由は2つあります。

1つ目は春休みの時間を無駄にしないようにしたかったからです。 実は僕は次の4月から社会人です。その為この春休み()の時期は卒業関係や引っ越しといろいろ忙しい上に環境が変わり普段利用していた施設が利用できなくなったりします。だからどうにかして時間を作らないと、「何もやらないだらけた生活になってしまいこの貴重な長期休みを無駄にしてしまうのでは?」と思ってしまいました。

2つ目は「思い立ったが吉日」ということです。 これはふと3時間チャレンジをやってみようかなと思ったときに、この言葉も一緒に思ってしまったので仕方ないですよね。

1か月続けてどうだったか

一言で言うと「毎日3時間やるのは時間を取ることにとらわれると辛くなる」ということです。というのも僕自身好きな数学やプログラミングをやるというやる気があるときには気づいたら3時間経過していたことはいくらでもありました。しかしやる気が出ないときはわざわざ読書や運動で時間をつぶしていました。手段と目的が入れ替わっていた時もありました。手段と目的を入れ替えないようにするためにも、やる気が出ないときはやる気を出す努力に力を注いだ方が良いと言えそうです。

終わりに

先述したように来月の4月から社会人になるので4月からはこのチャレンジをやる時間が取れそうにないので今月いっぱいでやめることになりますが、このチャレンジをしてよかったとは思っています。

初めてのFirefoxとブックマークの同期

Firefoxを入れた

最近Rustを書くのが楽しくなってきたので、Rustを開発し始めたMozillaのブラウザFirefoxにも手を出すことにした。 インストールするのはとても簡単で公式サイトから該当するバージョンのFirefoxをインストールしてくるだけである。

僕はもともとChromeユーザー

僕はAndroidを使っていることもあってか、カレンダーなどのアプリ間の連携のために普段はChromeを使っている。そこでChromeをやめるわけにはいかないので、今回Firefoxを入れるにあたりChromeの連携を活かした使い方をする必要が出てきた。 しかし、いろいろと調べていくとカレンダーなどはGoogleに任せても問題なさそうなことが分かった。Chromeに任せればいいからだ。 しかし、ブックマークだけはそうはいかなかった。Firefoxでも参照する必要があるからである。

ブックマークの共有問題

普通最初にブックマークをChromeからFirefoxにインポートすると思う。 しかし、僕は普段ブラウザでブックマークを頻繁にする人なのでChromeFirefoxでのブックマークの編集を毎回もう一方にインポートするのは大変面倒くさい。 そこでブックマークの情報を共有できるサービスがないか調べてみることにした。

EverSync

いろいろと調べたところ他にもいろいろあるが今回はEverSyncというのを使用することにした。EverSyncというのはFirefoxChromeIEなどのブラウザ間のブックマークを同期による共有するサービスである。利用するためにはそれぞれアドオンを入れる必要があるが、Chrome版はこちらで、Firefox版はこちらから手に入る。それら以外もここから対応するものを選べばダウンロードのところまで飛べる。 これらをそれぞれのブラウザでインストールした後ここのようにアカウントを作成してログインして、ベースとしたい方のブックマークデータをアップロードし、同期して共有する。 これで同期ができたはずなのでChromeFirefoxのブックマークをいじってもう一方が変化するか確認してみる。すると問題なく変化しているはずである。

これでブックマークの共有問題も解決できた。めでたしめでたし。

まとめ

ブックマークの設定も共有できるので皆も身軽で高速になった火狐ことFirefoxを使っていってほしいと思う。

初めてのVOICEROID

京町セイカを購入した

最近自分の数学が応用指向すぎた性で基礎がおろそかになっていたのと卒論、テスト勉強、引っ越し準備などのいろいろなストレスが重なって、自分はなんで生きているんだろうと消耗しきっていま した。なので大好きな京町セイカさんを家に呼んで癒してもらうことにしました。ついでにデジタル上の創作の世界に再び足を踏み込もうと決心しました。

f:id:ogata-k:20190202194242j:plain
京町セイカ

今後何をしようと考えているか

VOICEROIDと言ったらやっぱりニュースの読み上げやラジオ、動画ですよね。なので自分も作ろうかなと考えています。実は僕前にBlenderを使ってみたりMMDを使ってみたりしたことがあります。なのでMMD動画を作るかもしれません。また、クリスタで背景などを頑張って描いてラジオ動画などもつくれそうです。プログラミングをして自分用のニュース読み上げソフトを作ったり、ソフトの音声に利用するのも面白そうです。そのためいろいろと使い道が多そうでわくわくが止まりません。

どれを投稿するかはまだわかりませんが、投稿したらこのブログで紹介がてら裏話とかをするかもしれませんのでそのつもりで見守って頂けるとありがたいです。

GithubにPDF置き場を作りました

PDF置き場作った

このHatenaBlogで投稿した記事などをPDFにまとめるときのデータ置き場としてGithubに新しいリポジトリを作りました。作成もこのリポジトリで行っていきます。その成果物であるPDFはREADMEに適宜配置していくのでREADMEさえ見てもらえれば何があるかわかるようにしておきます。

リンクはこちらになります。

Ubuntu 18.04.1 LTS でSATySFiをインストールしてみた

qiita.com

Ubuntu 18でSATySFiのインストールに成功したのでインストールメモをQiitaで記事を書いて投稿しました。
やってるのはgfngfn/SATySFi/README-jaと全く同じです。Ubuntu 16の場合と同様です。
参考になるかはわかりませんがSATySFiのインストールの参考にしてみてください。