第七章 图

图的基本概念

相邻

关联

支配集

设图$G=$是简单无向图，$S⊆V,S≠∅$，若对于$∀x∈V-S$，$x$都与$S$里至少一个顶点相邻，则称$S$是图$G$的支配集(dominating set)。

$S$是图$G$的支配集，若S的任何真子集都不是支配集，则称$S$为图$G$的极小支配集(minimal dominating set)。

图的矩阵表示

关联矩阵 M(D) M(G)

有向图的关联矩阵

无环有向图$D=, V={v_1,v_2,…,v_p},E={e_1,e_2,…,e_q}$

$p×q$ 阶矩阵$M(D)=(m{ij}) {p×q}$,其中

$m_{ij} = \begin{cases}
1 & \text{若vi是ej的起点}\
-1 & \text{若vi是ej的终点}\
0 & \text{若vi不关联ej}
\end{cases}$

离散数学 II 实验一（实验报告）

20020007095-叶鹏

盛艳秀-老师

实验题目

可简单图化、连通图、欧拉图和哈密顿图的判断

可图化

设非负整数数列d=( d1,d2, …, dn ),若存在无向图G, 使得G的度数列是d, 则称d为可图化的.

可简单图化

设非负整数列d=( d1,d2, …, dn ),若存在无向简单图G, 使得G的度数列是d,则称d为可简单图化的.

平面图

在平面上边与边不在非顶点处相交的图

平面嵌入

画在平面上使得边与边不在 非顶点处相交的图

• 可平面图主要表明图具有平面性质,平面嵌入是平面图的一种表示形式,平面图的平面嵌入不唯一