轻量级边

October 15, 2022

Content #

无向图 G=(V,E)\(的一个切割\) 的一个切割 (S,V-S) 指的是集合V的一个划分。如果一条边 \((u,v)\in E\) 的一个端点位于集合S，另一个端点位于集合\(V-S\)，则称该条边横跨切割\((S,V-S)\)。请问什么是轻量级边(light edge)？

在横跨一个切割的所有边中，权重最小的边称为劲量级边。轻量级边可能不是唯一的。