0 .6 0.4 x 0 .2
图可以用图形表示：V中的元素用平面上一个黑点表示，E
中的元素用一条连接V中相应点对的任意形状的线表示。
例1、设图G＝<V,E>。这里V＝{v1,v2,v3,v4} E＝{e1,e2,e3,e4,e5,e6}，
e1＝(v1,v2)，e2＝(v1,v3)，e3＝(v1,v4)， e4＝(v2,v3)，e5＝(v3,v2)，e6＝(v3,v3)。
2、图论模型
为了抽象和简化现实世界，常建立数学模型。图是关系的 数学表示，为了深刻理解事物之间的联系，图是常用的数学 模型。
(1) 化学中的图论模型
19世纪，化学家凯莱用图论研究简单烃——即碳氢化合物
实用文档
12
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
20世纪30年代出版第一本图论著作.
实用文档
7
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
目前，图论已形成很多分支：如随机图论、 网络图论、代数图论、拓扑图论、极值图论等。
3、应用状况
图论的应用已经涵盖了人类学、计算机科学、 化学、环境保护、非线性物理、心理学、社会学、
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
图论及其应用
任课教师：杨春 数学科学学院
实用文档
1
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
《图论及其应用》
作者: 张先迪、李正良 购买地点：教材科
(2) 商业中的图论模型
商业中，经常用图来对仓库和零售店进行建模
例如：令V={w1,w2,w3,r1,r2,r3,r4,r5}代表3个仓库和5个零售点
E={w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5}代表每个仓库和每 个
[4] 美，Fred Buckley《图论简明教程》，清华大 学出版社，2005 李慧霸 王风芹译
实用文档
3
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
[5] 李尉萱，《图论》，湖南科学技术出版社， 1979
[6] 美，Douglas B.West《图论导引》，机械工业 出版社，2007 李建中，骆吉洲译
[7] 杨洪，《图论常用算法选编》，中国铁道出版 社，1988
[8] 陈树柏，《网络图论及其应用》，科学出版社， 1982
实用文档
4
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
[9] Chris Godsil，Gordon Royle 《Algebraic Graph Theory》，世界图书出版公司北京公司， 2004
简单图：无环无重边的图称为简单图；其余的图称为
复合图；
实用文档
11
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为 该边的两个端点；
顶点u与边e相关联：顶点u是边e的端点；
边e1与边e2相邻接：边e1与边e2有公共端点；
[10] 王朝瑞，《图论》，高等教育出版社，1983
实用文档
5
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
第一章 图的基本概念
本次课主要内容
图的概念与图论模型
(一)、图论课程简介 (二)、图的定义与图论模型 (三)、图的同构
实用文档
6
实用文档
2
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
参考文献
[1] 美，帮迪《图论及其应用》
[2] 美，Gary Chartrand《图论导引》，人民邮电 出版社，2007
[3] Bela Bollobas，《现代图论》，科学出版社， 2001 一个有限的非空集合，称为顶点集合, 其
(元2)素E称是为由顶V中点的或点点组。成用的|V无|表序示对顶构点成数的；集合， 称
为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用|E|表示边数。
实用文档
9
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
(一)、图论课程简介
1、研究对象
图论是研究点与线组成的“图形”问题的一门 科学。属于应用数学分支.
2、发展历史
图论起源于18世纪的1736年，标志事件是“哥 尼斯堡七桥问题.
数学家欧拉被称为“图论之父”.
交通管理、电信以及数学本身等。
4、教学安排
主要介绍图的一些基本概念、基本理论和图论 的典型应用。60学时。
实用文档
8
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
(二)、图的定义与图论模型
1、图的定义
一个图是一个序偶<V,E>，记为G=(V,E),其中：
v1 e1 e2
e3 v3
v4
v2
e4
e6
e5
实用文档
10
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
图的相关概念：
有限图：顶点集和边集都有限的图称为有限图； 平凡图：只有一个顶点的图称为平凡图； 空图：边集为空的图称为空图；
n阶图：顶点数为n的图称为n阶图； (n, m) 图：顶点数为n,边数为m的图称为(n, m) 图； 边的重数：连接两个相同顶点的边的条数称为边的重数； 重数大于1的边称为重边； 环：端点重合为一点的边称为环；
用点抽象分子式中的碳原子和氢原子，用边抽象原子间
的化学键。
通过这样的建模，能很好研究简单烃的同分异构现象.
例如：C4H10的两种同分异构结构图模型为：
h hh h
h hhh h
hhh
hh
h
h h hh
h
实用文档
13
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2