第14章图的基本概念
12
握手定理应用
补例1 无向图G有16条边，3个4度顶点，4个3度顶点，其 余顶点度数均小于3，问G的阶数n为几？
解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx， 则
若顶点vi不与边ek关联，则称ek与vi的关联次数为0。 8. 设D=<V, E> 为有向图, ek=(vi, vj) E, 称vi, vj为ek的端点，
vi为ek的始点，vj为ek的终点，并称ek与vi（vj）关联。若vi = vj，则称ek为D中的环。 顶点相邻：两个顶点有一条边连接，
边相邻：两条边中一条边的终点是另一条边的起点。
有限图(本书讨论都是有限图) 3. n 阶零图与平凡图
一条边都没有的图，称为零图。 n 阶零图记为Nn, 1阶零 图N1称为平凡图。平凡图只有一个顶点，没有边。 4. 空图——，顶点集为空集。 5.标定图与非标定图 标定图：若给每一个顶点和每一条边指定一个符号 。
第14章图的基本概念
6
相关概念
6. 基图
将有向图的各条有向边改成无向边后所得到的无向图称为 这个图的基图。
7. 设G=<V, E> 为无向图, ek=(vi, vj) E, 称vi, vj为ek的端点， ek与vi（vj）关联。
若vi ≠ vj，则称ek与vi（vj）的关联次数为1，若vi = vj，则称 ek与vi（vj）的关联次数为2，交称为ek环。
孤基本概念
7
相关概念
9. 邻域与关联集 ① vV(G) (G为无向图)
v 的邻 N (v ) 域 { u |u V (G ) (u ,v ) E (G ) u v } v 的闭 N (v ) 邻 N (v ) { v 域 }
v 的关联集 I(v){e|e E (G )e与 v关}联 ② vV(D) (D为有向图)
第五部分 图论
本部分主要内容 图的基本概念 欧拉图、哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色
第14章图的基本概念
1
第十四章 图的基本概念
主要内容 图 通路与回路 图的连通性 图的矩阵表示 图的运算 预备知识 多重集合——元素可以重复出现的集合 无序集——AB={(x,y) | xAyB}
于1条，则称这些边为平行边，平行边的条数称为重数。 (2) 有向图中的平行边及重数（注意方向性） 如果关联一对顶点的有向边多于1条，并且这些边的始点与
终点相同，则称这些边为平行边，平行边的条数称为重数。 (3) 多重图：含平行边的图称为多重图。 (4) 简单图：既不含平行边也不含有环的图。 在定义14.3中定义的简单图是极其重要的概念
第14章图的基本概念
2
预备知识
多重集合——元素可以重复出现的集合
设A,B为任意的两个集合，称 {{x,y} | xAyB}
为A与B的无序积，记作AB.
任意a，b均有(a,b)=(b,a) 无序集——AB={(x,y) | xAyB}
第14章图的基本概念
3
14.1 图
定义14.1 无向图G 是一个有序的二元组，G= <V,E>, 其中 (1) V 为顶点集，元素称为顶点或结点 (2) E为VV 的多重集，其元素称为无向边，简称边
注意：图的数学定义与图形表示，在同构（待叙）的意义下 是一一对应的
第14章图的基本概念
5
相关概念
1. 图 ① 可用G泛指图（无向的或有向的） ② V(G), E(G), V(D), E(D),顶点集与边集，
|V(G)|,|E(G)|, |V(D)|, |E(D)|,顶点数与边数。 2. n阶图----顶点数称为图的阶，
V1={v | vV d(v)为奇数} V2={v | vV d(v)为偶数} 则V1V2=V, V1V2=，由握手定理可知
2 m d(v) d(v) d(v)
v V
v V 1
v V 2
由于2m, d (v) 均为偶数，所以 d (v) 为偶数，但因为V1中
vV2
vV1
顶点度数为奇数，所以|V1|必为偶数.
第14章图的基本概念
9
顶点的度数
定义14.4 (1) 设G=<V,E>为无向图, vV, d(v)——v的度数, 简称度 V作为边的端点的次数之和。 (2) 设D=<V,E>为有向图, vV,
d+(v)——v的出度： V作为边的始点的次数之和。 d(v)——v的入度： V作为边的终点的次数之和。 d(v)——v的度或度数
定理14.2 设D=<V,E>为任意有向图，V={v1,v2,…,vn}, |E|=m, 则
n
n
n
d(vi)2 m , 且d(vi)d(vi) m
i 1
i 1
i 1
本定理的证明类似于定理14.1
第14章图的基本概念
11
握手定理推论
推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数.
证 设G=<V,E>为任意图，令
实例
设 V = {v1, v2, …,v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3),
(v2,v5), (v1,v5), (v4,v5)} 则 G = <V,E>为一无向图
第14章图的基本概念
4
有向图
定义14.2 有向图D=<V,E>, 只需注意E是VV 的多重子集 图2表示的是一个有向图，试写出它的V 和 E
v的后继元 D (v)集 {u|uV(D)v,u E(D)uv} v的先驱元 D (v)集 {u|uV(D)u,v E(D)uv} v的邻域ND(v)D (v)D (v) v的闭邻N 域 D(v)ND(v){v}
第14章图的基本概念
8
多重图与简单图
定义14.3 (1) 无向图中的平行边及重数:如果关联一对顶点的无向边多
(3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点
第14章图的基本概念
10
握手定理
定理14.1 设G=<V,E>为任意无向图， V={v1,v2,…,vn}, |E|=m, 则
n
d(vi ) 2m
i1
证 G中每条边 (包括环) 均有两个端点，所以在计算G中各顶点 度数之和时，每条边均提供2度，m 条边共提供 2m 度.