图

无向图 $G=<V,E>$, 其中 $V\ne \varnothing$ 为顶点集, $E$ 为 $V\&V$ 的多重集, 元素为无向边.

有向图 $D=<V,E>$, $E$ 是 $V\times V$ 的多重子集.

n 阶图

$n$ 个顶点的图为 $n$ 阶图.

没有一条边的 $n$ 阶图称为 $n$ 阶零图.

指向原始笔记的链接

平凡图

只有一个顶点, 没有边的图.

也称为 $1$ 阶零图.

指向原始笔记的链接

邻域和关联集

$G$ 为无向图, $v\in V(G)$,

• $v$ 的邻域 $N(v)=\{u|u\in V(G)\wedge (u,v)\in E(G)\wedge u\ne v\}$,
• $v$ 的闭邻域 $\overline{N}(v)=N(v)\cup \{v\}$,
• $v$ 的关联集 $I(v)=\{e|e\in E(G)\wedge e\text{与}v\text{关联}\}$.

$D$ 为有向图, $v\in V(D)$,

• $v$ 的后继元集 ${\Gamma }_D^{+}(v)=\{u|u\in V(D)\wedge <v,u>\in E(D)\wedge u\ne v\}$,
• $v$ 的先驱元集 ${\Gamma }_D^{-}(v)=\{u|u\in V(D)\wedge <u,b>\in E(D)\wedge \ne v\}$,
• $v$ 的邻域 $N_D(v)={\Gamma }_D^{+}(v)\cup {\Gamma }_D^{-}(v)$,
• $v$ 的闭邻域 ${\overline{N}}_D(v)=N_D(v)\cup \{v\}$.

指向原始笔记的链接

多重图

含平行边的图.

指向原始笔记的链接

简单图

既不含平行边也不含环的图.

指向原始笔记的链接

顶点的度

设 $G=<V,E>$ 为无向图, $\forall v\in V,d(v)$ 为 $v$ 的度数.

设 $D=<V,E>$ 为有向图, $\forall v\in V$, $d^{+}(v)$ 为 $v$ 的出度, $d^{-}(v)$ 为 $v$ 的入度, $d(v)=d^{+}(v)+d^{-}(v)$ 为 $v$ 的度.

$\Delta (G)$ 为最大度, $\delta (G)$ 为最小度.

${\Delta }^{+}(D),{\delta }^{+}(D),{\Delta }^{-}(D),{\delta }^{-}(D),\Delta (D),\delta (D)$.

奇度顶点和偶度顶点.

指向原始笔记的链接

握手定理

任何无向图中, 顶点度数之和为边数的两倍.

任何有向图中, 顶点度数之和为边数的两倍, 入度之和等于出度之和, 等于边数.

• 任何图中, 奇度顶点的个数是偶数.

指向原始笔记的链接

度数列

$V$ 为无向图 $G$ 的顶点集, 则 $d(v_1),d(v_2),...,d(v_n)$ 为 $G$ 的度数列.

$V$ 为有向图 $D$ 的顶点集, $d(v_1),d(v_2),...,d(v_n)$ 为 $D$ 的度数列, $d^{+}(v_1),d^{+}(v_2),...,d^{+}(v_n)$ 为 $D$ 的出度列, $d^{-}(v_1),d^{-}(v_2),...,d^{-}(v_n)$ 为 $D$ 的入度列.

• 非负整数列 $d=(d_1,d_2,...,d_n)$ 是可图化的, 当且仅当 ${\sum }_{i=1}^n{d}_i$ 为偶数.
• 设 $G$ 为任意 $n$ 阶无向简单图, 则 $\Delta (G)\le n-1$.

指向原始笔记的链接

图的同构

$G_1,G_2$ 为两个图, 若存在双射函数 $f:V_1\to V_2$, 对于 $v_i,v_j\in V_1$, $(v_i,v_j)\in E_1$ 当且仅当 $(f(v_i)),f(v_j))\in E_2$, 并且 $(v_i,v_j),(f(v_i),f(v_j))$ 重数相同, 则 $G_1,G_2$ 是同构的, 记作 $G_1\cong G_2$.

图的同构关系具有自反性, 对称性, 传递性.

指向原始笔记的链接

n 阶完全图

每个顶点与其他顶点均相邻的 简单图.

$n$ 阶无向完全图记为 $K_n$.

指向原始笔记的链接

n 阶竞赛图

基图为 $K_n$ 的有向简单图.

$m=\frac{n(n-1)}{2},\Delta =\delta =n-1$.

指向原始笔记的链接

k-正则图

设 $G$ 为 $n$ 阶无向简单图, 若 $\forall v\in V(G)$ 均有 $d(v)=k$, 则 $G$ 为 k- 正则图.

$m=\frac{nk}{2}$.

彼得松图

彼得松图是 3- 正则图.

指向原始笔记的链接

指向原始笔记的链接

子图

$G=<V,E>,G^{\prime }=<V^{\prime },E^{\prime }>$,

• 若 $V^{\prime }\subseteq V$ 且 $E^{\prime }\subseteq E$, 称 $G^{\prime }$ 是 $G$ 的子图, 记为 $G^{\prime }\subseteq G$.

• 若 $G^{\prime }\subseteq G$ 且 $V^{\prime }=V$, 称 $G^{\prime }$ 为 $G$ 的生成子图.

• 若 $V^{\prime }\subset V$ 或 $E^{\prime }\subset E$, 称 $G^{\prime }$ 为 $G$ 的真子图.

• $G$ 中两个端点都在 $V^{\prime }$ 中的边组成边集 $E^{\prime }$ 的子图称为 $V^{\prime }$ 的导出子图, 记作 $G[V^{\prime }]$.

• $G$ 中与 $E^{\prime }$ 中的边关联的顶点组成的顶点集 $V^{\prime }$ 的子图称为 $E^{\prime }$ 的导出子图, 记作 $G[E^{\prime }]$.

指向原始笔记的链接

补图

$G=<V,E>$, 以 $V$ 为顶点集, 以所有使 $G$ 成为完全图 $K_n$ 的添加边组成的集合为边集的图, 称为 $G$ 的补图, 记为 $\overline{G}$.

若 $G\cong \overline{G}$, 称 $G$ 为自补图.

指向原始笔记的链接