资源描述：
《第3章-图论与网络模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章图论与网络模型青岛理工大学通信与电子工程学院第一节图论的基本概念第二节最短路问题及其算法第三节树及最小生成树第四节中国邮路问题第五节旅行推销商问题第六节图的着色问题1)图的概念定义一个图G是指一个二元组(V,E)，其中:其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.定义图G的阶是指图的顶点数
2、V(G)
3、;用v表示；图的边的数目
4、E(G)
5、用来表示.也用来表示边是非空有限集，称为顶点集，1)2)E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记用定义若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有
6、图都称为非平凡图.定义若图G中的边均为有序偶对,称G为有向图边为无向边，称e连接和，顶点和称称边为有向边或弧,称是从连接，称为e的尾，称为e的头.若图G中的边均为无序偶对，称G为无向图.称为e的端点.既有无向边又有有向边的图称为混合图.常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，端点不相同的边称为连杆.4)若一对顶点之间有两条以上的边联结，则这些边称为重边．5)既没有环也没有重边的图，称为简单图．6)任意两顶点都相邻的简单图,称为完全图.记为Kv.7)若，，且
7、X中任意两顶点不相邻，Y中任意两顶点不相邻，则称为二分图或偶图；若X中每一顶点皆与Y中一切顶点相邻,称为完全二部图或完全偶图,记为(m=
8、X
9、,n=
10、Y
11、)．8)图叫做星.二分图常用术语2)赋权图与子图定义若图的每一条边e都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图.定义设和是两个图.1)若,称是的一个子图,记2)若，则称是的生成子图.3)若，且，以为顶点集，为的由导出的子图，记为.4)若，且，以为边集，以的端点集为顶点集的图的子图，称为的由导出的子图，记为.包含在之间的所有中的所有边，称3)图的矩阵表示邻接矩阵:1)对无向图，其邻接矩阵，其
12、中：(以下均假设图为简单图).2)对有向图,其邻接矩阵,其中：其中：3)对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义.关联矩阵1)对无向图，其关联矩阵,其中：2)对有向图，其关联矩阵,其中：4)图的顶点度定义1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.5)路和连通定义1)无向图G的一条途径（或通道或链）是指一个有限非空序列，它的项交替地为顶点和边，使得对，的端点是和,称W是从到的一条途径，或一条途径.整数k称为W的长.顶点和分别称为的起点和终点,而称
13、为W的内部顶点.2)若途径W的边互不相同但顶点可重复，则称W为迹或简单链.3)若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路记为定义1)途径中由相继项构成子序列称为途径W的节.2)起点与终点重合的途径称为闭途径.3)起点与终点重合的的路称为圈(或回路)，长为k的圈称为k阶圈，记为Ck.4)若在图G中存在(u,v)路，则称顶点u和v在图G中连通.5)若在图G中顶点u和v是连通的，则顶点u和v之之间的距离d(u,v)是指图G中最短(u,v)路的长；若没没有路连接u和v，则定义为无穷大.6)图G中任意两点皆连通的图称为连通图．7)对于有向图G，
14、若，且有类似地，可定义有向迹，有向路和有向圈.头和尾，则称W为有向途径.例在右图中：途径或链：迹或简单链：路或路径：圈或回路：调课通知下周一（3月28）的课（5,6节），由于出差顺延，望周知；3．最短路径问题及算法最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.最短路问题的两种方法：Dijkstra和Floyd算法.1)求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.最短路的定义：在一个赋权图中，求权的总和最小的路径，即：2)在赋权图G中，从顶点u到顶点v的具有最
15、小权定义1)若H是赋权图G的一个子图，则称H的各边的权和为H的权.类似地，若称为路P的权．若P(u,v)是赋权图G中从u到v的路,称的路P*(u,v)，称为u到v的最短路．3)把赋权图G中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作d(u,v).1)赋权图中从给定点到其余顶点的最短路假设G为赋权有向图或无向图，G边上的权均非负．若，则规定最短路是一条路，且最短路的任一节也是最短路．求下面赋权图中顶点u0到其余顶点的最短路．23Dijkstra算法:基本思想设置一个集合U，存放已求出最短路径的顶点，V-U是尚未确定最短路径的
