邻接、关联
G = (V; E)
vertex: n = |V|
edge|arc : e = |E|
邻接关系 (adjacency): 相邻接的两个顶点之间的关系
关联关系 (incideace): 顶点与邻接边之间的关系
无向、有向
若邻接顶点 U 和 V 的次序无所谓
则 (U, V) 为无向边 (undirected edge)
例: 若 U 是 V 的好友，则 V 也必是 U 的好友
所有边都是无向的图，即无向图 (undigraph)
反之，有向图 (digraph) 中均为有向边 (directed edge)
U、V 分别称作边 (U, V) 的尾 (tail) 、头 (head)
例: U 欠 V 的钱 与 V 欠 U 的钱
路径、环路
路径: π = <V(0), V(1), ..., V(k)>
长度: |π| = k
简单路径: V(i) = V(j) 除非 i = j
环/环路: V(0) = V(k)
有向无环图 (DAG)
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
