简单图

简单图是一种最基本的无向图：每条边连接两个不同的顶点，任意两个顶点之间最多有一条边。它适合描述“两个对象是否有关系”，例如一组人中哪些人互相认识；如果还要记录多种关系或方向，就需要扩展图的模型。

定义与例子

简单图记作 $G=(V,E)$。$V$ 是顶点集合，$E$ 是由 $V$ 中两个不同元素组成的二元子集构成的集合。边 $\{u,v\}$ 也可简写为 $uv$。所以简单图既没有从一个顶点回到自身的环，也没有连接同一对顶点的多重边。以下只讨论有限图。

例如 $V=\{1,2,3,4\}$、$E=\{12,23,31,34\}$。前三条边连接成一个三角形，第四条边把顶点 4 接到顶点 3。顶点 3 的邻居是 1、2、4，因此度为 3；其余三个顶点的度依次为 2、2、1。

图有四个顶点和四条边；顶点三连接其余三个顶点。

边数与度数

设 $n=|V|$、$m=|E|$。每条边有两个端点，把所有顶点的度相加时恰好被计算两次，因此 $$\sum _{v\in V}\mathrm{deg}(v)=2m.$$ 这称为握手引理。例子中度数和 $2+2+3+1=8=2\times 4$。因为总和是偶数，奇数度顶点的个数必为偶数；例子里的顶点 3、4 正好是两个奇数度顶点。

简单图的边从所有不同顶点对中选取，因此 $$0\le m\le (\genfrac{}{}{0ex}{}{n}{2})=\frac{n(n-1)}{2}.$$ 当每一对不同顶点都相邻时，取到上界，这就是完全图 $K_n$。如果 $n=4$，最多有 6 条边；上例还有两对顶点没有边连接。

邻接矩阵

将顶点按 1 至 $n$ 编号，令 $A_{ij}=1$ 表示 $ij\in E$，否则为零。无向性使 $A=A^{𝖳}$；无环使每个对角元素为零。上述例子的邻接矩阵为 $$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 0\\ 1& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right).$$ 每一行的和就是对应顶点的度。不同的顶点编号会改变矩阵中行列顺序，却不一定改变图的结构；相关的比较方法见图同构。

模型的边界

无向边 $uv$ 本身不表示从 $u$ 到 $v$ 的方向。如果用边表达单行交通，就应使用有向图；如果两座城市之间的不同道路必须分别记录，仅用简单图的一个邻接关系会丢失信息。孤立顶点的度为零，仍属于顶点集，不应因为没有边就被删除。