グラフ理論
こちらで代数的確率論・量子確率論のことを書いた その中に出てくる隣接代数というものを整理する 隣接行列とは、いわゆるグラフの行列のことで、エッジで結ばれたノードに対応する要素が１でそれ以外が０であるような行列のこと グラフは有限かも無限かもし…
伊原のゼータ函数と言うのがある プライムサイクル P についての式 これが、エッジ形式の表現になるという話がある ２つめの式だと、Wのサイズは(mはグラフのエッジ本数)なので、uの最大次数は2mになる 1つめの式だと、uの最大次数は大きくなりうる この乖離…
完全グラフはp個のノードを持つグラフで、すべてのノードペアにエッジがある(無向)グラフ これのゼータ関数は ただし、 ちなみににも定義された式になっている。の場合は項がキャンセルアウトして、結果としては、すべてとなる my.ihara.n <- function(p){ s…
資料 伊原のゼータ関数を非正則グラフにまで拡張したのが橋本のゼータ関数で ただし、uは複素数、mとnはグラフGのエッジ数とノード数、はMの行列式で、Iはノード数ｘノード数の単位行列、AはGの隣接行列、DはGのノードの次数を対角成分とする対角行列 ちなみ…
隣接行列Aのm乗の(i,j)要素の値は、i,j間のグラフ距離 3.1 Eigenvalues n完全グラフの隣接行列の固有値は、1がn-1重で-1が1個。p,q-完全2部グラフのそれはとp+q-2重の0 Full-cycle permutation matrix of order nの場合、隣接行列の固有値は、 n頂点を結ぶパ…
10.1 Majorization ベクトルの要素の和が等しいような２つのベクトルがあって、その累積和ベクトルの要素のすべてについて、後者のそれが前者のそれ以上であるとき、前者は後者でMajorzationされているという そのMajorizationでできる行列がある 10.2 Thres…
Distance を考えるとき、最短経路のみが問題になるが、非最短経路との相対的な関係で最短経路とその距離とを考えることも有用。そのような距離がResistance distance Laplacianの章で出てきた行列H(g-inverse of L)を使うと となる 三角不等式も成り立つ ネ…
2.1 ランク 有向グラフGのn個のノードと、m個のエッジ。nxm行列で、エッジの始点と終点とを1,-1で表したもの、それがIncidence matrix Q(G) Q(G)の列和はゼロ、行ベクトルは線形非独立 連結グラフのランクはn-1、k個の連結グラフの集合ならランクはn-k k個の…
木のDistance matrixの場合、 木でないグラフのDistance matrixの場合は、サイクルとそうでない部分(木)に分けて行く 木のDistance matrixのLaplacian、固有値を考えることで有用な性質がある
Laplacian matrixの最小固有値は0。二番目に小さい固有値をalgebraic connectivityと言う。非連結グラフのalgebraic connectivityは0。完全グラフのそれはn 7.1 Preliminary results 7.2 Classification of trees(Types I and II) 7.3 Monotocinicty propert…
グラフはノードとエッジでできており、それにIDを振ると色々な行列が出来る 行列は正方行列と非正方行列とがある 非正方行列の代表はIncidence matrix(ノードとエッジの関係を表した行列) 正方行列はノードｘノードの行列があり、いろいろある グラフの特徴…
全ノードの次数が等しいグラフがRegular 6.1 Perron-Frobenius theory 成分が正である実正方行列には唯一つの最大実固有値が存在し、それに対応する固有ベクトルの各成分は厳密に正である、という主張。グラフのノードの重みづけ(ページランク)計算などに用…
Incidence matrix Qのnull spaceをcycle subspace、Q^Tのnull space を cut subspaceと呼ぶ edgeのセットをうまく取り出して足し合わせると、キャンセルアウトするのがcycleなので、incidence matrixのcolumnsの線形和でゼロベクトルができれば、その線形和…
1.1 Matrices 行列、転置、対角行列 Trace and determinent ベクトル空間とランク Minorsは行の一部と列の一部とを取り出した部分行列。と書くと、行の部分集合S、列の部分集合TでのMinor。はSとTの補集合によるMinor。は１行、１列を除いたMinor 特に、行と…
エッジが無いノードペアは0、エッジありのペアは-1、対角成分はノードの次数であるような行列がLaplacian matrix L=D-A (ただし、Dは対角行列で対角成分がノードの次数、Aはadjacency matrix) L=Q Q^T (ただしQはincidence matrix)でもある Lは対称で半正定…
Graphs and Matrices (Universitext)作者: Ravindra B. Bapat出版社/メーカー: Springer発売日: 2014/10/02メディア: ペーパーバックこの商品を含むブログを見る 目次 1 Preliminaries 2 Incidence Matrix 3 Adjacency Matrix 4 Laplacian Matrix 5 Cycles a…
毛虫グラフを描く library(igraph) n <- 8 ke <- sample(1:5,n,replace=TRUE) e.l <- NULL for(i in 2:n){ e.l <- rbind(e.l, c(i-1,i)) } v.id <- n+1 for(i in 1:n){ for(j in 1:ke[i]){ e.l <- rbind(e.l, c(i,v.id)) v.id <- v.id +1 } } g <- graph.edg…
トポロジカル・インデックス: フィボナッチ数からピタゴラスの三角形までをつなぐ新しい数学作者: 細矢治夫出版社/メーカー: 日本評論社発売日: 2012/08/20メディア: 単行本（ソフトカバー） クリック: 5回この商品を含むブログ (3件) を見る フィボナッチ数…
収束の少し遅い数列 芋づる式の解 ヘロンの三角形
ピタゴラスの三角形 ピタゴラスの定理 既約ピタゴラスの三角形 互いに素 既約・準既約 拡張既約ピタゴラス三角形 ピタゴラスの三角形の戸籍・系統分類 芯グラフ バーニングとホールの行列 野蛮で大胆な推論と厳密な証明・理論のほころびの繕い作業 ケイリー-…
ユークリッドの互除法 最大公約数 剰余 商 変数変換 カッシーニの等式 広義の グラフの分割 分割公式 数論
連分数展開 不定方程式 ペル方程式 整数解 無限循環連分数 鏡映対称な数列 連分多項式 ディオファントスの不定方程式 解の振る舞い 突然発狂したような振る舞い アルゴリズム 対数 フェルマーの無限降下法 数論 必要条件 必要十分条件 部分グラフ間に成立す…
単環グラフ ルカ三角形 変型二項係数 n次元の世界の原子の原子起動の角度部分の縮合度 量子力学 シュレーディンガー方程式 マッチング多項式 組合せの集合(ザックス・グラフ) ザックスの定理 グラフのスペクトル 特性多項式の零点 オイラーの定理 正多面体グ…
グラフ理論 頂点・辺 集合 空グラフ 隣接 向き 無向単純グラフ 連結グラフ 経路グラフ 星グラフ 木グラフ 非木グラフ 櫛グラフ 単環グラフ 歯車グラフ 完全グラフ 添え字 毛虫グラフ 中心点 埋め込み 直鎖経路グラフ 非隣接数 z-数え上げ多項式 組合せ論 パ…
数列 多項式 フィボナッチ数 ルカ数 ウサギの増殖問題 黄金比 漸化式 第i項 フィボナッチ数・ルカ数・ペル数・ペル-ルカ数 複数の定義 場合の数 パターン ドミノ タイリング グラフ理論 マッチング １因子の問題 不飽和共役炭化水素 ケクレ(Kekule)構造式 ２…
トポロジカル・インデックス: フィボナッチ数からピタゴラスの三角形までをつなぐ新しい数学作者: 細矢治夫出版社/メーカー: 日本評論社発売日: 2012/08/20メディア: 単行本（ソフトカバー） クリック: 5回この商品を含むブログ (3件) を見る トポロジカル・…
