尝试用二划分问题归约到二维最短路问题。

假设有一个集合\(S\), 定义其中的元素为\(a_{i}\)

权函数为\(w: S \rightarrow R\)

定义顶点集合为\(N = \{(x,0), (0,x) | \forall x \in S\}\)

边集\(E = \{((a_{i},0), (a_{i+1},0)),((0,a_{i}), (a_{i+1},0)),((0,a_{i}), (0,a_{i+1})),((a_{i},0), (0,a_{i+1}))| 1 \leq i < |S|\}\)

定义\(\large V = (\frac{\sum w(a_{i})}{2}, \frac{\sum w(a_{i})}{2})\)

\[\sum\]