PDF《离散数学基础：图论》

4

第一章 图的基本概念 (3) 删除子图:设G = (V , E )是G的子图,则G ? G = (V, E ? E );

(4) 边的收缩:设边e = (u, v)∈E,G\e表示从G中删除边e后,将e的两个端点u和v用一个新顶 点w(或用u或v充当w)代替,使w关联e以外u和v关联的所有边,称为边e的收缩;

(5) 添加新边:设u, v∈V (u, v可能相邻,也可能不相邻,G ∪ (u, v)或G + (u, v)表示在u, v之间加 一条边(u, v),称为添加新边. 注意,G ? V 不仅要将G中那些在V 中的顶点删除,而且要将这些顶点相关联的边也删除,因 为边是不难单独存在的,它一定要与两个顶点关联,而G ? E 只将G中那些在E 中的边删除,不改 变G的顶点.特别地,当V = {v},只有一个顶点时,将G ? V 记为G ? v,类似地有G ? e.对于有 向图,也可类似地定义有向图删除顶点集、边集及子图的操作. 定义 1.1.12 对于无向图G = (V, E),设|V | = n,即G有n个顶点,则称G = Kn ? G为G的补图. 下面我们定义顶点的度数: 定义 1.1.13 对于无向图G = (V, E),定义顶点v∈V 的度数(degree)d(v) = |{e∈E | e = (u, v) 或e = (v, u)}|,也即d(v)是v所关联的边数,但若e = (v, v)是环,则边e要计算两次. 对于有向图G = (V, E),定义顶点v∈V 的入度d? (v) = |{e∈E | e = u, v }|,则d+ v是以v为终 点的边数;

定义顶点v∈V 的出度d+ (v) = |{e∈E | e = v, u }|,则d+ v是以v为起点的边数;

定义定 点v∈V 的度数d(v) = d? (v) + d+ (v). 度数为0的顶点称为孤立顶点,度数为1的顶点称为悬挂顶点,与它关联的边称为悬挂边.很简 单地,可证明下面的定理: 定理 1.1.14 握手定理:对于任意的无向图G = (V, E),有: v∈V d(v) = 2|E|;

对于任意的有向 图G = (V, E),有: v∈V d? (v) = v∈V d+ (v) = |E|. 后面称度数为奇数的定点为奇度顶点,度数为偶数的顶点为偶度顶点.很容易地,根据握手定 理,有如下推论: 推论 1.1.15 任何图(无向图或有向图)的奇度顶点个数是偶数. 例子 1.1.16 很显然,对于n个顶点的完全图Kn,因为每个顶点都与其它n ? 1个顶点有边,因此 每个顶点的度数都是n ? 1,从而 d(v) = n(n ? 1),因此Kn的边有n(n ? 1)

2 条. 例子 1.1.17 (耿素云教材[1]p213习题七第2题) :设9阶无向图G中,每个顶点的度数不是5就是6,证明G中至少有5个6度顶点,或至少有6个5度顶点. 证明 由握手定理,G的度数为5的顶点个数为偶数个,也即可能为0,2,4,6,8个,由于图G的顶 点度数不是5就是6,因此相应地,度数为6的顶点就为9,7,5,3,1个,显然这五种情况都表明G中至少 有5个6度顶点或至少有6个5度顶点. 定义 1.1.18 设G = (V, E)是无向图,V = {v1, v2,vn},称(d(v1), d(v2)d(vn))为图G的度 数列(degree sequence).对于任意给定的非负整数列d = (d1, d2,dn),如果它是某个图的度数 列,则称d是可图化的(graphical);

如果它是某个简单图的度数列,则称d是可简单图化的. 1.1 图的基本定义

5 很容易证明下面的定理: 定理 1.1.19 非负整数列d = (d1, d2,dn)是可图化的当且仅当( n i=1 di) mod

2 = 0. 证明 由握手定理易知,当d是某个图的度数列时有( n i=1 di) mod

2 = 0.反之,若( n i=1 di) mod

2 = 0,则可构造图G,其顶点集是V = {v1, v2,vn},对任意的1 ≤ i ≤ n,若2ki ≤ di <

2ki + 1,则在vi上设置ki条环,这样非负整数列d = (d1 ? 2k1, d2 ? 2k2,dn ? 2kn)中的数要么 是0,要么是1,而且由于( n i=1 di) mod

2 = 0,则其中必定有偶数个1,将这些1所对应的顶点成对地连 一条边,显然得到的图的度数列就是d. 要判断一个非负整数列是否可简单图化则要困难很多,不过下面的定理可以帮助........