・頂点の集合Vと辺の集合Eとして、グラフはG＝＜V,E＞と表現する
・グラフGはpコの点とqコの互いに素な点の非順序対からなる集合Eをもった、空でない有限集合V＝V(G)から構成される
・グラフGは位数p、規模qをもつという
・Eにおける点の対e＝{u,v}はGの辺と呼ばれ、eはuとvを結合している
・e＝uvと書き、uとvは隣接しているという
・ある点が隣接する他の点の数を次数とよぶ
・点の接合関係があるときを1、ないときを0で表した行列を隣接行列という。
《距離》
・歩道：点と辺が代わる代わる連続したもの
・歩道の長さ：その歩道において辺が出現する回数
・道：同じ点が2度以上現れないもの
・グラフGにおいて、どの2点u-vにおいても道が存在するとき、Gは連結しているという
・連結グラフGにおいて、2点u,vの間の道の長さの最小値を距離、その道のことを測地線という
《密度》
・グラフの各点からすべての他の点に辺が存在するとき、そのグラフを完備グラフという
・密度：グラフGの辺の数とそれが完備グラフであったときの辺の数の比（実際の結合数／最大可能結合数）
・ダイグラフとは方向のあるグラフのことで、辺ではなく弧と呼ばれる
・出ていく弧の数と入ってくる弧の数を区別でき、出次数・入次数と呼ぶ
・通路とは互いに方向のある弧に連続的につながっている歩道のことで、ひとつでも違う方向を向いた弧が混ざっている場合は半通路という
・点iから点jへ長さr以下の通路が存在する場合、点jは点iからr‐到達可能と呼ばれる
・点iが点jに到達可能であるとき、その成分rij=1、そうでないときは0で表される行列を到達可能性行列という
・隣接行列Aをn乗したとき、そのij成分は点iからjへの長さnの歩道の数を表す
《結合の類型》
・弱結合：点iと点jの間に長さr以下の半通路が存在する
・片方結合：点iと点jの間に長さr以下の通路が存在する
・強結合：点iと点jの間の両方に長さr以下の通路が存在する
・再帰結合：点iと点jの間に長さr以下の通路が存在し、点iと点jの間に同じ点を使う逆の順番の通路が存在する
《推移性》
・点AからB、BからCに結合関係があり、AからCに結合があるとき、それを推移的であるという
・ダイグラフDの推移度は Tran(D) = ∑(A2×A)／∑(A2 - diagA2) と表す
※A2はAの2乗を示す。diagは行列の対角成分のみを取り出す。
・弧にあらゆる種類の値を与えたダイグラフを重みつきグラフといい、ネットワーク流を求めるのに便利である
・実数値に限らず、さまざまな｢値｣（ex.好意・権力・影響）を弧に与えたグラフをバイグラフという
・点が辺に属している様を表現したのがハイパーグラフで、点が多重的に辺に接続している関係を表していて（これを示す行列を接合行列という）、個人のグループへの所属関係を表すのに用いられる。
・隣接行列 adjacency matrix
・道 path (歩道 walk)
・連結 connected
・測地線 geodesic
・推移性 transitivity
・到達可能性行列 reachability matrix
・接合行列 incidence matrix
ゲーム理論合宿で利用したパワーポイントファイルがダウンロードできます。
さらに勉強したい方は教科書を買うべし。
CogniTom Academic Designによるbookreader.jsを利用しています