今天想要总结的内容是无向图。
1 定义
图G=（V，E）由节点的有限非空集合V和节点无序对偶集合E组成。其中，
V={N1, N2, ..., Nm}
E={e1, e2, ..., ep}
N1，N2，...，Nm为节点，e1，e2，...，ep为边，而某一条边ek又等于(Ni，Nj)。
(Ni，Nj)是无序对偶集，即(Ni，Nj)=(Nj，Ni)。
2 节点的度
节点的度是以该节点作为端点的边的条数，也就是有几条边连着这个点。例如上图中N1的节点的度是2，N4的节点的度是3，记作deg(N1)=2，deg(N4)=3。
3 关联矩阵
如图1，边e1=(N1,N2)，因此关联矩阵e1列的取值为[1,1,0,0,0,0,0]，同理，关联矩阵e2列的取值为[1,0,0,1,0,0,0]，由此可得出每条边的取值。因此图1所示线性图的关联矩阵如图2所示。对于一个m个节点和n条边的图，其关联矩阵是一个m✖️n的矩阵。
根据关联矩阵可以轻易地求出每个节点的度，只需将关联矩阵对应行的元素相加即可。
4 相邻矩阵
相邻矩阵行和列的对象都是节点，如果两个节点可以形成一条边，则在相邻矩阵相应处的值为1，否则为0。例如，e1=(N1,N2)，因此第一行第二列和第二行第一列的值均为1。图1所示线性图的相邻矩阵如图3所示。
同样根据相邻矩阵也可以轻易地求出每个节点的度，只需将节点对应的行或列的元素相加即可。
5 路径
路径是一系列的边，可以描述为边序列或者是节点序列。如图4所示为由图1得到的三条路径。事实上，可以通过相邻矩阵与其本身的乘积得到路径。例如，图4中路径N1和N6可以由相邻矩阵（1,4）和（4,6）相乘得到。
6 连接性
当Ni和Nj在同一路径上时，Ni和Nj是被连接的。
图的组件是相连节点的最大集合。图1的图由两个组件：{N1,N2,N3,N4,N5,N6}和{N7}。
7 压缩图
压缩图通过用压缩节点替代每个组件构成。个人理解，图1压缩图的两个压缩节点即为两个组件，显然，这两个组件不是等价的，因此也就避免了冗余。压缩图中没有边的概念，因为所有的压缩节点是不存在连接性的。
8 圈数
圈复杂度：图G的圈数V(G)=e-n+p，其中：
e是G中的边数，n是节点数，p是组件数。
V(G)是图中不同区域的个数。个人理解是节点不变的情况下，边数越多显然代码的复杂性也越高，而组件数越大显然代码的复杂性也越高，因此可以用圈复杂度来衡量代码复杂性。当然查阅其他资料发现这个圈复杂度还有其他的计算方法，下回再分解吧。
参考资料：
《软件测试》第二版 Paul C. Jorgensen 韩柯 杜旭涛 译
