资源描述：
《图论与网络分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论与网络分析（GraphTheoryandNetworkAnalysis）教学要求：了解图论的基本概念，理论和方法以及应用掌握最小树以及最短路问题等模型及其基本算法。掌握欧拉道路、回路的判断和构造方法18世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？陆地A陆地B岛D岛CA·D··B·C1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。图论起源第一节图论的概念图论的图与一般几何图形或函数图形是
2、完全不同的图论中的图:由一些点和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系v1v2v3··v4v1v2v3v434512无向图的基本概念G=(V,E)V={vi}——G的顶点集合E={ek}——G的边集合，且ek=（vi,vj）为无序二元组,表示ek连接vi,vjn(G)=
3、V
4、=n——G的顶点数m(G)=
5、E
6、=m——G的边数顶点相邻两顶点之间有一条边，顶点为该边的端点，边与其端点关联。边相邻e1e2e3e4e5e6e7两边与同一顶点关联，即两边有共同的端点。环两端点重合为一点的边，如e1多重边两点之间
7、多于一条边，如e6，e7简单图不含环和多重边的图，去掉e1和e7.（不特指都是简单图）完全图每对顶点之间都有边相连的无向简单图，n个顶点的无向完全图记为Kn次与顶点v相关联的边数，即以v为顶点的边数记为d(v),环记2次。d(1)=4.奇点，偶点次为奇数的点为奇点，次为偶数的点为偶点。次为1的点为悬挂点。若4，5之间有一条边，则5为悬挂点。孤立点次为0的点为孤立点，5为孤立点。Kn有边条悬挂点无向图的基本概念二部图：图G=(V,E)，顶点集合V可分为两个非空子集X,Y，知X∪Y=V，X∩Y=Φ，E中每条边的两个端点，一个在X中，一个在Y中，则称G为二部图，记为G=
8、（X,Y,E）v1v2v3··v4v2v4v3v1有向图的基本概念G=(V,E)V={vi}：G的顶点集合E={ek}：G的有向边(弧)集合，且ek=（vi,vj）为有序二元组,表示弧ek从vi（始点）指向vj（终点）环有向图中，始点、终点重合的弧为环，如e1多重边始点和终点都相同的弧为多重边，如e6，e7非多重边。简单有向图不含环和多重边的有向图，去掉e1有向完全图以任意点为始点，另一点为终点都有一条弧的简单有向图，n个顶点的有向完全图有弧n(n-1)条出次，入次，次34512e1e2e3e4e5e6e7以顶点v为始点的弧数为v的出次，记为；以顶点v为终点的弧数
9、为v的入次，记为；顶点v的出次与入次之和为点v的次。网络（赋权图）在无向图的边（或有向图的弧）上标上实数，称为该边（或弧）的权，无向（有向）图连同它边上的权称为一个网络赋权图，简称网络。（无向网络，有向网络）子图34512e1e2e3e4e5e6e7412e2e3e4e53412e2e3e4e5道路，回路34512e1e2e3e4e5e6e734512e1e2e3e4e5e6e7连通图点i和j点是连通的：i,j之间存在一条链G是连通的：G中任意两点都是连通的不连通图可以分为若干连通子图，每个称为原图的分图。关联矩阵图的矩阵表示关联矩阵示例右图的关联矩阵是右图的关联
10、矩阵是134521342e1e2e4e7e6e5e8e3e1e2e3e4e5邻接矩阵邻接矩阵示例右图的邻接矩阵是右图的邻接矩阵是134521342主要结论图论基本概念应用例1：证明在9座工厂之间，不可能每座工厂只与其他3座工厂有业务联系，也不可能只有4座工厂与偶数个工厂有业务联系。将9座工厂看做9个点，他们有联系用边相连，若每座工厂只与其他3座工厂有业务联系，则每个点的次都为3，从而总次为27，非偶数，与总次为边的2倍矛盾。从而得证。若只有4座工厂与偶数个工厂有业务联系，则其余5座与奇数个工厂有业务联系，从而总次为4*偶+5*奇=奇数非偶数，矛盾。从而得证。例2：
11、6个人围成圆圈就座，每个人恰好只与相邻者不认识，是否可以重新就座，使每个人都与邻座认识？将6个人看做6个点，相互认识用边表示162345要求重排之后每个人与邻座认识只需找到一个序列，该序列中前后两个点是相邻的就可以了。如1->3->5->2->6->4->1143526例3甲、乙、丙、丁、戊5个运动员报名参加A,B,C,D,E，F六个项目比赛，报名情况见下表（打*表示各运动员报名参加的比赛项目）。问如何安排项目，使每名运动员不连续参加两项比赛？将6个项目看做6个点，同一个人参加的项目之间有边要求安排项目，每名运动员不连续参加两项比赛，只需找到一个遍历点的序列，该序
12、列中前后两
