最小树形图 例 例:信息传播 “直接方式”:总经理直接传达; “接力方式”:总经理只给某些部门经理打电话,而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理,依此类推,最后将信息传达到所有部门经理 如何决定传达信息的途径? √信息传播是有向的,有一个“根”。 √信息传播途径(忽略方向时)是一棵树。 以上结构称为树形图,上面这样一类问题称为最小树形图问题10 ➢“直接方式”：总经理直接传达； ➢“接力方式”：总经理只给某些部门经理打电话，而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？ ✓ 信息传播是有向的，有一个“根”。 ✓ 信息传播途径（忽略方向时）是一棵树。 以上结构称为树形图，上面这样一类问题称为最小树形图问题. 例： 信息传播 最小树形图 – 例