一、完全图

完全图 概念 :

• 1.条件 1 : $G$ 为 $n(n\ge 1)$ 阶无向简单图 ;
• 2.条件 2 : 若 $G$ 中每个顶点 均与 其余的 $n-1$ 个顶点相邻 ;
• 3.结论 : 则称 $G$ 为 $n$ 阶 无向完全图 , 记做 $K_n$ ;

$G$ 的顶点集是 $V(G)$ , 其顶点个数为 $|V(G)|$ , 则称 $G$ 为 $n$ 阶图 ;

---

二、 二部图

二部图概念 :

• 1.条件 1 : 图 $G$ 的顶点集划分为两个非空子集 $X$ 和 $Y$ ;
• 2.条件 2 : 一条边 有一个端点 在 $X$ 中 , 另一个端点在 $Y$ 中 ;
• 3.结论 : 满足上述条件 , 称 $G$ 是二部图 或 偶图 ;
• 4.标记 : 记做 $G=(X\cup Y,E)$ , $(X,Y)$ 是 $G$ 的一个划分 ( 二分类 ) ;

其中 $(a)$ 是二部图 , $(b)$ 也是二部图 , 其不明显 , 改变 $(b)$ 中顶点 和 边 位置 , 可以得到 $(c)$ , 此时就能看出 其是 二部图 ;

注意 : 二部图的一边中 不允许有边相连 ;

$G$ 指的是 Graphic 图 ;
$E$ 指的是 Edge 边 ;
$V$ 指的是 Vertext 顶点 ;

三、完全二部图

完全二部图概念 :

• 1.条件 1 : 简单二部图 $G=(X\cup Y,E)$
• 2.条件 2 : 如果 $X$ 中的 每个顶点 与 $Y$ 中的每个顶点都有边连接 ;
• 3.结论 : 满足上述条件 的 二部图 $G$ , 称为完全二部图 ;
• 4.记法 : $|X|=m$ , $|Y|=n$ , 此完全二部图 记做 $K_{m,n}$ ;
• 5.特殊存在 : $K_{1,n}$ 称为星 ;

$G$ 指的是 Graphic 图 ;
$E$ 指的是 Edge 边 ;
$V$ 指的是 Vertext 顶点 ;

---

四、 连通性概念

图中两个顶点的连通 :

• 条件 $1$ : 如果在图 $G$ 中 , 存在两个顶点 $u,v$ ;
• 条件 $2$ : 两个顶点之间存在 $(u,v)$ 路 ;
• 结论 : 满足上述条件 , 则称 点 $u,v$ 在图 $G$ 中连通 ;

涉及到的其它概念 :


途径 : 顶点和边的交替出现的序列 , 其顺序符合图中的位置即可 ;
迹 : 每个边不能相同的 途径 ;
路 : 每个点都不相同的 迹 ;


这三个概念 , 一个比一个严格 ;


闭途径 : 起点 和 终点 相同的 途径 ;
闭迹 : 起点 和 终点 相同的 迹 , 也称 回路 ;
圈 : 起点 和 终点 相同的 路 ;

$G$ 指的是 Graphic 图 ;
$E$ 指的是 Edge 边 ;
$V$ 指的是 Vertext 顶点 ;

---

五、连通图

连通图 : 图 $G$ 中 , 任意两个顶点都连通 , 那么这个图 $G$ 是连通图 ;

---

六、 图的分支

图的分支 :

• 条件 1 : 图 $G$ 顶点集 $V(G)$ 划分为若干非空子集 { V 1 , V 2 , ⋯   , V n } \{V_1, V_2, \cdots , V_n\} {V1​,V2​,⋯,Vn​} ;
• 条件 2 : 两个顶点 属于 同一个 子集 , 当且仅当 它们 在 $G$ 中连通 ;
• 满足上述条件 : 称 每个子图 $G[V_i]$ 是 图 $G$ 的一个分支 ; $(i=1,2,3,\cdots ,n)$

$G$ 指的是 Graphic 图 ;
$E$ 指的是 Edge 边 ;
$V$ 指的是 Vertext 顶点 ;

---

七、 欧拉回路 ( 闭迹 / 回路 ) [ 遍历图中所有的边 | 每个边只经过一次 | 顶点可经过多次 ]

欧拉回路 : 图 $G(V,E)$ , $E$ 中所有边的回路 ( 闭迹 ) 称为 欧拉回路 ;

涉及到的其它概念 :
…
途径 : 顶点和边的交替出现的序列 , 其顺序符合图中的位置即可 ;
迹 : 每个边不能相同的 途径 ;
路 : 每个点都不相同的 迹 ;
…
这三个概念 , 一个比一个严格 ;
…
闭途径 : 起点 和 终点 相同的 途径 ;
闭迹 : 起点 和 终点 相同的 迹 , 也称 回路 ;
圈 : 起点 和 终点 相同的 路 ;
…
$G$ 指的是 Graphic 图 ;
$E$ 指的是 Edge 边 ;
$V$ 指的是 Vertext 顶点 ;

---

八、 欧拉定理

欧拉定理 :

无向图 存在 欧拉回路 的 充要条件 :

① 图是连通的 ;

② 图中 没有 度数是奇数的顶点 ;

与顶点 $v$ 关联的边数之和 ( 环算 $2$ 条边 ) 就是该顶点的度 , 记作 $d(v)$

---

九、 哈密顿圈 ( 闭路 / 圈 ) [ 遍历图中所有的顶点 | 每个顶点只经过一次 ]

图 $G=(V,E)$ 中 , 从 某顶点出发 , 将所有顶点遍历一遍 , 每个顶点只经过一次 ;

$G=(V,E)$ , $G$ 中经过 $V$ 中所有顶点的 圈 , 称为 哈密顿圈 ;

$G=(V,E)$ , $G$ 中经过 $V$ 中所有顶点的 道路 , 称为 哈密顿道路 ;

涉及到的其它概念 :
…
途径 : 顶点和边的交替出现的序列 , 其顺序符合图中的位置即可 ;
迹 : 每个边不能相同的 途径 ;
路 : 每个点都不相同的 迹 ;
…
这三个概念 , 一个比一个严格 ;
…
闭途径 : 起点 和 终点 相同的 途径 ;
闭迹 : 起点 和 终点 相同的 迹 , 也称 回路 ;
圈 : 起点 和 终点 相同的 路 ;
…
$G$ 指的是 Graphic 图 ;
$E$ 指的是 Edge 边 ;
$V$ 指的是 Vertext 顶点 ;

---

十、 哈密顿圈 相关定理

定理 :

设 $G(V,E)$ 是 $n(n\ge 2)$ 个顶点的 简单图 , 如果 任意 一对顶点的度数之和 大于等于与 $n-1$ , 则 $G$ 中一定有 哈密顿道路 ;

推论 :

设 $G(V,E)$ 是 $n(n\ge 3)$ 个顶点的 简单图 , 如果 任意 一对顶点的度数之和 大于等于与 $n$ , 则 $G$ 中一定有 哈密顿道路 ;

注意这里是任意 一对顶点的度数之和 大于等于 $n(n\ge 3)$ , 所有的能找出来的 顶点都要满足该条件 ;

---

十一、 平面图

平面图 定义 :

• 1.条件 : $G=<V,E>$ 是 一个 无向图 ;
• 2.行为 : 将 $G$ 的所有的节点 和 边 画在 平面上 , 使 任何 两条边 除了端点外 没有 其他 的交点 ;
• 3.结论 : 满足上述要求 , $G$ 是平面图 ;

平面图的特殊情况 , 改变边的形状可以使相交的边不相交 , 这个图是平面图 ;

有些图 表面上看 , 有相交的边 , 但是不能肯定其不是 平面图 , 改变某些边的形状 , 可以使各个边不相交 , 那这个图还是平面图 ;
如下图 , 左图有相交的边 , 但是把边拉出来到外侧 , 各个边可以不相交 , 因此该图是平面图 ;

有些图其边相交 , 但是无论怎么改变其 顶点位置 和 边的形状 , 总是有相交的边 , 那么这个图不是平面图 ;

---

十二、 面的次数 与 边数 定理 ( 面次数之和 = 边数两倍 ) ★

设 $G$ 是有限平面图 , 面的次数之和 等于 边数 的两倍 ;

有限平面图中 , 边在平面中划分的区域成为面 , 包围每个面的边的个数成为面的次数 , 又称为面的度数 ;

• 有限区域 : 有限面 , 三角形内部的面
• 无线区域 : 无限面 , 三角形外部的面

---

十三、 欧拉定理 ★

$G$ 是平面连通图 , $v$ 是顶点数 , $e$ 是边数 , $r$ 是面数 ;

欧拉公式 : $v-e+r=2$

( 该公式 是 顶点 边 面 之间的关系 , 没有面的度数 )

面的度数之和 是 $2e$ , 可以与上面组成方程组 , 前提是 $G$ 是平面连通图 ;

$v$ : 顶点数 ;
$e$ : 边数 ;
$r$ : 面数 ;
$d_{all}$ : 所有面度数之和 ;
公式 1 : $2e=d_{all}$ , 设 $G$ 是有限平面图 , 面的次数之和 等于 边数 的两倍
公式 2 : $v-e+r=2$
公式 3 : $G$ 是平面图 $\Rightarrow$ $e\le 3v-6$
助记 : 三角形 : 3 个顶点 , 3条边 , 2个面 ( 内部一个面 , 外部一个面 )

---

十四、 平面图的 必要条件 定理 ( 平面图 满足 e 小于等于 3v -6 条件 ) ★

$G$ 是简单连通平面图 , 其顶点数 $v\ge 3$ , 其边数 $e$ ;

那么 $e\le 3v-6$ ;

如果是平面图 , 那么公式一定成立 ;
公式成立 , 这个图不一定是平面图 ;

该定义用来证明该图不是平面图 , 公式不成立 , 那么该图一定不是平面图 ;

---

十五、 图的模型应用★

题目 :

• 条件 $1$ : 一个班级的学生选修 $A,B,C,D,E,F$ 六门课程 ;
• 条件 $2$ : 一部分人同时选修 $D,C,A$ , 一部分人同时选修 $B,C,F$ , 一部分人选修 $B,E$ , 还有一部分人选修 $A,B$
• 问题 : 要求安排考试 , 不能有学生连续两天参加考试 ;

解题思路 :

• 1.构造图 : 每门课程当做一个顶点 , 共同被选修的课程用边相连 ;
• 2.构造补图 : 将其它顶点用虚线连起来 , 虚线部分是上图的补图 ;
• 3.找哈密顿道路 : 在 补图中 中找到一个哈密顿道路 即可 , 道路沿线顶点就是每天考试课程 ;

黑色的边是共同选修的课程连接在一起 ;

红色的边是补图 ;

从红色边中找出一个哈密顿圈 , 对应的哈密顿道路就是结果 ;

哈密顿圈中 , 每个顶点都不能重复 ;

哈密顿道路为 : $B\to D\to F\to A\to E\to C$

---

十六、 完全图★

题目 : $G$ 是 $n$ 个顶点的 简单连通平面图 , 且每个面的度数都是 $3$ , 求此图的边数 $e$ , 面数 $r$ ;

$v$ : 顶点数 ;
$e$ : 边数 ;
$r$ : 面数 ;
$d_{all}$ : 所有面度数之和 ;
公式 1 : $2e=d_{all}$ , 设 $G$ 是有限平面图 , 面的次数之和 等于 边数 的两倍
公式 2 : $v-e+r=2$
公式 3 : $G$ 是平面图 $\Rightarrow$ $e\le 3v-6$
助记 : 三角形 : 3 个顶点 , 3条边 , 2个面 ( 内部一个面 , 外部一个面 )

涉及到的相关概念 :

• 1. 图的几个属性 : 顶点数 $v$ , 边数 $e$ , 面数 $r$ , 面的度数之和 $D$ ;
• 2. 面的度数之和 是 边数的两倍 :
  $D=2e$
• 3. 欧拉定理 :
  $v-e+r=2$

解 :

① 列出方程 1 : 顶点数 $v=n$ , 每个面度数是 $3$ , 那么 度数之和 是 $3r$ ;

先根据 面的度数之和 = 边数两倍写出方程 :

$3r=2e$
$r=\frac{2e}{3}$

② 列出方程 2 : 根据欧拉定理 $v-e+r=2$ 写出下面方程
$n-e+r=2$

③ 解方程 : 使用 $n$ 表示 $e,r$ 即可 ;

$n-e+\frac{2e}{3}=2$
$e=3(n-2)$
$r=\frac{2e}{3}=2(n-2)$

---

十七、 握手定理 题目★

题目 : 证明空间中不可能存在这样的多面体 , 其面数是奇数 , 每个面都由奇数条线段围成 ;

证明 :

① 用反证法 , 假设存在这样的多面体 $H$ , 其面数 是 奇数 , 每个面 都有 奇数条线段围成 ;

将空间中的多面体 与 平面中的平面图 建立一一对应关系

② 构造多面体 及 对应的 图 :
构造图 : 如果有这样的多面体 , 以 此 多面体的面集合 为顶点 , 构造图 $G$ ;
构造图中连线标准 : 当且仅当 $H$ 中 两个面 有公共边界时 , 才能在 $G$ 中 两个面 对应的 两个顶点 之间连一条边 ;

③ 提取关键信息 : 提取其中构造图 $G$ 的 顶点个数 和 顶点的度 信息 ;
$H$ 有奇数个面 , 代表着 $G$ 有奇数个顶点 ,
$H$ 中每个面 都有 奇数条线段 , 代表 $G$ 中每个点的度数都是奇数 ;

④ 使用握手定理证明该假设不成立 :
握手定理 : 图的所有顶点度数之和等于边的两倍 ; ★
握手定理推论 : 奇数个顶点的个数 必定是 偶数个 ; ★

图 $G$ 中 顶点的个数是奇数个 , 每个顶点的度是奇数 , 与握手定理 及 推论 冲突 , 假设不成立 ; 因此这种多面体不存在 ;

---