连通圈 从图的某一结点出发,沿 着一些支路连续移动,从 而到达另一指定的节点 85 (或回到原出发点), 这样的一系列支路构成了图G的一条 条支路本身也是一条路径。 图G的任意两个 结点之间至少存在 条路径时,G就 称为连通图。 连通图 非连通图 2021年2月10日星期
2021年2月10日星期 三 11 1. 连通图 ▪ 当图G的任意两个 结点之间至少存在 一条路径时，G就 称为连通图。 ① 1 2 4 3 5 6 7 8 ② ③ ④ ⑤ 从图的某一结点出发，沿 着一些支路连续移动，从 而到达另一指定的节点 (或回到原出发点)， 这样的一系列支路构成了图G的一条 路径。一条支路本身也是一条路径。 连通图 非连通图
若一条路径的起点和终点重(1,2,6.8) 合,且经过的其它结点都相 异,则这条闭合路径就构成① 了图G的一个回路。 158)(2,5,6),(1,2,3,4),/(3.4.8.6 共有13个不同的回路,但独 立回路数远小于13个。 由任意2个可得第3个。 ③不包含回路 2.树(ree)的定义 构成树的各支路叫 个连通图G的树丁 ,如5,6,7,8。 ①包含G的全部结点 其余支路叫 ②本身是连通的 如1,2,3,4。 2021年2月10日星期 12
2021年2月10日星期 三 12 若一条路径的起点和终点重 合，且经过的其它结点都相 异，则这条闭合路径就构成 了图G的一个回路。 ▪ 共有13个不同的回路，但独 立回路数远小于13个。 2. 树 (Tree)的定义 一个连通图G的树T， ①包含G的全部结点； ②本身是连通的； ① 1 2 4 3 5 6 7 8 ② ③ ④ ⑤ (1,5,8)，(2,5,6)，(1,2,3,4)， 构成树的各支路叫 树支，如5,6,7,8。 其余支路叫连支， 如1,2,3,4。 ① 1 2 4 3 5 6 7 8 ② ③ ④ ⑤ (3,4,8,6) (1,2,6,8) 由任意2个可得第3个。 ③不包含回路
符合定义 的T很多 8 3 ④ ● 图G有5个结点,不管哪 个树T,树支数总是4。 任一个具有n个结点的连 通图,它的任何一个树的 树支数为(n-1) ④ 2021年2月10日星期
2021年2月10日星期 三 13 ① 1 3 5 6 ② ③ ④ ⑤ ① 1 3 5 6 ② ③ ④ ⑤ 符合定义 的 T很多 ① 1 2 4 3 5 6 7 8 ② ③ ④ ⑤ ▪ 图G有5个结点，不管哪一 个树T，树支数总是4。 ▪ 任一个具有n个结点的连 通图，它的任何一个树的 树支数为(n -1)
说明 设想把G的全部支路移去 剩下它的m(5)个节点 (1 为了构成G的一个树,先用 1条支把2个结点连起来 之后,每连接一个新结点,只 ④ 需一条支路,(也只能用一条支 路,则将形成回路)。 因为第一条支路连接了两个结点,所以把 n(=5)个节点全部连接起来所需要的支路 数恰好是(n-1=4) 2021年2月10日星期 14
2021年2月10日星期 三 14 ① 1 2 4 3 5 6 7 8 ② ③ ④ ⑤ 设想把G的全部支路移去，只 剩下它的n (=5)个节点。 ▪ 为了构成G的一个树，先用 1条支路把2个结点连起来。 因为第一条支路连接了两个结点，所以把 n (=5) 个节点全部连接起来所需要的支路 数恰好是(n-1=4)。 ① ② ③ ④ ⑤ ▪ 之后，每连接一个新结点，只 需一条支路，(也只能用一条支 路，否则将形成回路)。 说明
8⑤ 回路 6 不连通 ④ 2021年2月10日星期 15
2021 年 2 月10日星期 三 15 ① 2 5 6 7 8 ② ③ ④⑤ ① 5 6 8 ② ③ ④⑤ 含回路 不连通 ① 1 2 4 3 5 6 7 8 ② ③ ④⑤