数学建模第四章 图与网络模型及方法

无向图：$G = (V , E)$

有向图：$D = (V , A)$

有向边又称为弧。

$V$ 是点集，$E$ 是边集，$A$ 是弧集合。

弧 $a_k = (v_i , v_j)$ 表示 $v_i \to v_j$，$v_i$ 称为始端，$v_j$ 称为末端或终端。$a_k$ 称为 $v_i$ 的出弧，也称为 $v_j$ 的入弧。

环：即自环。

重边：端点是同一对顶点的多条边

简单图：无环无重边。

完全图：任意两顶点均相邻的简单图。

赋权图：带权的图。

子图：点集边集都被包含。

生成子图：在是子图的情况下点集相同。

道路：$W = v_0e_1v_1e_2\cdots e_kv_k$。

迹：各边相异。

轨道：各顶点相异。

回路：起点和终点重合的道路。

圈：起点和重点重合的轨道。

连通的：顶点 $u$ 到顶点 $v$ 有道路。

连通图：任意两点连通的图。

连通分支：分连通图中的连通子图。

无向图邻接矩阵 $W = (w_{ij})_{n\times n}$

有向图邻接矩阵 $W = (w_{ij})_{n\times n}$

无向赋权图 $W = (w_{ij})_{n\times n}$

graph % 无向图
diagraph %有向图