运筹学第次精品文稿.ppt
运筹学第次第1页，本讲稿共11页BACDn哥尼斯堡七桥问题n哈密尔顿回路nLeonhard Euler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理n很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联第2页，本讲稿共11页26.1 图与网路的基本概念1图与网路图与网路n节点节点(Vertex)物理实体、事物、概念物理实体、事物、概念一般一般用用 vi 表示表示n边边(Edge)节点间的连线，表示有关系节点间的连线，表示有关系一般一般用用 eij 表示表示n图图(Graph)节点和边的集合节点和边的集合一般用一般用 G(V,E)表示表示点集点集 V=v1,v2,vn边集边集E=eij 网路网路 (Network)边上具有表示连接强度的权值，边上具有表示连接强度的权值，如如 wij又称又称加权图加权图(Weighted graph)v1v5v4v3v2e12e34e13e24e22e13e45图图 6.1第3页，本讲稿共11页3 6.1.2 无向图与有向图n边都没有方向的图称为无向图边都没有方向的图称为无向图n在无向图中在无向图中 eij=eji，或，或(vi,vj)=(vj,vi)n当边都有方向时，称为有向图，用当边都有方向时，称为有向图，用G(V,A)表示表示n在有向图中，有向边又称为在有向图中，有向边又称为弧弧，用，用 aij表示，表示，i,j 的顺序是不能的顺序是不能颠倒的，图中弧的方向用箭头标识颠倒的，图中弧的方向用箭头标识n图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图第4页，本讲稿共11页4 6.1.3 端点，关联边，相邻，次n图中可以只有点，而没有边；而有边必有点图中可以只有点，而没有边；而有边必有点n若节点若节点vi,vj 之间有一条边之间有一条边 eij，则称，则称 vi,vj 是是 eij 的的端点端点(end vertex)，而而 eij 是节点是节点 vi,vj 的的关联边关联边(incident edge)n同一条边的两个端点称为同一条边的两个端点称为相邻相邻(adjacent)节点节点，具有共同端点的边称，具有共同端点的边称为为相邻边相邻边n一条边的两个端点相同，称为一条边的两个端点相同，称为环环；具有两个共同端点的两条边称为；具有两个共同端点的两条边称为多重多重边边n既没有自环也没有平行边的图称为既没有自环也没有平行边的图称为简单图简单图(simple graph)n在无向图中，与节点相关联边的数目，称为该节点的在无向图中，与节点相关联边的数目，称为该节点的“次次”(degree)，记为记为 d；次数为奇数的点称为；次数为奇数的点称为奇点奇点(odd),次数为偶数的点称为次数为偶数的点称为偶点偶点(even)；图中都是偶点的图称为偶图；图中都是偶点的图称为偶图(even graph)第5页，本讲稿共11页5 6.1.3 端点，关联边，相邻，次n有向图中，由节点指向外的弧的数目称为正次数，记为有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向，指向该节点的弧的数目称为负次数，记为该节点的弧的数目称为负次数，记为 dn次数为次数为 0 的点称为的点称为孤立点孤立点(isolated vertex)，次数为，次数为 1 的点称为的点称为悬挂点悬挂点(pendant vertex)定理定理 1：图中奇点的个数总是偶数个：图中奇点的个数总是偶数个 6.1.4 链，圈，路径，回路，欧拉回路链，圈，路径，回路，欧拉回路n相邻节点的序列相邻节点的序列 v1 ,v2 ,vn 构成一条构成一条链链(link)；首尾相；首尾相连的链称为连的链称为圈圈(loop)，在无向图中，节点不重复出现的链称为，在无向图中，节点不重复出现的链称为路径路径(path)；在有向图中，节点不重复出现且链中所有弧的；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有方向一致，则称为有向路径向路径(directed path)n首尾相连的路径称为首尾相连的路径称为回路回路(circuit)；第6页，本讲稿共11页6 6.1.4 链，圈，路径，回路，连通图n走过图中所有边且每条边仅走一次的圈称为走过图中所有边且每条边仅走一次的圈称为欧拉回路欧拉回路定理定理 2：偶图一定存在欧拉回路：偶图一定存在欧拉回路(一笔画定理一笔画定理)6.1.4 连通图，子图，成分连通图，子图，成分n设有两个图设有两个图 G1(V1,E1),G2(V2,E2),若若V2 V1,E2 E1，则则 G2 是是 G1 的的子图子图n无向图中，若任意两点间至少存在一条路径，则称为无向图中，若任意两点间至少存在一条路径，则称为连连通图通图，否则为，否则为非连通图非连通图；非连通图中的每个；非连通图中的每个连通子图连通子图称为称为成分成分n一个简单图中若任意两点之间均有边相连，称为一个简单图中若任意两点之间均有边相连，称为完全图完全图。n链，圈，路径链，圈，路径(简称路简称路)，回路都是原图的子图，回路都是原图的子图n平面图平面图，若在平面上可以画出该图而没有任何边相交，若在平面上可以画出该图而没有任何边相交第7页，本讲稿共11页76.2 树图与最小生成树n一般研究无向图一般研究无向图n树图：倒置的树，树图：倒置的树，根根(root)在上，在上，树叶树叶(leaf)在下在下n多级辐射制的电信网络、管理的指标体系、家谱、多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图分类学、组织结构等都是典型的树图第8页，本讲稿共11页8 6.2.1 树的定义及其性质n任两点之间有且只有一条路径的图称为任两点之间有且只有一条路径的图称为树树(tree)，记为，记为T 树的性质树的性质：n任何树必存在次数为任何树必存在次数为 1 的点的点n具有具有 n 个节点的树个节点的树 T 的边恰好为的边恰好为 n 1 条，反之，任何有条，反之，任何有n 个节个节点，点，n 1 条边的连通图必是一棵树条边的连通图必是一棵树 6.2.2 图的生成树图的生成树n树树 T 是连通图是连通图 G 的的生成树生成树，若，若 T 是是 G的子图且包含图的子图且包含图 G 的所的所有的节点；包含图有的节点；包含图 G 中部分指定节点的树称为中部分指定节点的树称为 部分树；部分树；n每个节点有唯一标号的图称为标记图，标记图的生成树称每个节点有唯一标号的图称为标记图，标记图的生成树称为为标记树；标记树；定理定理：n(2)个节点，有个节点，有nn 2个不同的个不同的标记树标记树第9页，本讲稿共11页9 6.2.2 图的生成树n如何找到一棵生成树深探法深探法(depth first search)：任选一点标记为：任选一点标记为 0 点开始搜点开始搜索，选一条未标记的边走到下一点，该点标记为索，选一条未标记的边走到下一点，该点标记为 1，将走，将走过的边标记；假设已标记到过的边标记；假设已标记到 i 点，总是从最新标记的点向点，总是从最新标记的点向下搜索，若从下搜索，若从 i 点无法向下标记，即与点无法向下标记，即与 i 点相关联的边都点相关联的边都已标记或相邻节点都已标记，则退回到已标记或相邻节点都已标记，则退回到 i 1 点继续搜索，点继续搜索，直到所有点都被标记直到所有点都被标记广探法广探法(breadth first search)：是一种有层级结构的搜索，：是一种有层级结构的搜索，一般得到的是树形图一般得到的是树形图ACDBACDBACDBADCB第10页，本讲稿共11页10 6.2.3 最小生成树n有有n 个乡村，各村间道路的长度是已知的，如何敷设光缆线路使个乡村，各村间道路的长度是已知的，如何敷设光缆线路使 n 个乡村连通且总长度最短个乡村连通且总长度最短n显然，这要求在已知边长度的网路图中找最小生成树显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法最小生成树的算法：n避圈避圈 算法：将图中所有边按权值从小到大排列，依次选所剩最小的算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集边加入边集 T，只要不和前面加入的边构成回路，直到只要不和前面加入的边构成回路，直到 T 中中有有 n 1 条边，则条边，则 T 是最小生成树是最小生成树n避圈避圈算法基于下述定理算法基于下述定理定理定理 3 指定图中任一点指定图中任一点vi，如果，如果 vj 是距是距 vi 最近的相邻节点，则关最近的相邻节点，则关联边联边 eij 必在某个最小生成树中。必在某个最小生成树中。推论推论 将网路中的节点划分为两个不相交的集合将网路中的节点划分为两个不相交的集合V1和和V2，V2=V V1，则，则V1和和V2间权值最小的边必定在某个最小生成树中间权值最小的边必定在某个最小生成树中。第11页，本讲稿共11页11
