切分定理 评估函数

切分定理

切分

  • 把图中的节点分为两部分,称为一个切分(Cut)

横切边

  • 如果一个边的两个端点,属于切分(Cut)不同的两边,这个边称为横切边(Crossing Edge);

切分定理

  • 给定任意切分,横切边中权值最小的边必然属于最小生成树

树也可以理解图

子节点可以理解为邻接节点

一节点 的所有子节点成为邻接表

评估函数

可以理解为该节点与目标节点的相似程度

这个需要计算的!也就是权值

上一篇:NCRE_Python Day8


下一篇:linux sort uniq cut sed