圈和树 ■树的等价定义： ·图G连通且不含圈。 ·图G中任意两个顶点间有且只有一条路。 ●图G不含圈且(G=WG-1。 ●图G连通且(G=v(G-1。 ●图G极小连通，即：G连通，但删除任意一条边均不连通。 ·图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 ■树中的边有什么特征？你能就此给出树的另一种等价定义吗？ 2023/3/13 21
n 树的等价定义： l 图G连通且不含圈。 l 图G中任意两个顶点间有且只有一条路。 l 图G不含圈且ε(G) = ν(G) – 1。 l 图G连通且ε(G) = ν(G) – 1。 l 图G极小连通，即：G连通，但删除任意一条边均不连通。 l 图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 n 树中的边有什么特征？你能就此给出树的另一种等价定义吗？ 2023/3/13 21 圈和树
圈和树 ■树的等价定义： ●图G连通且不含圈。 ·图G中任意两个顶点间有且只有一条路。 ●图G不含圈且(G)=v(G)-1。 ●图G连通且(G)=v(G-1。 ●图G极小连通，即：G连通，但删除任意一条边均不连通。 ●图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 ■树中的边有什么特征？你能就此给出树的另一种等价定义吗？ ●图G连通且每条边都是割边 2023/3/13 22
n 树的等价定义： l 图G连通且不含圈。 l 图G中任意两个顶点间有且只有一条路。 l 图G不含圈且ε(G) = ν(G) – 1。 l 图G连通且ε(G) = ν(G) – 1。 l 图G极小连通，即：G连通，但删除任意一条边均不连通。 l 图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 n 树中的边有什么特征？你能就此给出树的另一种等价定义吗？ l 图G连通且每条边都是割边 2023/3/13 22 圈和树
圈和树 ■树的等价定义： ·图G连通且不含圈。 ·图G中任意两个顶点间有且只有一条路。 ●图G不含圈且(G)=v(G)-1。 ●图G连通且(G)=v(G-1。 ●图G极小连通，即：G连通，但删除任意一条边均不连通。 ·图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 ■树中的边有什么特征？你能就此给出树的另一种等价定义吗？ ●图G连通且每条边都是割边 ■非平凡树的叶顶点数量的上界和下界分别是多少？ 2023/3/13 23
n 树的等价定义： l 图G连通且不含圈。 l 图G中任意两个顶点间有且只有一条路。 l 图G不含圈且ε(G) = ν(G) – 1。 l 图G连通且ε(G) = ν(G) – 1。 l 图G极小连通，即：G连通，但删除任意一条边均不连通。 l 图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 n 树中的边有什么特征？你能就此给出树的另一种等价定义吗？ l 图G连通且每条边都是割边 n 非平凡树的叶顶点数量的上界和下界分别是多少？ 2023/3/13 23 圈和树
圈和树 ■树的等价定义： ●图G连通且不含圈。 ·图G中任意两个顶点间有且只有一条路。 ●图G不含圈且(G)=v(G)-1。 ●图G连通且(G)=v(G-1。 ●图G极小连通，即：G连通，但删除任意一条边均不连通。 ●图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 ■树中的边有什么特征？你能就此给出树的另一种等价定义吗？ ●图G连通且每条边都是割边 ■非平凡树的叶顶点数量的上界和下界分别是多少？ ■生成树：连通图的生成子图，且是树 2023/3/13 24
n 树的等价定义： l 图G连通且不含圈。 l 图G中任意两个顶点间有且只有一条路。 l 图G不含圈且ε(G) = ν(G) – 1。 l 图G连通且ε(G) = ν(G) – 1。 l 图G极小连通，即：G连通，但删除任意一条边均不连通。 l 图G极大无圈，即：G不含圈，但增加任意一条边均形成圈。 n 树中的边有什么特征？你能就此给出树的另一种等价定义吗？ l 图G连通且每条边都是割边 n 非平凡树的叶顶点数量的上界和下界分别是多少？ n 生成树：连通图的生成子图，且是树 2023/3/13 24 圈和树
圈和树 ■如何判定一个图是否为树？ 2023/3/13 25
n 如何判定一个图是否为树？ 2023/3/13 25 圈和树