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