G的最大度(G)=max{d(v)| vV} G的最小度(G)=min{d(v)| vV}
例如 d(v5)=3, d(v2)=4, d(v1)=4,
(G)=4, (G)=1,
v4是悬挂顶点, e7是悬挂边, e1是环。
11
设D=<V,E>为有向图, vV, v的出度d(v)：v作为边的始点次数之和 v的入度d+(v)：v作为边的终点次数之和 v的度数(度) d(v)：v作为边的端点次数之和 d(v)= d+(v)+ d-(v)
接于vi .
vi
vj
定义 标定图：顶点或边带标记。
非标定图：顶点或边不带标记。
如
a
c
b
d
7
4、邻域和关联集
设无向图G, vV(G)
v的邻域
v的闭邻域
v的关联集
先
v
后
设有向图D, vV(D) 驱
继
v的后继元集
v的先驱元集
v的邻域
v的闭邻域
8
5、多重图与简单图
定义 (1)平行边： 在无向图中,关联同一对顶点的无向边多于1条. 在有向图中,关联同一对顶点的有向边多于1条， 且这些边的始点和终点相同(同向)。 重数：平行边的条数.
5
3、顶点和边的关联与相邻
定义 设ek=(vi, vj)是无向图G=<V,E>的一条边, 称vi, vj 为ek的端点, ek与vi ( vj)关联. 若vi vj, 则称ek与vi ( vj) 的关联次数为1;若vi = vj, 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不是ek端点, 则称ek与vi 的关联 次数为0. 无边关联的顶点称作孤立点.
定义 设无向图G=<V,E>, vi,vjV, ek,elE, 若(vi,vj) E,
则称vi,vj相邻; 若ek,el至少有一个公共端点, 则称
ek,el相邻. vi
vj
(vi,vj)
ek el
6
对有向图有类似定义. 设ek=vi,vj是有向图的一条
边,又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻
D的最大出度(D), 最小出度(D) 最大入度+(D), 最小入度+(D) 最大度(D), 最小度(D)
例如 d(a)=4, d+(a)=1, d(a)=5, d(b)=0, d+(b)=3, d(b)=3,
(D)=4, (D)=0, +(D)=3, +(D)=1, (D)=5, (D)=3.
12
例 如图，V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}
2
有向图 D=<V,E>, 其中 (1) V同无向图的顶点集, 元素也称为顶点. (2) E是笛卡尔积VV的多重子集， 其元素称为有向边，简称边.
如右图，试写出它的V和E。
注意：图的数学定义与图形表示，在同构的意义 下是一一对应的。
3
一般地，用小圆圈（或实心点）表示顶点，用 顶点间的连线表示无向边，用有方向的连线表示 有向边。如
u
vu
v
(u, v)
(起点) <u, v> (终点)
例1 设D=<V, E>，V={a, b, c, d, e}，E={<a, a>, <a, b>, <a, b>, <b, a>, <b, c>, <c, d>, <d, b>}，画图。42、几个特殊的图
通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用ek表示无向边或有向边. V(G), E(G) —表示图G的顶点集, 边集. |V(G)|, |E(G)| —表示图G的顶点数集（阶）和边数. n 阶图：n个顶点的图 有限图：V, E都是有穷集合的图 零图：E= 平凡图：1 阶零图 空图：V= 基图：用无向边代替D的所有有向边所得到的无向 图称作D的基图。
14
8、图的度数列
(1) 设无向图G的顶点集V={v1, …, vn} G的度数列: d(v1), d(v2), …, d(vn) 如右图度数列:4,4,2,1,3
(2) 设有向图D的顶点集V={v1, v2, …, vn} D的度数列: d(v1), d(v2), …, d(vn) D的出度列: d(v1), …, d(vn) D的入度列: d+(v1), …, d+(vn)
2·x=2×16 ∴ x=16 (2) 21条边, 3个4度的顶点, 其余顶点的度数均为3。 解：设顶点数为x，由握手定理，有
4×3+3×(x-3)=2×21 ∴ x=13 (3) 24条边，每个顶点的度数均相同。 解：设顶点数为x，顶点的度数为y，则x·y= 2×24
∴整数解(x, y)有：(2, 24), (24, 2), (3, 16), (16, 3), (4, 12), (12, 4), (6, 8), (8, 6) 8种。
第十四章 图的基本概念
14.1 图
无向图与有向图 几个特殊的图 顶点和边的关联与相邻 邻域和关联集 简单图与多重图 顶点的度数
握手定理 图的度数列 图的同构 完全图与正则图 子图 补图
1
1、无向图与有向图
多重集合：元素可以重复出现的集合。 无序积：AB={(x,y) | xAyB} 。 无向图 G =<V,E>, 其中 (1) V为顶点集，元素称为顶点. (2) E为VV的多重子集，其元素 称为无向边，简称边.
(2) 简单图：既无平行边也无环的图. (3) 多重图：含平行边的图.
注意：简单图是极其重要的概念
9
例2
e5和e6 是平行边 重数为2
不是简单图
e2和e3 是平行边,重数为2 e6和e7 不是平行边 不是简单图
10
6、顶点的度数
设G=<V, E>为无向图, vV, v的度数(度) d(v)：v作为边的端点次数之和 悬挂顶点：度数为1的顶点 悬挂边：与悬挂顶点关联的边
7、图论的基本定理—握手定理
定理 任意无向图和有向图的所有顶点度数之和都 等于边数的2倍, 并且有向图的所有顶点入度之 和等于出度之和等于边数.
d(v) 2m d(v) d(v) m
推论 在任何无向图和有向图中，奇度顶点的个数 必为偶数.
13
例3 下列各图中各有多少个顶点？ (1) 16条边，每个顶点的度数均为2。 解：设顶点数为x，由握手定理，有