Profile cover photo
Profile photo
Shimizu Nobutaka
6 followers
6 followers
About
Shimizu's posts

Post has attachment
駆け足で学ぶ「グラフマイナー定理」
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つである グラフマイナー定理 について、その中身と研究背景をグラフ理論の観点から可能な限りちゃんと書いていきたいと思います. なお本記事では「グラフ」とは単に有限グラフのことを指すこととします.  章の構成は以下です. グラフマイナー定理の凄さをアピールす...

Post has attachment
全順序・半順序・擬順序
概要  数学では様々な順序を考えることがあります. 一番簡単な例で言うと実数の全体 $\mathbb{R}$ において, $x,y\in \mathbb{R}$に対し$y-x\geq 0$ を $x\leq y$と定義して順序集合$(\mathbb{R},\leq)$を考えることが多いです. 実数だけではなく, 例えばグラフ理論でも順序を考えたりすることがあります.  本記事では, 順序の公理について述べ, 全順序・半順序・擬順序について一気に述べたのちに例を幾つか挙げたいと思います. 解説単語 : 擬順序(...

Post has attachment
有名な東大の問題
1998年の東大の後期入試の問題で、「大学入試史上で最も難しい問題」といわれているみたいですがグラフ理論の問題なので、解いてみることにします。 問題文にある二つの操作(白頂点の追加、辺の細分)をそれぞれ(I), (II)と記すことにします。 小さい例で試すと、 長さ$3n+2$のパスは生成できなくて、長さ$3n$もしくは$3n+1$のパスは生成できないっぽいので答えとしてはこれになることが簡単に予想できると思います。でも長さ$3n+2$のパスが生成できないことを示すのが難しいです。 少し考えて見ると, 長さ$...

Post has attachment
The Unfounded Moore Graph
Abstract  グラフ理論で60年くらい前から研究されてきている "Degree Diameter Problem" という問題があります. 本記事ではこれについて簡単な説明を与えます. そしてこの問題の最適解の一つである "Moore Graph"  について書いていきます. しかし今現在もなお, とある Moore Graph は今もなお見つかっておらず, 存在しないのではないかとさえ言われています. (存在性の否定も肯定も2017年2月2日現在未解決です).   未だにみつかっていない Moore ...

Post has attachment
条件付期待値のキモチ
条件付期待値についてなんとなくつかめてきた気がしたので備忘録がてら書きます. 勉強中なので些細なところで間違えてるかもしれません. (逐次修正していく) *今回は確率変数は全て標本空間から実数への関数だとします. 条件付確率というのはP(A | B)で, P(A | B) := P(A ∩ B) / P(B) として定義されます. これをもとにして条件付期待値 E(X | A) は E(X | A) := Σx P(X=x | A) などと定義され, これはよく慣れ親しんだものだと思います. しかし測度論的な...

Post has attachment
Tutte 多項式入門
概要 最近 Tutte 多項式が面白いと思ったのでこれについて書きます. 今回はTutte 多項式の定義とその気持ちについて簡単に述べた後, Tutte 多項式についての予想の一つである Merino-Welsh 予想[1]について書きます. 1. 連結グラフの全域木の個数 連結グラフ G=(V, E) があるときにGが含む全域木の個数を t(G) と表すことにします. Gの辺 e={x, y}   (eは自己ループでないとする) に対して G から e を削除して得られるグラフを G-e と書き, G ...

Post has attachment
Localization and centrality in networks
読んだ論文の内容について書いています。 論文のタイトルは Localization and centrality in networks で http://journals.aps.org/pre/abstract/10.1103/PhysRevE.90.052808 にあります。 Physical Reviewという物理学の中で最も権威ある学術雑誌の2014年の論文です。 内容をかいつまんで要約すると  グラフの各頂点の 重要度(centrality) として、そのグラフの隣接行列の第一固有値に対応する 固...

Post has attachment
全点間最短経路の求め方
概要 最近研究で重みなし連結正則グラフの全点間の最短経路を求めることが多く、ちょっと工夫したらちょっとだけ早くなったのでそれについて簡単に書きます。 素朴な方法 一番素朴な方法としては幅優先探索があります。 全ての頂点から幅優先探索をして全点間の最短経路を全て計算する方法です。 アルゴリズム ところである点から幅優先探索を行うと図のように三角形みたいな図が出てくると思います。                 幅優先探索をやっているとキューに頂点を取り出しては突っ込んでを繰り返して最短距離を計算していくわけです...

Post has attachment
摩訶不思議系魔法ランキング
それでも色々数学について勉強していると何かと「ホンマかそれ」と思うような, まさに 「魔法」 のような定理やアルゴリズムに出会い数学って面白く奥深いなぁと感じることがあると思います. そこで僕が今まで出会ってきた「魔法」の中で非常に印象の深かったものの中で深夜にパッと思いついた分だけ列挙していきます. タイトルにランキングとありますがランキングではありません. 列挙です. 多分グラフ理論についてが多いです. 理論部門 ・貪欲法が上手くいく ⇔ マトロイド   「行列のようなもの」という意味をもつマトロイドは,...

Post has attachment
位相空間と可測空間の対比
前までは位相空間や可測空間と聞くとどうしても「オェ...」ってなってしまっていたのですが、最近になってザリスキー位相やマルチンゲールについて学んでいくうちにどうしてもこれらの単語について知っておかねばならなくなったので少し勉強しました. 「位相空間」の定義と「可測空間」の定義は意外と似ているので対比して紹介しようと思います. 参考文献として  Real and Complex Analysis  (著: Walter Rudin) を挙げます. 以下, 位相空間に関する諸定義を T , 可測空間に関する定義を...
Wait while more posts are being loaded