第1节图的基本概念 定理2任一个图中,奇点的个数为偶数 o证明设V和V分别是G中奇点和偶点的集 合,由定理1,有 ∑d+∑6∑≥2 因∑是偶数,∑d也是偶数,故∑“) 必定也是偶数,从而V的点数是偶数。 17 清华大学出版社
第1节 图的基本概念 v 定理2 任一个图中，奇点的个数为偶数。 ¢ 证明:设V1和V2分别是G中奇点和偶点的集 合，由定理1，有 1 2 v V v V v V v v v 2q d( )d( )d( ) ¢ 因 是偶数， 也是偶数，故 必定也是偶数，从而V1的点数是偶数。 v V v d( ) 2 v V v d( ) 1 v V v d( ) 清华大学出版社 17
第1节图的基本概念 图论中几个重要记号和术语(续) o给定一个图G=(VE)和一个点、边交错序 列(v,en,V,…,,,v),如果满足 e=[v,v](=1,2,…,k 则称为一条联结和的链,记为 称点v2,V…,v1为链的中间点。 清华大学出版社
则称为一条联结 的链，记为 称点 为链的中间点。 v 图论中几个重要记号和术语（续） ¢ 给定一个图G=(V,E)和一个点、边交错序 列 , 如果满足 第1节 图的基本概念 1 1 2 k 1 k 1 k ( ) i i i i i i v ,e ,v , ,v ,e ,v t t t 1 [ ] i i i e v ,v (t=1，2，…，k-1) 1 2 k 1 k ( ) i i i i v ,v , ,v ,v 2 3 k 1 i i i v ,v ,v 1 k i i v 和v 清华大学出版社 18
第1节图的基本概念 图论中几个重要记号和术语(续) 链(", 中,若v=”,则称之为 个圈,记为(v,”…,,n)。 若链 )中,点 都是不同的,则称之为初等链;若圈 (nn2…;n)中,v,n…,,都是不同的 刂称之为初等圈。 o若链(圈)中含的边均不相同,则称之为简 单圈。以后说到链(圈),除非特别交代, 均指初等链(圈)。 清华大学出版社
v 图论中几个重要记号和术语（续） ¢ 链 中，若 ，则称之为 一个圈，记为 。 ¢ 若链 中，点 都是不同的，则称之为初等链；若圈 中， 都是不同的， 则称之为初等圈。 ¢ 若链(圈)中含的边均不相同，则称之为简 单圈。以后说到链(圈)，除非特别交代， 均指初等链(圈)。 第1节 图的基本概念 1 2 k 1 k ( ) i i i i v ,v , ,v ,v 1 k i i v v 1 2 k 1 1 ( ) i i i i v ,v , ,v ,v 1 2 k 1 k ( ) i i i i v ,v , ,v ,v 1 2 k 1 k i i i i v ,v , ,v ,v 1 2 k 1 1 ( ) i i i i v ,v , ,v ,v 1 2 k 1 i i i v ,v , ,v 清华大学出版社 19
第1节图的基本概念 令例子 o图10-9中,("n,,3是一条简单链,但不是初 等链,(,2n,m)是一条初等链。图中不存在联结 v1和v的链。 (n,n2n2,n,n)是一个初等圈,(,)是简 单圈,但不是初等圈。 e 初等链与初等圈 图10-9 清华大学出叔
v 例子 ¢ 图10-9中， 是一条简单链，但不是初 等链， 是一条初等链。图中不存在联结 v1和v9的链。 ¢ 是一个初等圈， 是简 单圈，但不是初等圈。 第1节 图的基本概念 v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 v1 ,v2 ,v3 ,v6 ,v7 v1 ,v2 ,v3 ,v4 ,v1 v4 ,v1 ,v2 ,v3 ,v5 ,v7 ,v6 ,v3 ,v4 初等链与初等圈 图10-9 清华大学出版社 20
第1节图的基本概念 令连通图 o图G中,若任何两点之间至少有一条链,则称G是连通 图,否则称为不连通图。 o若G是不连通图,它的每个连通的部分称为G的一个连 通分图(也简称分图)。 o图10-9是一个不连通图,它有两个连通分图。 清华大学出版社
第1节 图的基本概念 v 连通图 ¢ 图G中，若任何两点之间至少有一条链，则称G是连通 图，否则称为不连通图。 ¢ 若G是不连通图，它的每个连通的部分称为G的一个连 通分图(也简称分图)。 ¢ 图10-9是一个不连通图，它有两个连通分图。 清华大学出版社 21