文章目录

一、完全图
二、二部图
三、完全二部图
四、连通性概念
五、连通图
六、图的分支
七、欧拉回路 ( 闭迹 / 回路 ) [ 遍历图中所有的边 | 每个边只经过一次 | 顶点可经过多次 ]
八、欧拉定理
九、哈密顿圈 ( 闭路 / 圈 ) [ 遍历图中所有的顶点 | 每个顶点只经过一次 ]
十、哈密顿圈相关定理
十一、平面图
十二、面的次数与边数定理 ( 面次数之和 = 边数两倍 ) ★
十三、欧拉定理 ★
十四、平面图的必要条件定理 ( 平面图满足 e 小于等于 3v -6 条件 ) ★
十五、图的模型应用★
十六、完全图★
十七、握手定理题目★

一、完全图

完全图概念 :

1.条件 1 : $\geq 1)$
$n (n \geq 1)$ 阶无向简单图 ;
2.条件 2 : 若
$n - 1$ 个顶点相邻 ;
3.结论 : 则称 $K_n$
$K_{n}$ ;

G

G

$G$ 的顶点集是

V

(

G

)

V(G)

$V (G)$ , 其顶点个数为

∣

V

(

G

)

∣

|V(G)|

$∣ V (G) ∣$ , 则称

G

G

$G$ 为

n

n

$n$ 阶图 ;

二、二部图

二部图概念 :

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

在这里插入图片描述

其中

(

a

)

( a )

$(a)$ 是二部图 ,

(

b

)

( b )

$(b)$ 也是二部图 , 其不明显 , 改变

(

b

)

( b )

$(b)$ 中顶点和边位置 , 可以得到

(

c

)

( c )

$(c)$ , 此时就能看出其是二部图 ;

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

G

G

$G$ 指的是 Graphic 图 ;

E

E

$E$ 指的是 Edge 边 ;

V

V

$V$ 指的是 Vertext 顶点 ;

三、完全二部图

完全二部图概念 :

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

在这里插入图片描述

G

G

$G$ 指的是 Graphic 图 ;

E

E

$E$ 指的是 Edge 边 ;

V

V

$V$ 指的是 Vertext 顶点 ;

四、连通性概念

图中两个顶点的连通 :

条件
$1$ : 如果在图

G

G

$G$ 中 , 存在两个顶点

u

,

v

u,v

$u, v$ ;
条件
$2$ : 两个顶点之间存在

(

u

,

v

)

(u,v)

$(u, v)$ 路 ;
结论 : 满足上述条件 , 则称 点
$G$ 中连通 ;

涉及到的其它概念 :

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

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

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

G

G

$G$ 指的是 Graphic 图 ;

E

E

$E$ 指的是 Edge 边 ;

V

V

$V$ 指的是 Vertext 顶点 ;

五、连通图

连通图 : 图

G

G

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

G

G

$G$ 是连通图 ;

六、图的分支

图的分支 :

条件 1 : 图 $\{V_1, V_2, \cdots , V_n\}$
${V_{1}, V_{2}, \dots, V_{n}}$ ;
条件 2 : 两个顶点属于同一个子集 , 当且仅当它们在
$G$ 中连通 ;
满足上述条件 : 称每个子图 $G[V_i] G[Vi] 是图 G G G 的一个分支 ; ( i = 1 , 2 , 3 , ⋯ , n ) ( i=1,2,3,\cdots,n )$
$(i = 1, 2, 3, \dots, n)$

G

G

$G$ 指的是 Graphic 图 ;

E

E

$E$ 指的是 Edge 边 ;

V

V

$V$ 指的是 Vertext 顶点 ;

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

欧拉回路 : 图

G

(

V

,

E

)

G(V,E)

$G (V, E)$ ,

E

E

$E$ 中所有边的回路 ( 闭迹 ) 称为 欧拉回路 ;

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

G

G

$G$ 指的是 Graphic 图 ;

E

E

$E$ 指的是 Edge 边 ;

V

V

$V$ 指的是 Vertext 顶点 ;

八、欧拉定理

欧拉定理 :

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

① 图是连通的 ;

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

与顶点

v

v

$v$ 关联的边数之和 ( 环算

2

2

$2$ 条边 ) 就是该顶点的度 , 记作

d

(

v

)

d(v)

$d (v)$

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

图

G

=

(

V

,

E

)

G=(V,E)

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

G

=

(

V

,

E

)

G=(V,E)

$G = (V, E)$ ,

G

G

$G$ 中经过

V

V

$V$ 中所有顶点的圈 , 称为哈密顿圈 ;

G

=

(

V

,

E

)

G=(V, E)

$G = (V, E)$ ,

G

G

$G$ 中经过

V

V

$V$ 中所有顶点的道路 , 称为哈密顿道路 ;

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

G

G

$G$ 指的是 Graphic 图 ;

E

E

$E$ 指的是 Edge 边 ;

V

V

$V$ 指的是 Vertext 顶点 ;

十、哈密顿圈相关定理

定理 :

设

G

(

V

,

E

)

G(V,E)

$G (V, E)$ 是

n

(

n

≥

2

)

n (n\geq 2)

$n (n \geq 2)$ 个顶点的简单图 , 如果任意一对顶点的度数之和 大于等于与

n

−

1

n-1

$n - 1$ , 则

G

G

$G$ 中一定有哈密顿道路 ;

推论 :

设

G

(

V

,

E

)

G(V,E)

$G (V, E)$ 是

n

(

n

≥

3

)

n (n\geq 3)

$n (n \geq 3)$ 个顶点的简单图 , 如果任意一对顶点的度数之和 大于等于与

n

n

$n$ , 则

G

G

$G$ 中一定有哈密顿道路 ;

注意这里是任意一对顶点的度数之和大于等于

n

(

n

≥

3

)

n(n\geq3)

$n (n \geq 3)$ , 所有的能找出来的顶点都要满足该条件 ;

十一、平面图

平面图定义 :

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

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

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

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

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

设

G

G

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

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

有限区域 : 有限面 , 三角形内部的面

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

十三、欧拉定理 ★

G

G

$G$ 是平面连通图 ,

v

v

$v$ 是顶点数 ,

e

e

$e$ 是边数 ,

r

r

$r$ 是面数 ;

欧拉公式 :

v

−

e

+

r

=

2

v - e + r = 2

$v - e + r = 2$

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

面的度数之和是

2

e

2e

$2 e$ , 可以与上面组成方程组 , 前提是

G

G

$G$ 是平面连通图 ;

v

v

$v$ : 顶点数 ;

e

e

$e$ : 边数 ;

r

r

$r$ : 面数 ;

d

a

l

l

d_{all}

$d_{a l l}$ : 所有面度数之和 ;
公式 1 :

2

e

=

d

a

l

l

2e = d_{all}

$2 e = d_{a l l}$ , 设

G

G

$G$ 是有限平面图 , 面的次数之和 等于边数 的两倍
公式 2 :

v

−

e

+

r

=

2

v -e + r = 2

$v - e + r = 2$
公式 3 :

G

G

$G$ 是平面图

⇒

\Rightarrow

$\Rightarrow$

e

≤

3

v

−

6

e \leq 3v - 6

$e \leq 3 v - 6$
助记 : 三角形 : 3 个顶点 , 3条边 , 2个面 ( 内部一个面 , 外部一个面 )

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

G

G

$G$ 是简单连通平面图 , 其顶点数

v

≥

3

v\geq3

$v \geq 3$ , 其边数

e

e

$e$ ;

那么

e

≤

3

v

−

6

e \leq 3v - 6

$e \leq 3 v - 6$ ;

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

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

十五、图的模型应用★

题目 :

条件
$1$ : 一个班级的学生选修

A

,

B

,

C

,

D

,

E

,

F

A,B,C,D,E,F

$A, B, C, D, E, F$ 六门课程 ;
条件
$2$ : 一部分人同时选修

D

,

C

,

A

D,C,A

$D, C, A$ , 一部分人同时选修

B

,

C

,

F

B,C,F

$B, C, F$ , 一部分人选修

B

,

E

B,E

$B, E$ , 还有一部分人选修

A

,

B

A,B

$A, B$
问题 : 要求安排考试 , 不能有学生连续两天参加考试 ;

解题思路 :

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

在这里插入图片描述

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

红色的边是补图 ;

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

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

哈密顿道路为 :

→

B \to D \to F \to A \to E \to C

$B \to D \to F \to A \to E \to C$

十六、完全图★

题目 :

G

G

$G$ 是

n

n

$n$ 个顶点的简单连通平面图 , 且每个面的度数都是

3

3

$3$ , 求此图的边数

e

e

$e$ , 面数

r

r

$r$ ;

v

v

$v$ : 顶点数 ;

e

e

$e$ : 边数 ;

r

r

$r$ : 面数 ;

d

a

l

l

d_{all}

$d_{a l l}$ : 所有面度数之和 ;
公式 1 :

2

e

=

d

a

l

l

2e = d_{all}

$2 e = d_{a l l}$ , 设

G

G

$G$ 是有限平面图 , 面的次数之和 等于边数 的两倍
公式 2 :

v

−

e

+

r

=

2

v -e + r = 2

$v - e + r = 2$
公式 3 :

G

G

$G$ 是平面图

⇒

\Rightarrow

$\Rightarrow$

e

≤

3

v

−

6

e \leq 3v - 6

$e \leq 3 v - 6$
助记 : 三角形 : 3 个顶点 , 3条边 , 2个面 ( 内部一个面 , 外部一个面 )

涉及到的相关概念 :

1. 图的几个属性 : 顶点数
$D$ ;
2. 面的度数之和是边数的两倍 :
3. 欧拉定理 :

解 :

① 列出方程 1 : 顶点数

v

=

n

v=n

$v = n$ , 每个面度数是

3

3

$3$ , 那么度数之和是

3

r

3r

$3 r$ ;

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

3r = 2e

$3 r = 2 e$

r=\cfrac{2e}{3}

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

② 列出方程 2 : 根据欧拉定理

v

−

e

+

r

=

2

v-e+r=2

$v - e + r = 2$ 写出下面方程

−

n-e+r=2

$n - e + r = 2$

③ 解方程 : 使用

n

n

$n$ 表示

e

,

r

e,r

$e, r$ 即可 ;

−

n-e+\cfrac{2e}{3}=2

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

(

−

)

e=3(n-2)

$e = 3 (n - 2)$

(

−

)

r=\cfrac{2e}{3} =2(n-2)

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

十七、握手定理题目★

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

证明 :

① 用反证法 , 假设存在这样的多面体

H

H

$H$ , 其面数是奇数 , 每个面都有奇数条线段围成 ;

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

② 构造多面体及对应的图 :
构造图 : 如果有这样的多面体 , 以此多面体的面集合为顶点 , 构造图

G

G

$G$ ;
构造图中连线标准 : 当且仅当

H

H

$H$ 中两个面有公共边界时 , 才能在

G

G

$G$ 中两个面对应的两个顶点之间连一条边 ;

③ 提取关键信息 : 提取其中构造图

G

G

$G$ 的顶点个数和顶点的度信息 ;

H

H

$H$ 有奇数个面 , 代表着

G

G

$G$ 有奇数个顶点 ,

H

H

$H$ 中每个面都有奇数条线段 , 代表

G

G

$G$ 中每个点的度数都是奇数 ;

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

图

G

G

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

【图论】简单概念及公式入门 ( 完全图 | 二部图 | 连通图 | 欧拉回路 | 哈密顿圈 | 平面图 | 欧拉定理 )

文章目录

一、完全图

二、二部图

三、完全二部图

四、连通性概念

五、连通图

六、图的分支

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

八、欧拉定理

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

十、哈密顿圈相关定理

十一、平面图

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

十三、欧拉定理 ★

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

十五、图的模型应用★

十六、完全图★

十七、握手定理题目★

相关推荐

一个分享Java & Python知识的社区

文章目录

一、完全图

二、 二部图

三、完全二部图

四、 连通性概念

五、连通图

六、 图的分支

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

八、 欧拉定理

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

十、 哈密顿圈 相关定理

十一、 平面图

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

十三、 欧拉定理 ★

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

十五、 图的模型应用★

十六、 完全图★

十七、 握手定理 题目★

相关推荐

一个分享Java & Python知识的社区

二、二部图

四、连通性概念

六、图的分支

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

八、欧拉定理

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

十、哈密顿圈相关定理

十一、平面图

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

十三、欧拉定理 ★

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

十五、图的模型应用★

十六、完全图★

十七、握手定理题目★