7
有向图
定义14.2 有向图D=<V,E>, (1) V 为顶点集，元素称为顶点 (2) E为VV 的有穷多重子集，其元素称为有向边，简称边 图2表示的是一个有向图，试写出它的V 和 E
注意：图的数学定义与图形表示，在同构（待叙）的意义下
是一一对应的
8
相关概念
1. 图 ① 可用G泛指图（无向的或有向的） ② V(G), E(G), V(D), E(D) ③ n阶图
11
实例
例1
G1、G2是多重图，G3是线图，G4是简单图。
12
顶点的度数
定义14.4 (1) 设G=<V,E>为无向图, vV, d(v)——v的度数, 简称度 (2) 设D=<V,E>为有向图, vV,
d+(v)——v的入度 d(v)——v的出度 d(v)——v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇度顶点与偶度顶点 (6) 悬挂顶点与悬挂边
2
(2) n (n1)阶有向完全图——每对顶点之间均有两条方向相 反的有向边的有向简单图. 边数为：
m n(n 1), 2(n 1), n 1
(3) n (n1) 阶竞赛图——基图为Kn的有向简单图. 边数为
m n(n 1) , n 1
于该结构，那么这些方法也可以用于新领域的结构。这就
使得理解和处理该对象结构变得容易，并往往可以让数学
家对该领域有更深刻的理解。
25
完全图、竞赛图、 k 正则图
定义14.6
(1) n (n1) 阶无向完全图——每个顶点与其余顶点均相邻的 无向简单图，记作 Kn. 边数为：
m n(n 1) , n 1
第五部分 图论
图论是数学的一个分支,以图为研究对象。图是由若干给 定的点和连接两点的线构成，其中，点代表事物，连接两点 的线表示两个事物之间具有的特定关系。
图论起源于18世纪，追朔到1736年瑞士数学家L.Euler发 表了图论的首篇论文——《哥尼斯堡七桥问题无解》，提出 和解决著名Konigsberg七桥问题。
1
经典的图论问题——七桥问题
瑞士数学家 欧拉（Euler）
2
经典的图论问题——四色问题
3
本部分主要内容
图的基本概念 欧拉图、哈密顿图 树 平面图
图论结构
4
第十四章 图的基本概念
主要内容 图的概念 通路与回路 图的连通性 图的矩阵表示 图的运算 预备知识 多重集合——元素可以重复出现的集合 无序集——AB={(x,y) | xAyB}
图之间的同构关系具有自反性、对称性和传递性. 图同构的必要条件，但它们全不是充分条件：
① 边数相同，顶点数相同; ② 度数列相同; ③ 对应顶点的关联集及邻域的元素个数相同。 若破坏必要条件，则两图必不同构
24
图同构的目的
同构是在数学对象之间定义的一类映射,它能揭示出在这些 对象的属性或者操作之间存在的关系。若两个数学结构之 间存在同构映射，那么这两个结构叫做是同构的。一般来 说，如果忽略掉同构的对象的属性或操作的具体定义，单 从结构上讲，同构的对象是完全等价的。
28
实例
例6 画出K4的所有非同构的生成子图
29
补图
定义14.9 设G=<V,E>为n阶无向简单图，以V为顶点集，以 所有使G成为完全图Kn的添加边组成的集合为边集的图， 称为G的补图，记作G . 若G G , 则称G是自补图. 问1：相对于K4, 求上面图中所有图的补图，并指出哪些是 自补图.（提示：互为自补图的两个图的边数有何关系？） 问2：（n,m）无向简单图G的补图的边数是多少？
2. 有限图即(n,m)图 3. n 阶零图与平凡图 4. 空图—— 5. 用 ek 表示无向边或有向边 6. 顶点与边的关联关系
① 关联、关联次数 ②环 ③ 孤立点 7. 顶点之间的相邻与邻接关系
9
相关概念
8. 邻域与关联集 ① vV(G) (G为无向图)
v的邻域 N (v) {u | uV (G) (u, v) E(G) u v}
v的邻 域
N D (v) D (v) D (v)
v的 闭 邻 域 N D (v) ND (v) {v}
9. 标定图（每个顶点、每条边标注符号）与非标定图
104.3 (1) 无向图中的平行边及重数 (2) 有向图中的平行边及重数（注意方向性） (3) 多重图：含有平行边的图 (4) 简单图：既不含平行边也无环的图 简单图是图论中基础而又极其重要的概念
研究同构的主要目的是为了把数学理论应用于不同的领域。
如果两个结构是同构的，那么其上的对象会有相似的属性
和操作，对某个结构成立的命题在另一个结构上也就成立
。因此，如果在某个数学领域发现了一个对象结构同构于
某个结构，且对于该结构已经证明了很多定理，那么这些
定理马上就可以应用到该领域。如果某些数学方法可以用
21
图同构的实例
例5
G1≌G2；
G3≌G4 (G3和G4称为自补图) ；
G5≌G6 ，G5称为彼得森图；
G7与G8不同构。
22
练习
(1)
(2)
(3)
(4)
(5)
(6)
图(1)与(2) 的度数列不同，它们不同构，(3)与(4)也不同构.
图(5)与(6)的度数列相同，它们同构吗？为什么？
23
图同构的必要条件
19
实例
例4 (1) (3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为什么？ (2) (3,3,3,1)可图化吗？可简图化吗？ (3) (4,4,3,3,2,2)可图化吗？可简图化吗？ 解 (1) 由可图化定理，它们都不能成为图的度数序列。 (2) 可图化，但不可简单图化。 (3) 可简单图化。
20
图的同构
定义14.5 设G1=<V1, E1>, G2=<V2, E2>为两个无向图(两 个有向图)，若存在双射函数f:V1V2, 对于vi,vjV1,
(vi,vj) E1 当且仅当 (f(vi),f(vj)) E2 （< vi,vj > E1 当且仅当 <f(vi),f(vj)> E2 ) 并且, (vi,vj)（< vi,vj >）与 (f(vi),f(vj))（<f(vi),f(vj)>）的重 数相同，则称G1与G2是同构的，记作G1G2.
上图的度数列为（3,3,5,1,0）
18
可图化与可简单图化
对于给定的一个非负整数序列d=(d1,d2,…dn),若存在以 V=(v1,v2,…vn)为顶点集的n阶无向图G,使得d(vi)=di，则称 d是可图化的，若所得的图是简单图，则称d是可简单化的。
定理14.3 d是可图化的当且仅当非负整数序列之和能被2整除。 定理14.4 设G为任意的n阶无向简单图，则Δ(G)≦n-1.
v的闭邻域 N (v) N (v) {v}
v 的关联集 I (v) {e | e E(G) e与v关联} ② vV(D) (D为有向图)
v的 后 继 元 集 D (v) {u | u V ( D) v, u E( D) u v}
v的 先 驱 元 集 D (v) {u | u V ( D) u, v E( D) u v}
d(vi) 2，i =1, 2, …, x， 于是得不等式
32 3*4+4*3+2x 得 x 4, 阶数 n 4+4+3=11.
17
图的度数列
1 . V={v1, v2, …, vn}为无向图G的顶点集，称d(v1), d(v2), …, d(vn)为G的度数列
2. V={v1, v2, …, vn}为有向图D的顶点集， D的度数列：d(v1), d(v2), …, d(vn) D的入度列：d+(v1), d+(v2), …, d+(vn) D的出度列：d(v1), d(v2), …, d(vn)
设e＝(u,v)∈E，用G\e表示从G中删除e，将e的两个端点u,v用 一个新的结点w代替，使w关联除e外的u和v关联的一切边， 称为边e的收缩。一个图G可以收缩为图H，是指H可以从G 经过若干次边的收缩而得到。
2m d(v) d(v) d(v)
vV
vV1
vV2
由于2m, d(v) 均为偶数，所以 d(v) 为偶数，但因为V1中
vV2
vV1
顶点度数为奇数，所以|V1|必为偶数.
16
握手定理的应用
例3 无向图G有16条边，3个4度顶点，4个3度顶点，其余 顶点度数均小于3，问G至少有多少顶点？ 解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx， 则
5
引例
四个班进行第一轮的足球循环赛， 为了表示四个班之间比赛胜负情 况，作出如右图所示的竞赛图。 该图中的4个小圆圈分别表示这四 个班，称之为顶点。如果两个班 进行了一场比赛，则在两个顶点 间用一条带箭头的线连接起来， 称之为边。这样，利用图形使得 各班之间的比赛及胜负情况一目 了然。
6
14.1 图
30
图的操作
定义14.10 设图G＝<V,E>为无向图，
设e∈E，用G-e表示从G中去掉边e得到的图，称为删除边e。 又设EE，用G-E表示从G中删除E中所有边得到的图， 称为删除E。
设v∈V，用G-v表示从G中去掉结点v及v关联的所有边得到的 图，称为删除顶点v。又设VV，用G-V 表示从G中删除 V中所有结点及关联的所有边得到的图，称为删除V。