数学旅行商问题本页总览旅行商问题考虑图 G=(N,E)G=(N,E)G=(N,E)，每条边有权重 cec_ece，寻找一个包含所有节点的权重总和最小的回路。定义 δ(v)\delta(v)δ(v): 和 vvv 相邻的边 δ(S)\delta(S)δ(S): 和 SSS 相邻的边 γ(S)\gamma(S)γ(S): 在 SSS 内的边 切割形式 ∑e∈δ(S)xe≥2,∀S≠N\sum_{e\in\delta(S)}x_e\ge2,\forall S\ne N∑e∈δ(S)xe≥2,∀S=N ∑e∈δ(i)xe=2\sum_{e\in\delta(i)}x_e=2∑e∈δ(i)xe=2 无环形式 ∑e∈E(S)xe≤∣S∣−1,∀S≠N\sum_{e\in E(S)}x_e\le|S|-1,\forall S\ne N∑e∈E(S)xe≤∣S∣−1,∀S=N ∑e∈δ(i)xe=2\sum_{e\in\delta(i)}x_e=2∑e∈δ(i)xe=2