2.回路、树、割集 (1)回路(L00p) L是连通图的一个子图，构成一条闭合路径，并满 足：a.连通；b.每个结点关联2条支路。 8 8 回路 不是 回路 一个图的回路数很多，如何确定它的一组独立回路 有时并不容易。借助于“树”的概念可以方便地确定 一个图的独立回路组
(2)树 树：包含图G的全部结点，但不包含任何回路的连 通子图。 即树T是连通图的一个子图且满足： a.连通 b.包含所有结点 c.不含闭合路径 是树 不是树
个连通图可以有多个树。不同的树有不同的树支，也 有不同的连支。但这些树的树支数是相同的。 5,6,7,8 5 5 为树支，相 应的连支为 8 6 8 6 1,2,3,4。 ⑤ 3 ⑤ ③ 3 5 1,3,5,6 为树支，相 应的连支为 3 2,4,7,8。 4 18
例：下列图G是不是树？ ② ② 5 均不是树的子图 8 8 6 ⑤ ⑤ ③ 3 未包含所有结点 ④ 5 5 8 6 8 ⑤ ① ⑤ ③ ④ 含闭合路径 不连通 19