离散数学 多重图与简单图 定义11.3无向图中关联同一对顶点的2条和2条以上的边称为 平行边.有向图中2条和2条以上始点、终点相同的边称为平 行边.平行边的条数称为重数 含平行边的图称为多重图，不含平行边和环的图称为简单图， 定义11.4设G=<V,E>为无向图，HveV,称作为边的端点的次 数之和为v的度数，简称度，记作（吵 设D=<V,E>为有向图，Vv∈y,称作为边的始点的次数之和 为的出度，记作(；称作为边的终点的次数之和为的入 度，记作(y)；称(y)+t(y)为的度数，记作d(v), 6
6 多重图与简单图 定义11.3 无向图中关联同一对顶点的2条和2条以上的边称为 平行边. 有向图中2条和2条以上始点、终点相同的边称为平 行边. 平行边的条数称为重数. 含平行边的图称为多重图, 不含平行边和环的图称为简单图. 定义11.4 设G=<V,E>为无向图, vV, 称v作为边的端点的次 数之和为v的度数, 简称度, 记作d(v). 设D=<V,E>为有向图, vV, 称v作为边的始点的次数之和 为v的出度, 记作d + (v); 称v作为边的终点的次数之和为v的入 度, 记作d − (v); 称d + (v)+d − (v)为v的度数, 记作d(v)
离散数学 顶点的度数 设G=<V,E>为无向图， G的最大度△(G)=max{d(v)川ve G的最小度G=min{d)川v∈乃 设D=<V,E>为无向图， D的最大度(D)=max{d()川v∈ D的最小度D)=min{d(vy川ve D的最大出度(D)=max{(y)川v∈乃 D的最小出度δ+(D)=min{(y)lv∈ D的最大入度(D)=max{d()川v∈仍 D的最小入度6-(D)=min{(y)川v∈乃 悬挂顶点：度数为1的顶点，悬挂边：与悬挂顶点关联的边 偶度（奇度）顶点：度数为偶数（奇数）的顶点 7
7 顶点的度数 设G=<V,E>为无向图, G的最大度(G)=max{d(v) | vV} G的最小度 (G)=min{d(v) | vV} 设D=<V,E>为无向图, D的最大度(D)=max{d(v) | vV} D的最小度 (D)=min{d(v) | vV} D的最大出度 + (D)=max{d + (v) | vV} D的最小出度 + (D)=min{d + (v) | vV} D的最大入度 − (D)=max{d − (v) | vV} D的最小入度 − (D)=min{d − (v) | vV} 悬挂顶点: 度数为1的顶点, 悬挂边: 与悬挂顶点关联的边. 偶度(奇度)顶点: 度数为偶数(奇数)的顶点
离散数学 实例 e e dy1)=4,d(y2)=4,dy3)=2,d(y4)=1, e6 dy5)=3. =4,1. e V3 y4是悬挂点，e是悬挂边. A e d(o)=4,d(o=1,do=5, b d(b)=0,d(b)=3,d(b)=3, 3 es d(c)=2,(c)=1,d(c)=3, d'(0=1,(d0=2,dd0=3, +=4,6+=0,=3,6=1,△=5,83. e 8
8 实例 d(v1 )=4, d(v2 )=4, d(v3 )=2, d(v4 )=1, d(v5 )=3. =4, =1. v4是悬挂点, e7是悬挂边. d + (a)=4, d − (a)=1, d(a)=5, d + (b)=0, d − (b)=3, d(b)=3, d + (c)=2, d − (c)=1, d(c)=3, d + (d)=1, d − (d)=2, d(d)=3, +=4, +=0, − =3, − =1, =5, =3
离散数学 握手定理 定理11.1在任何无向图中，所有顶点的度数之和等于边数的2倍 证G中每条边（包括环）均有两个端点，所以在计算G中各顶 点度数之和时，每条边均提供2度，m条边共提供2m度. 定理11.2在任何有向图中，所有顶点的度数之和等于边数的2倍； 所有顶点的入度之和等于所有顶点的出度之和，都等于边数： 推论任何图无向或有向)中，奇度顶点的个数是偶数， 证由握手定理，所有顶点的度数之和是偶数，而偶度顶点的度 数之和是偶数，故奇度顶点的度数之和也是偶数.所以奇度顶 点的个数必是偶数. 9
9 定理11.1 在任何无向图中, 所有顶点的度数之和等于边数的2倍. 证 G中每条边 (包括环) 均有两个端点，所以在计算G中各顶 点度数之和时，每条边均提供2度，m 条边共提供2m 度. 握手定理 定理11.2 在任何有向图中，所有顶点的度数之和等于边数的2倍; 所有顶点的入度之和等于所有顶点的出度之和, 都等于边数. 推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数. 证 由握手定理, 所有顶点的度数之和是偶数, 而偶度顶点的度 数之和是偶数, 故奇度顶点的度数之和也是偶数. 所以奇度顶 点的个数必是偶数．
离散数学 握手定理应用 例1无向图G有16条边，3个4度顶点，4个3度顶点，其余 均为2度顶点度，问G的阶数n为几？ 解本题的关键是应用握手定理， 设除3度与4度顶点外，还有x个顶点，由握手定理， 16×2=32=3×4+4×3+2x 解得x=4,阶数n=4+4+3=11. 例2在一个部门的25个人中间，由于意见不同，是否可能 每个人恰好与其他5个人意见一致？ 解：不可能。考虑一个图，其中顶点代表人，如果两个 人意见相同，可用边连接，所以每个顶点都是奇数度。 存在奇数个度为奇数的图，这是不可能的。 定理11.3设G为任意n阶无向简单图，则4(G)≤n-1. 10
10 例1 无向图G有16条边，3个4度顶点，4个3度顶点，其余 均为2度顶点度，问G的阶数n为几？ 解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点, 由握手定理, 162=32 = 34+43+2x 解得 x = 4, 阶数 n = 4+4+3=11. 握手定理应用 定理11.3 设G为任意n阶无向简单图，则(G)n−1． 例2 在一个部门的25个人中间，由于意见不同，是否可能 每个人恰好与其他5个人意见一致？ 解：不可能。考虑一个图，其中顶点代表人，如果两个 人意见相同，可用边连接，所以每个顶点都是奇数度。 存在奇数个度为奇数的图，这是不可能的