《(8.3.1)--8.2.2求最小树的破圈法和避圈法.ppt》由会员分享，可在线阅读，更多相关《(8.3.1)--8.2.2求最小树的破圈法和避圈法.ppt（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、8.2.2 8.2.2 求最小树的破圈法和避圈法求最小树的破圈法和避圈法定理定理 图图 G有生成树的充分必要条件为图是连通图。有生成树的充分必要条件为图是连通图。定义（最优树）定义（最优树）在赋权图在赋权图G中，一棵生成树所有树柱上权的和，称为生成中，一棵生成树所有树柱上权的和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。树的权。具有最小权的生成树，称为最优树（或最小树）。求最小树的方法有求最小树的方法有破圈法破圈法和和避圈法避圈法。v1v7v4v3v2v5v62015916253281741 12336例例7破圈法破圈法v1v7v4v3v2v5v620159162532817
2、412336v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v693174123总造价总造价=1+4+9+3+17+23=57v1v7v4v3v2v5v620159162532817412336避圈法避圈法v1v7v4v3v2v5v5v620159162532817412336总造价总造价=1+4+9+3+17+23=57