6)算法作骤:( Edmonds和E.L. Johnson70年 代,O(m4) 1)若G中无奇顶点,令G*=G,转2,否则转3 2)求G*中的欧拉回路,结束。 ■3)求G中所有奇度顶点对之间的最短路径。 4)以G中奇度顶点集V为顶点集,Vv,,∈V 边n的权为vn之间最短路径的权,得完全 带权图人x少 5)求中K2最小权完美匹配M。 6)将M边对应的各最短路径中的边均在G中加 重复边,得欧拉图G*,转2
6）算法步骤： （J. Edmonds 和E. L. Johnson70 年 代, O(n 4 ) ） 1）若 G中无奇顶点，令G*=G，转 2，否则转 3 。 2）求G*中的欧拉回路，结束。 3）求 G中所有奇度顶点对之间的最短路径。 4）以 G中奇度顶点集V’为顶点集， vi, vj V’ ， 边(vi, vj )的权为 vi, vj之间最短路径的权，得完全 带权图 K2k (2k=|V’|) 。 5）求中 K2k最小权完美匹配 M 。 6）将 M中边对应的各最短路径中的边均在 G中加 重复边，得欧拉图G*，转 2
24X4的黑白格棋盘助互 在4×4的黑白格棋盘(四分之一国 际象棋盘)上跳马,使得它经过每个格 次并且仅一次,最后又回到出发点 能否办到?为什么?
2 44的黑白格棋盘跳马 在44的黑白格棋盘（四分之一国 际象棋盘）上跳马，使得它经过每个格 一次并且仅一次，最后又回到出发点。 能否办到？为什么？
1)构造数学模型: 将棋盘转化为无向图,作无 向图G=,E)。16个格中各放一个顶点顶 点集V马跳“日”字,若马能在ν和v 之间走一步,则v和ν相邻,于是就组成 了边集
1）构造数学模型： 将棋盘转化为无向图，作无 向图G=(V, E) 。16个格中各放一个顶点顶 点集 V。马跳“日”字，若马能在 v i 和 vj 之间走一步，则 v i 和 vj相邻，于是就组成 了边集
2)算法思想: G中是否存在哈密顿回路
2）算法思想： G中是否存在哈密顿回路
定理(必要条件) 若图G是哈密顿图,则对于顶点集 V的每一个非空真子集S,均成立 O(G-S)≤|Sl 其中|S表示S中的顶点数,G-S表示G中 删去顶点子集S后得到的图
定理（必要条件） 若图G是哈密顿图，则对于顶点集 V的每一个非空真子集S，均成立 (G-S) |S| 其中|S|表示S中的顶点数，G-S表示G中 删去顶点子集S后得到的图