回路中有 个不同顶点,费用矩阵的每行每列都有且只有一个元素与回路中的顶
点的出边与入边一一对应。
例:,图 8.1(a)中 5 城市的货郎担问题的费用矩阵,
令 是哈密尔顿回路,回路上的边对应于费用矩阵中的元素
。
图 8.1 5 城市货郎担问题的费用矩阵及其归约
二、费用矩阵的归约
1、行归约和列归约
定义 8.1 费用矩阵 的第 行(或第 列)中的每个元素减去一个正常数 (或 ),
得到一个新的费用矩阵 ,使得 中第 行(或第 列)中的最小元素为 0,称为费用矩
阵的行归约(或列归约)。称 为行归约常数,称 为列归约常数。
例:把图 8.1(a)中归约常数 , , , , 。
列归约常数 ,所得结果如图 8.1(c)所示。
2、归约矩阵
定义 8.2 对费用矩阵 的每一行和每一列都进行行归约和列归约,得到一个新的费用
矩阵 ,使得 中每一行和每一列至少都有一个元素为 0,称为费用矩阵的归约。矩阵
称为费用矩阵 的归约矩阵。称常数