紙媒体で知識や経験を管理すると無くなりがちなのでブログで管理することにしました.
      殆どの記事は自分自身のためだけに書いているため,他人に見せる前提の内容, 文章ではありません.
      また, ブログのコメント欄を解放していたらbotからの迷惑行為を受けたため現在コメント欄は解放しておりません.

グラフ理論

【グラフ理論】 オイラーグラフについて

「オイラーグラフ」という考え方は,「中国人郵便配達問題」を考える際に重要になってくる. 中国人郵便配達問題とは, 正の重み付き無向グラフについて, 重みの和が最小となる閉路(閉じた道)を求める問題である.まずはオイラーグラフについて考える. オイラー…

【グラフ理論】 隣接行列について諸定理

グラフ理論勉強会No.04隣接行列は頂点から頂点への辺の本数を表すものである. 単純グラフではループが無いため, 対角成分の要素は0である.行列の表し方には 隣接行列 接続行列 隣接リスト などの表現方法がある. 定理1.10 ループを含まない(p,q)-グラフGの点…

【グラフ理論】 次数について諸定理

グラフ理論勉強会No.03 用語 次数 頂点vに接続する辺の本数 などで表す. 孤立点 次数0の頂点 (グラフGの)最大次数, 最小次数 それぞれと表す. 偶点, 奇点 偶数, 奇数の次数の頂点 平均次数 一頂点あたりから出ている辺の個数. 定理1.5 (握手の補題) (p,q)-…

【グラフ理論】 ダイキストラ法

グラフ理論勉強会No.02ダイキストラ法とは重みが最小である道を求めるために用いられているアルゴリズムの一つ. (最短経路問題の中では, 2頂点対最短経路問題で辺の重みが非負の有向グラフに適応できるアルゴリズムという位置づけらしい. この問題を解くアル…

【グラフ理論】 グラフの半径と直径の関係

グラフ理論勉強会No. 01定理1.2 説明: まずrad, diamの説明の前に離心数を定義する必要がある. 離心数とは, 連結グラフGの点vにおいて で定義される数. グラフの半径rad(G)とは各頂点における離心数の最小値で定義される数. グラフの直径diam(G)とは各頂点に…