般先确定一个可行方案，然后不断改善可行方案 就能求出最优方案。具体作法如下： 1.确定可行方案 一个连通图中，若有奇点，则奇点个数必为偶数。 把奇点配对后，沿连接每对奇点的链增加重复边，则新 图中没有奇点，这样，带有重复边的新图就是可行方案。 2.调整可行方案 可以证明最优方案具有下述两条性质，并可以按这 两条性质不断调整可行方案，直至获得最优方案。 (1)最优方案中，每一条边上最多有一条重复边。 如果可行方案中，某条边重复边多于一条，则可以 成对减去重复边，直至满足该性质。 (2)最优方案的图中，每个圈上的重复边权数之和不 大于该圈总权数的一半。否则，将该圈上的重复边去掉，一般先确定一个可行方案，然后不断改善可行方案 就能求出最优方案。具体作法如下： 1.确定可行方案 一个连通图中，若有奇点，则奇点个数必为偶数。 把奇点配对后，沿连接每对奇点的链增加重复边，则新 图中没有奇点，这样，带有重复边的新图就是可行方案。 2.调整可行方案 可以证明最优方案具有下述两条性质，并可以按这 两条性质不断调整可行方案，直至获得最优方案。 ⑴最优方案中，每一条边上最多有一条重复边。 如果可行方案中，某条边重复边多于一条，则可以 成对减去重复边，直至满足该性质。 ⑵最优方案的图中，每个圈上的重复边权数之和不 大于该圈总权数的一半。否则，将该圈上的重复边去掉