图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树(Tree)和最小树 破圈法,避圈法求最小生成树: 生成最 小树T 3 3 图G 生成最 2 小树T 16
16 图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树（Tree）和最小树 破圈法，避圈法求最小生成树： 图G 1 5 4 2 4 5 3 1 3 4 4 2 1 5 1 2 生成最 小树T 生成最 小树T 1 2 3 1 2 1 1 2 1 2 3 1 2 1 1 2
图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 根树及其应用 有向树若一个有向图在不考虑边的方向时是一棵树。 出次 入次 根树—有向树T,恰有一个结点入次为0,其余各个点入次均为 叉树—在根树中,若每个顶点的出次小于或等于m,称其为m 叉树。若每个顶点的出次恰好等于m或0,则称其为完 全m叉树。 4叉树 完全3叉树 17
17 图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 根树及其应用 有向树——若一个有向图在不考虑边的方向时是一棵树。 出次—— 入次—— 根树——有向树 T ，恰有一个结点入次为 0 ，其余各个点入次均为 1。 叉树——在根树中，若每个顶点的出次小于或等于 m ，称其为 m 叉树。若每个顶点的出次恰好等于 m 或 0 ，则称其为完 全 m 叉树。 4 叉树 完全3 叉树