树的有关定义 口定理3.1.1 e=(u,v)是割边当且仅当e不属于G的任何回路 证明: 必要性,设e三(u)是割边,此时若e=(u 路结点和属于同连通支,宋是割边盾 充分性。设e不属于G的任何回路此时着e不是割 边,帅Ge与G的连道数 U和v仍 属子同一连通支敌Q中存在追路F(u) (uv)+e就是G的一个回路矛盾树的有关定义  定理3.1.1 e=(u, v)是割边,当且仅当e不属于G的任何回路. 证明: 必要性。设e=(u, v)是割边, 此时若e=(u, v)属 于G的某个回路, 则G’=G-e中仍存在u到v的道 路, 故结点u和v属于同一连通支, e不是割边.矛盾. 充分性。设e不属于G的任何回路, 此时若e不是割 边, 则G’=G-e与G的连通支数一样. 于是u和v仍 属于同一连通支. 故G’中存在道路P(u,v), P(u,v)+e就是G的一个回路.矛盾