版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。
哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
图论起源于18世纪。第一篇图论论文是瑞士数学家欧一个图G=
(V
,
E
)
由一些点及点之间的连线(称为边)构成,V、E
分别记G的点集合和边集合。在图的概念中,点的空间位置、边的曲直长短都是无关紧要的,重要的是其有几个点以及哪些点之间有边相连。v1v2v3v4v5v1v2v3v4v5≌一个图G=(V,E)由一些点及点之间的连线(称如果用点表示要研究的对象,则图的边可以用来反映对象之间是否存在某种关系。用点表示人,边表示两个人是否互相认识;在地区公路图中,用点表示城市,边表示城市之间是否有公路直接相连;在分子结构图中,用点表示原子,边表示原子之间是否存在化学键;……如果用点表示要研究的对象,则图的边可以用来反映对象之间是否存哥尼斯堡
七桥问题
ABCDABCD(Euler,1736)右图是否存在经过每条边恰好一次的回路,即是否为
Euler图?是否可以一笔画?哥尼斯堡七桥问化学药品存放问题某单位需要存放一些化学药品,其中某些药品不能放在同一个库房里,问至少需要几个库房?用点表示药品,在不能放在同一个库房的两种药品之间连边。需要几个库房等价于需要用几种颜色给图的点着色可以使得相邻的点有不同的颜色。abcdefg图中的7种药品需要3个库房,例如{a
,b
,e},{c
,d
,g},{f}各放一个库房。化学药品存放问题某单位需要存放一些化学药品,其中某些药品不能排课表问题有m位教师x1,
…,
xm和n个班级y1,
…,
yn,教师xi需要给班级yj
上wij
节课,试编制一张课表使得课时尽量少。构造图
G=(V
,
E
),其中V={
x1,
…,
xm,y1,
…,
yn
}
,点
xi
与
yj
之间连有
wij
条边。给G的边着色,使得相邻的边有不同的颜色。需要3种颜色给边着色y1y2y3x1x2x3x4排课表问题有m位教师x1,…,xm和n个班图的基本概念一个有序二元组(V,E)称为一个图,记G=(V,E),其中①V或V(G)称为G的顶点集,V≠Φ,其元素称为顶点或结点,简称点;②
E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.图的基本概念一个有序二元组(V,E)称为一个图,点v
的度数:与v
相连的边的条数,记作d(v)。与顶点v出关联的边的数目称为出度,记作d
+(v),与顶点v入关联的边的数目称为入度,记作d
-(v)。命题:图的所有点的度数之和等于边数的两倍,即例.碳氢化合物中氢原子的个数为偶数。CHHHHCCHHHHCCCCCCHHHHHH点v的度数:与v相连的边的条数,记作d(v)。命两个图G=
(V
,
E
)和,如果有则称G是G
的子图。若G是G
的子图,且V
=V,则称G是G
的生成子图。G
G'
G''
G'
和G''都是G的生成子图。两个图G=(V,E)和边数
k称为链P
的长度。v1v2v4v3v5v6v7v8称为链,其中当v0
=
vk
时,称P
为闭链。边不重复的链称为迹。点不重复的链称为路,v0=vk
的回路称为圈。图G
的一条点与边的交替序列迹的长度为7闭迹的长度为6圈的长度为4命题:若点v
与v
之间有Walk,则点v
与v
之间必有Path。边数k称为链P的长度。v1v2v4v3v5v6v7v8在图G中,若点u、v之间有路,则称u、v连通。若G的任何两点之间有路,则称G
是连通图。G
的极大连通子图称为连通分支。有三个连通分支若删去某条边e之后图的连通分支数增加,则称e为割边或桥;若删去某个点v及相连的边后连通分支数增加,则称v为割点。euvwe为割边u、v、w
皆为割点在图G中,若点u、v之间有路,则称u、v连通。若简单图:任何一条边连结两个不同的点,任何两个点之间至多有一条边的图。完全图:任何两个点之间都有边相连的简单图。n
个点的完全图记作Kn。
K3K4K5该图非简单图多重边自环简单图:任何一条边连结两个不同的点,任何两个点之间至多有一条二分图:点集
V能划分成两个子集X、Y,使得每条边的两个端点分别属于X
和Y
的图。二分图G
也记作G=(X,Y,E
)。称G=(X,Y,E
)为完全二分图,若
X中的每个点和Y中的每个点之间皆有边相连,记作。K1,3K2,3K3,3命题:图
G是二分图当且仅当G中不存在长度为奇数的圈。二分图:点集V能划分成两个子集X、Y,使得每条边的两在图G
=
(V
,E
)的边集上定义权函数后就得到一个赋权图,记为G=(V
,
E
,
w)
。对于赋权图,路的长度(即路的权)通常指路上所有边的权之和。最短路问题:求赋权图上指定点之间的权最小的路。在图G=(V,E)的边集上定义权函数
邻接矩阵
A=(aij)n×n,例:写出右图的邻接矩阵:解:图的矩阵表示邻接矩阵A=(aij)n×n,例:写出右图的邻权矩阵W=(wij)n×n例:写出右图的权矩阵:解:图的矩阵表示权矩阵W=(wij)n×n例:写出右图的权矩阵:
关联矩阵A=(aij)n×m
有向图:无向图:图的矩阵表示关联矩阵A=(aij)n×m
有向图:无向图:图例:写出右图与其基本图的关联矩阵解:分别为:图的矩阵表示例:写出右图与其基本图解:分别为:图的矩阵表示用图论思想求解以下各题例1、一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东,由于船小,一次只能带一物过河,并且,狼与羊,羊与菜不能独处,给出渡河方法。图论的基本概念用图论思想求解以下各题例1、一摆渡人欲将一只狼,一头羊,一篮解:用四维0-1向量表示(人,狼,羊,菜)的在西岸状态,(在西岸则分量取1,否则取0.)共24=16种状态,由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的,图论的基本概念解:用四维0-1向量表示(人,狼,羊,菜)的在西岸共24=1人在河西:(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)人在河东:以十个向量作为顶点,将可能互相转移的状态连线,则得10个顶点的偶图。问题:如何从状态(1,1,1,1)转移到(0,0,0,0)?方法:从(1,1,1,1)开始,沿关联边到达没有到达的相邻顶点,到(0,0,0,0)终止,得到有向图即是。人在河西:(1,1,1,1)(1,1,1,0)(1,1,0,例2、证明:在任意6人的集会上,总有3人互相认识,或总有3人互相不认识。解:以顶点表示人,以边表示认识,得6个顶点的简单图G。问题:3人互相认识即G包含K3为子图,3人互相不认识即G包含(3,0)图为子图。图论的基本概念例2、证明:在任意6人的集会上,总有3人互相认解:以顶点表示图论的基本概念图论的基本概念
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。
哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
图论起源于18世纪。第一篇图论论文是瑞士数学家欧一个图G=
(V
,
E
)
由一些点及点之间的连线(称为边)构成,V、E
分别记G的点集合和边集合。在图的概念中,点的空间位置、边的曲直长短都是无关紧要的,重要的是其有几个点以及哪些点之间有边相连。v1v2v3v4v5v1v2v3v4v5≌一个图G=(V,E)由一些点及点之间的连线(称如果用点表示要研究的对象,则图的边可以用来反映对象之间是否存在某种关系。用点表示人,边表示两个人是否互相认识;在地区公路图中,用点表示城市,边表示城市之间是否有公路直接相连;在分子结构图中,用点表示原子,边表示原子之间是否存在化学键;……如果用点表示要研究的对象,则图的边可以用来反映对象之间是否存哥尼斯堡
七桥问题
ABCDABCD(Euler,1736)右图是否存在经过每条边恰好一次的回路,即是否为
Euler图?是否可以一笔画?哥尼斯堡七桥问化学药品存放问题某单位需要存放一些化学药品,其中某些药品不能放在同一个库房里,问至少需要几个库房?用点表示药品,在不能放在同一个库房的两种药品之间连边。需要几个库房等价于需要用几种颜色给图的点着色可以使得相邻的点有不同的颜色。abcdefg图中的7种药品需要3个库房,例如{a
,b
,e},{c
,d
,g},{f}各放一个库房。化学药品存放问题某单位需要存放一些化学药品,其中某些药品不能排课表问题有m位教师x1,
…,
xm和n个班级y1,
…,
yn,教师xi需要给班级yj
上wij
节课,试编制一张课表使得课时尽量少。构造图
G=(V
,
E
),其中V={
x1,
…,
xm,y1,
…,
yn
}
,点
xi
与
yj
之间连有
wij
条边。给G的边着色,使得相邻的边有不同的颜色。需要3种颜色给边着色y1y2y3x1x2x3x4排课表问题有m位教师x1,…,xm和n个班图的基本概念一个有序二元组(V,E)称为一个图,记G=(V,E),其中①V或V(G)称为G的顶点集,V≠Φ,其元素称为顶点或结点,简称点;②
E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.图的基本概念一个有序二元组(V,E)称为一个图,点v
的度数:与v
相连的边的条数,记作d(v)。与顶点v出关联的边的数目称为出度,记作d
+(v),与顶点v入关联的边的数目称为入度,记作d
-(v)。命题:图的所有点的度数之和等于边数的两倍,即例.碳氢化合物中氢原子的个数为偶数。CHHHHCCHHHHCCCCCCHHHHHH点v的度数:与v相连的边的条数,记作d(v)。命两个图G=
(V
,
E
)和,如果有则称G是G
的子图。若G是G
的子图,且V
=V,则称G是G
的生成子图。G
G'
G''
G'
和G''都是G的生成子图。两个图G=(V,E)和边数
k称为链P
的长度。v1v2v4v3v5v6v7v8称为链,其中当v0
=
vk
时,称P
为闭链。边不重复的链称为迹。点不重复的链称为路,v0=vk
的回路称为圈。图G
的一条点与边的交替序列迹的长度为7闭迹的长度为6圈的长度为4命题:若点v
与v
之间有Walk,则点v
与v
之间必有Path。边数k称为链P的长度。v1v2v4v3v5v6v7v8在图G中,若点u、v之间有路,则称u、v连通。若G的任何两点之间有路,则称G
是连通图。G
的极大连通子图称为连通分支。有三个连通分支若删去某条边e之后图的连通分支数增加,则称e为割边或桥;若删去某个点v及相连的边后连通分支数增加,则称v为割点。euvwe为割边u、v、w
皆为割点在图G中,若点u、v之间有路,则称u、v连通。若简单图:任何一条边连结两个不同的点,任何两个点之间至多有一条边的图。完全图:任何两个点之间都有边相连的简单图。n
个点的完全图记作Kn。
K3K4K5该图非简单图多重边自环简单图:任何一条边连结两个不同的点,任何两个点之间至多有一条二分图:点集
V能划分成两个子集X、Y,使得每条边的两个端点分别属于X
和Y
的图。二分图G
也记作G=(X,Y,E
)。称G=(X,Y,E
)为完全二分图,若
X中的每个点和Y中的每个点之间皆有边相连,记作。K1,3K2,3K3,3命题:图
G是二分图当且仅当G中不存在长度为奇数的圈。二分图:点集V能划分成两个子集X、Y,使得每条边的两在图G
=
(V
,E
)的边集上定义权函数后就得到一个赋权图,记为G=(V
,
E
,
w)
。对于赋权图,路的长度(即路的权)通常指路上所有边的权之和。最短路问题:求赋权图上指定点之间的权最小的路。在图G=(V,E)的边集上定义权函数
邻接矩阵
A=(aij)n×n,例:写出右图的邻接矩阵:解:图的矩阵表示邻接矩阵A=(aij)n×n,例:写出右图的邻权矩阵W=(wij)n×n例:写出右图的权矩阵:解:图的矩阵表示权矩阵W=(wij)n×n例:写出右图的权矩阵:
关联矩阵A=(aij)n×m
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 车削加工技术 第2版 课件 模块七 车削螺纹 任务一 了解螺纹
- 出版行业数字化转型及内容创新发展方案
- 红星照耀中国读书笔记第九章
- 农业行业智能农业装备研发方案
- 消防控制室管理规定
- 《三角形的内角和》(教学设计)-2023-2024学年四年级下册数学人教版
- 《电场强度与电势差的关系》参考课件
- 《认识多用电表》参考课件
- 七年级英语上册第04讲 可数和不可数名词(解析版)
- 焦亚硫酸钠市场规模预测及发展动向分析报告模板
- JTG F40-2004 公路沥青路面施工技术规范
- (高清版)DZT 0323-2018 硅灰石、透辉石、透闪石、长石矿产地质勘查规范(附修改单)
- 小学生自我介绍竖版
- 新教科版五年级科学上册全册课件(精品PPT)
- 爆板原因分析
- 变压器的设计计算方法
- 英语特色学校工作汇报材料
- OTN单板连纤关系
- 浅析巴松音乐发展史
- 中班健康优秀教案及教学反思《小小营养师》
- 人教版高中英语必修第一册:Unit1Teenage life单元测试(附答案与解析)
评论
0/150
提交评论