CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第六章图与网路分析 图是最直观的模型
©管理与人文学院 忻展红 1999，4 第六章 图与网路分析 图是最直观的模型
图论 Graph Theory 哥尼斯堡七桥问题( Konigsberg bridge problem) Leonhard euler(1707-1783)在1736年发表第一篇图论 方面的论文,奠基了图论中的一些基本定理 很多问题都可以用点和线来表示,一般点表示实体 线表示实体间的关联 A
2 B A C D 图论 Graph Theory • 哥尼斯堡七桥问题 (Königsberg Bridge Problem) • Leonhard Euler (1707-1783) 在1736年发表第一篇图论 方面的论文，奠基了图论中的一些基本定理 • 很多问题都可以用点和线来表示，一般点表示实体， 线表示实体间的关联 A B C D
6图与网路的基本概念 611图与网路 网路( Network) 节点( ertex) 边上具有表示连接强度 物理实体、事物、概念 的权值,如w 一般用v表示 又称加权图( Weighted 边(Ege) graph 节点间的连线,表示有 关联 一般用e;表示 图( Graph) 12 节点和边的集合 一般用G(V,E)表示 点集v{v1,2y,wn} 边集E={en} 图61
3 6.1 图与网路的基本概念 6.1.1 图与网路 • 节点 (Vertex) – 物理实体、事物、概念 – 一般用 vi 表示 • 边 (Edge) – 节点间的连线，表示有 关联 – 一般用 eij 表示 • 图 (Graph) – 节点和边的集合 – 一般用 G(V,E) 表示 – 点集 V={v1 ,v2 ,…, vn } – 边集E={eij } v 1 v 5 v 4 v 3 v 2 e 12 e 34 e13 e 24 e22 e'13 e 45 图 6.1 网路 (Network) 边上具有表示连接强度 的权值，如 wij 又称加权图(Weighted graph)
612无向图与有向图 所有边都没有方向的图称为无向图,如图61 在无向图中e1="n,或(v以=(v 当所有边都有方向时,称为有向图,用G(V,4)表示 在有向图中,有向边又称为弧,用a表示,i的顺序 是不能颠倒的,图中弧的方向用箭头标识 图中既有边又有弧,称为混合图
4 6.1.2 无向图与有向图 • 所有边都没有方向的图称为无向图，如图6.1 • 在无向图中 eij=eji，或 (vi , vj )=(vj , vi ) • 当所有边都有方向时，称为有向图，用G(V,A)表示 • 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序 是不能颠倒的，图中弧的方向用箭头标识 • 图中既有边又有弧，称为混合图
6.13端点,关联边,相邻,次 图中可以只有点,而没有边;而有边必有点 若节点v"之间有一条边,则称v是en的端点 ( end vertex),而t是节点v,v的关联边( incident edge) 同一条边的两个端点称为相邻 adjacent)节点,具有共同 端点的边称为相邻边 条边的两个端点相同,称为自环(se!lop);具有两个 共同端点的两条边称为平行边( parallel edges) 既没有自环也没有平行边的图称为简单图( simple graph) 在无向图中,与节点相关联边的数目,称为该节点的 次"( degree),记为d;次数为奇数的点称为奇点 (od)次数为偶数的点称为偶点(even);图中都是偶点的 图称为偶图( even graph)
6.1.3 端点，关联边，相邻，次 • 图中可以只有点，而没有边；而有边必有点 • 若节点vi , vj 之间有一条边 eij，则称 vi , vj 是 eij 的端点 (end vertex)，而 eij 是节点 vi , vj 的关联边(incident edge) • 同一条边的两个端点称为相邻(adjacent)节点，具有共同 端点的边称为相邻边 • 一条边的两个端点相同，称为自环(self-loop)；具有两个 共同端点的两条边称为平行边(parallel edges) • 既没有自环也没有平行边的图称为简单图(simple graph) • 在无向图中，与节点相关联边的数目，称为该节点的 “次”(degree)，记为 d ；次数为奇数的点称为奇点 (odd),次数为偶数的点称为偶点(even)；图中都是偶点的 图称为偶图(even graph)
6.13端点,关联边,相邻,次 有向图中,由节点向外指的弧的数目称为正次数,记为 dr,指向该节点的弧的数目称为负次数,记为d 次数为0的点称为孤立点( Isolated vertex),次数为1的 点称为悬挂点( pendant vertex) 定理1:图中奇点的个数总是偶数个 6.1.4链,圈,路径,回路,欧拉回路 相邻节点的序列{v1,v2,vn}构成一条链(link),又称 为行走(wk);首尾相连的链称为圈(op),或闭行走 在无向图中,节点不重复出现的链称为路径(pth);在 有向图中,节点不重复出现且链中所有弧的方向一致, 则称为有向路径( directed path) 首尾相连的路径称为回路( circuit);
6 6.1.3 端点，关联边，相邻，次 • 有向图中，由节点向外指的弧的数目称为正次数，记为 d +，指向该节点的弧的数目称为负次数，记为 d – • 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的 点称为悬挂点(pendant vertex) 定理 1：图中奇点的个数总是偶数个 6.1.4 链，圈，路径，回路，欧拉回路 • 相邻节点的序列 {v1 ,v2 ,…, vn } 构成一条链(link)，又称 为行走(walk)；首尾相连的链称为圈(loop)，或闭行走 • 在无向图中，节点不重复出现的链称为路径(path)；在 有向图中，节点不重复出现且链中所有弧的方向一致， 则称为有向路径(directed path) • 首尾相连的路径称为回路(circuit)；
走过图中所有边且每条边仅走一次的闭行走称为欧拉 回路 定理2:偶图一定存在欧拉回路(一笔画定理) 61.5连通图,子图,成分 设有两个图G1(V1,E1),G2(V2E2),若V2cV,E2E1, 则G2是G1的子图 无向图中,若任意两点间至少存在一条路径,则称为 连通图 connected graph),否则为非连通图( discon nected graph);非连通图中的每个连通子图称为成分 (component) 链,圈,路径简称路),回路都是原图的子图 平面图 planar graph),若在平面上可以画出该图而没 有任何边相交
7 • 走过图中所有边且每条边仅走一次的闭行走称为欧拉 回路 定理 2：偶图一定存在欧拉回路(一笔画定理) 6.1.5 连通图，子图，成分 • 设有两个图 G1 (V1 , E1 ), G2 (V2 , E2 ), 若V2 V1 , E2 E1， 则 G2 是 G1 的子图 • 无向图中，若任意两点间至少存在一条路径，则称为 连通图(connected graph)，否则为非连通图( disconnected graph)；非连通图中的每个连通子图称为成分 (component) • 链，圈，路径(简称路)，回路都是原图的子图 • 平面图(planar graph)，若在平面上可以画出该图而没 有任何边相交
62树图与最小生成树 一般研究无向图 树图:倒置的树,根(r00n在上,树叶(leug在下 多级辐射制的电信网络、管理的指标体系、家谱、分 类学、组织结构等都是典型的树图 CQ根 C2 8 C3 C4 d叶
8 6.2 树图与最小生成树 • 一般研究无向图 • 树图：倒置的树，根(root)在上，树叶(leaf)在下 • 多级辐射制的电信网络、管理的指标体系、家谱、分 类学、组织结构等都是典型的树图 C1 C2 C3 C4 根 叶
621树的定义及其性质 任两点之间有且只有一条路径的图称为树(re),记为T 树的性质 最少边的连通子图,树中必不存在回略 任何树必存在次数为1的点 具有n个节点的树T的边恰好为n-1条,反之,任何有 n个节点,n-1条边的连通图必是一棵树 622图的生成树 树T是连通图G的生成树( spanning tree),若T是G的 子图且包含图G的所有的节点;包含图G中部分指定节 点的树称为 steiner tree 每个节点有唯一标号的图称为标记图,标记图的生成树 称为标记树( Labeled tree) Caylay定理:n(≥2)个节点,有m-2个不同的标记树
9 6.2.1 树的定义及其性质 • 任两点之间有且只有一条路径的图称为树(tree)，记为T 树的性质： • 最少边的连通子图，树中必不存在回路 • 任何树必存在次数为 1 的点 • 具有 n 个节点的树 T 的边恰好为 n−1 条，反之，任何有 n 个节点， n−1 条边的连通图必是一棵树 6.2.2 图的生成树 • 树 T 是连通图 G 的生成树(spanning tree)，若 T 是 G的 子图且包含图 G 的所有的节点；包含图 G 中部分指定节 点的树称为 steiner tree • 每个节点有唯一标号的图称为标记图，标记图的生成树 称为标记树(labeled tree) Caylay 定理：n (2)个节点，有n n−2个不同的标记树
622图的生成树 ④④ ④④ ③①⑧①⑧①③① ·如何找到一棵生成树 深探法( depth first search):任选一点标记为0点开始搜 索,选一条未标记的边走到下一点,该点标记为1,将 走过的边标记;假设已标记到i点,总是从最新标记的 点向下搜索,若从i点无法向下标记,即与i点相关联 的边都已标记或相邻节点都已标记,则退回到i-1点继 续搜索,直到所有点都被标记 广探法( breadth first search):是一种有层级结构的搜索, 一般得到的是树形图
10 6.2.2 图的生成树 • 如何找到一棵生成树 – 深探法(depth first search)：任选一点标记为 0 点开始搜 索，选一条未标记的边走到下一点，该点标记为 1，将 走过的边标记；假设已标记到 i 点，总是从最新标记的 点向下搜索，若从 i 点无法向下标记，即与 i 点相关联 的边都已标记或相邻节点都已标记，则退回到 i −1 点继 续搜索，直到所有点都被标记 – 广探法(breadth first search)：是一种有层级结构的搜索， 一般得到的是树形图 A C B D A C B D A C B D A D C B