离散数学期末复习-最小生成树

文章目录

• 无向图与最小生成树
• • 带权图
  • 最小生成树
  • 求最小生成树的方法
  • 举例

无向图与最小生成树

带权图

对无向图或有向图的每一条边e附加 一个实数w(e),称作边e的权。图连同附加在边上的权称作带权图，记作G=

设T是G的生成树，T所有的边的权的和称作T的权，记作W(T)

最小生成树

带权图权最小的生成树

求最小生成树的方法

避圈法

举例