グラフ
グラフ(Graph)
頂点を線分で結んだ図形をグラフと呼ぶ
節点(node)、点(point)だったりもする
線分は辺(edge)と呼ぶ
code:mermaid
flowchart LR
a(("頂点1"))---|"辺1"|b(("頂点2"))
単純グラフ$ G は$ V(G) と$ E(G) から成る。 ループや多重辺を含まないものが単純グラフ
ループや多重辺を含むものは多重グラフ
ループや多重辺を含む + 有効グラフの場合は箙(えびら、クィバー)と呼ばれる $ V(G)
$ V(G) は$ G の点集合(vertex set)
$ V(G) \neq \emptyset で、有限集合
点、頂点(vertex) or 節点(node) or ノード
$ E(G)
$ E(G) は$ G の辺集合(edge set)
辺(edge)は$ (v, w) の形で表す
$ v は始点
$ w は終点
$ E(G) = \{(v, w)\}
辺の数は高々1本
次数(degree)
点から出ている辺の数
ループは2本として数える
接続する辺の数
数式だと$ \mathrm{deg}(v) を使うらしい
code:mermaid
flowchart LR
node1((v1)) --- node2((v2))
node3((v3)) --- node2
node4((v4)) --- node3
node4 --- node4
次数を得るdegree(v: Node)的な関数があったとする。
degree(v1)の結果は1
degree(v2)の結果は2
degree(v3)の結果は2
degree(v4)の結果は3
確認用
Q. グラフ
Q. 単純グラフ
Q. 次数
参考
関連
メモ