运筹学讲义 支撑树的个数 图G的支撑树的个数:r(G) 图的收缩( contract):G·e( e is deleted from G and two endpoints of e are identified) Lν It is clear that if e is a link of G, then v(G e)=v(G)-1, E( e)=EG) O(G·e)=O(G) Cayley's Theorem If e is a link of G, thenr(G)=r(G-e)+rGe Proof:显然,G的任一支撑树或含有e,或不含有e 方面,G的任一不含有巳的支撑树必定也是G-e的支撑树,∴G的不含有e的支撑树的个数 为r(G-e);另一方面,G的任一含有e的支撑树T显然唯一对应G·e的支撑树r·e,∴G的含有 e的支撑树的个数为r(G·e)综上,有r(G)=r(G-e)+r(G·e).l iE: Cayley's Theorem provides a recursive (ise y) method of calculating the number of panning trees in a graph 例求图G的支撑树的个数:运 筹 学 讲 义 5 ▌ 支撑树的个数 图 G 的支撑树的个数： (G) . 图的收缩（contract）： G e （ e is deleted from G and two endpoints of e are identified） It is clear that if e is a link of G ，then  (G  e) = (G) −1， (G  e) =  (G) −1，  (G  e) = (G) . Cayley’s Theorem If e is a link of G ，then  (G) =  (G − e) + (G  e) . Proof：显然， G 的任一支撑树或含有 e ，或不含有 e . 一方面， G 的任一不含有 e 的支撑树必定也是 G − e 的支撑树，  G 的不含有 e 的支撑树的个数 为  (G − e) ；另一方面， G 的任一含有 e 的支撑树 T 显然唯一对应 G e 的支撑树 T  e ， G 的含有 e 的支撑树的个数为  (G  e) .综上，有  (G) =  (G − e) + (G  e) .▍ 注：Cayley’s Theorem provides a recursive（递归） method of calculating the number of spanning trees in a graph. 例 求图 G 的支撑树的个数：