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