概要
Pythonでネットワーク分析をする際に登場する用語集を整理しました。
今後も追加していく予定です。
- 頂点(vertex)
- グラフを構成する点(ノードと呼ばれることもある)
- 辺(edge)
- 頂点を結ぶ線(エッジと呼ばれることもある)
- 有向グラフ(directed path)
- 一方通行であるような辺が存在するグラフ
- 無向グラフ(undirected path)
- すべての辺が双方向であるようなグラフ
- 道(path)
- 頂点と辺が代わる代わる連続したもので同じ頂点が二度以上現れないもの
- 強連結
- 任意の２頂点間に道が存在する有向グラフ
- ２頂点間の方向は区別する
- 弱連結
- 各辺の方向を無視した時に任意の２頂点間に道が存在する有向グラフ
- 次数
- ある頂点に繋がっている辺の数のこと
- 自身に入ってくる辺の数を「入次数」、出て行く辺の数を「出次数」とよぶ
- 重み付きグラフ
- 各々の辺に数字が書いてあるもので数字は「重み」という
- 数個の頂点を通る経路について、始点と終点が同じ頂点になる場合を「閉路」という
- ある頂点から頂点への経路について、通過する辺の重みの和が最小になる経路を「最短経路」という
- 数個の頂点を通る経路について、始点と終点が同じ頂点になる場合を「閉路」という
- 木
- 閉路を持たないグラフのこと
- 一番上の頂点を「根」、一番したの頂点を「葉」と呼ぶ
- 自分より上の頂点を「親」、下の頂点を「子」という
- （辺の数）＝（頂点の数）－１である
- 一番上の頂点を「根」、一番したの頂点を「葉」と呼ぶ
- 二部グラフ
- 頂点を２つのグループに分けた時に、同じグループ内の頂点同士を結ぶ辺が無く、別々のグループの頂点同士を結ぶ辺しかないようなもの