1879年，伦敦数学会 Kemple 发表了四色问题（4CC） (Four Colour Conjective)的证明，提出了一些天才的想法，但后来发现其证明有错。但是，以后人们还是沿着Kemple的思想直至1976的最后解决（1977年有人又给出一个计算机证明，用50小时）。
在Kemple的证明中，首先提出了“颜色互换法”，用这一方法可以很简单的证明直线图可用二正常着色及X(G)≤5。
例2-17（二色图）平面上n条直线将平面分成若干个区域，则可用二种颜色对其涂色使其为正常涂色。
证明：用归纳法： n=1显然，设n=k成立，即可用二种颜色着色，增加一条直线（第n+1条），将该直线一侧二种颜色互换即知结论成立（图2-47）。
定理2-12(Heawood，1890) G为简单平面图，则X(G)≤5。 首先我们说，任一平面图可以“拉直”为“直线图”（如图2-48）
命题（1948，Fary）简单平面图G都可以“直线化”。
定理2-12的证明：对v用数学归纳法：若v≤5 则显然可用五种颜色涂色（各涂一色即可）。
设v=k 可用五种颜色涂色，来证明v=k+1时结论真。
首先，存在v∈G，d(v)≤5。（事实上，由于G是平面图，则每一面至少有3个边，于
f?图2-47
V7图2-48
是
23，
13f≤2E。
13若?v,d(v)?6则6V?2E23，从而，
E,V?3E,?V?E?f?E?E?E?0，与Euler公式矛盾）
设d(v0)≤5，且设G－v0(将相应的边也去掉) 已按规定涂好五种颜色。 1) d(v0)<5， 则将v0涂以不同于其他邻顶颜色即可
９８
2）d(v0)=5 且V(G－v0)=k 故不妨设v0的邻顶已涂a1， a2， a3， a4， a5 五种颜色。A) 若a1， a2， a3， a4， a5中有二个顶点颜色相同（这是可能的，因它们未必都与一个顶相邻）此时，将第五种颜色涂在v0即得G的一种涂色。(图2-49（a）)
B) 否则，设v1， v2， v3， v4， v5 分别涂以颜色a1，a2，a3，
a4，a5 （如图2-49（b）），设v1，v2不在同一连通分支，且Gaa表示含v1连通分支中由a1，
12V0V0(a)(b)图2-49
'a2颜色的顶及其相邻的边组成的图，考虑将
Ga1a2中a1，a2颜色互换，互换后含v1连通分
'支中仍以五种颜色正常着色，且此时v1变为a2，与a)情况相同，即可正常涂色。
因此，若定理结论不真，v1，v2必在同一连通分支，从而，存在v1到v2的一条轨道。
同理，v1，v3之间有一条轨道，从而v0v1p(v1v3)v3v0为G中一圈。此时，v2在该圈之内（如图2-50），v5在该圈之外（设按v1,v2,?,v5逆时针方向排序）。 同理，v2，v5之间亦有一条轨道。
由于G为平面图，这是不可能的。
（事实上，若v2，v5之间有一条轨道。则由于是平面图，必在某一公共顶与v0v1p(v1v3)v3v0相交，此顶在Gaa中故应为a1或a3色，又在Ga2a5中，故又需为a2或a5色。这是不可
13图2-50
''能的）。▌
11．其他问题
例18 人、羊、狼、菜渡河问题
一个摆渡人,要用一小船把一只狼、一头羊和一筐菜从小河的左岸渡到右岸去，记人 （F），羊（G），狼（W），菜（Cabege），船最多载F、W、G、C中二个，且在无人看守的时候，决不能让狼和羊、羊和白菜在一起，应怎样才能把狼、羊和白菜安全渡过河
９９
去。
以各种可能的状态FWGC/O，FWC/G，FGW/C，FGC/W，FG/WC；O/FGWC，G/FWC，C/FGW，W/FGC，WC/FG为顶点，此岸到彼岸可能的转移路线作边，组成二分图：
FWGC/O FWC/G FGW/C FGC/W FG/WC
① ② ③ ④ ⑤
⑥ ⑦ ⑧ ⑨ ⑩ O/FGWC G/FWC C/FGW W/FGC WC/FG
目标是寻找一条从1到6的交替路。易知①→⑩→②→⑨→③→⑦→⑤→⑥为所求路线。
例19． 夫妻过河
有3对夫妻要过河，船至多可载二个人，条件是任何一个女子不能在其丈夫不在场的情况下与其他男子在一起，问如何安排这3对夫妻渡河？
由条件，可设（H,W）表示H个男子和W个女子在此岸，其中0≤H,W≤3,则易知可取的状态有10个：（0，i）,(i,i),(3,i),I=1,2,3（其中（i,i）表示第i对夫妻）,目标:从(3,3)到(0,0).
规则：1）此→彼 对应：向下，左； 彼→此 向上；
2）仅有一船，故只能此→ 彼→ 此?;
仅有一船，向下，上，左，右一次最多移两格，向斜下，斜上可移一格.
方法：1)?状态转移在坐标系中表示(见图2-52)。
2) 用例18方法,表示为二分图，寻找交替路（作为练习，略）。 3）矩阵法
先找出允许状态集合。
此 彼 此 彼
①（3，3） （0，0） ⑩（0，0） （3，3） ②（3，2） （0，1） ⑨（0，1） （3，2） ③（3，1） （0，2） ⑧（0，2） （3，1）
１００
图2-51
32WA(3,3)1H0123图2-52
④（3，0） （0，3） ⑦（0，3） （3，0） ⑥（1，1） （2，2）
⑤（2，2） （1，1）
决策集 d={（u，v）|u+v=1,2} d k?{(1，1)，(0，2)，(2，0),(1,0),(0,1)} 状态转移规律 S k+1=Sk+(－1)d k 状态转移矩阵
定义：称矩阵A=(aij)V×V是标志图G的邻接矩阵，其中V=|V(G)|
?1,vij?E(G)aij??
0,v?E(G)ij?k
(vi→vi 理解为无边,即aii=0)
v1
?0?如：?1?0?1010??1? v2 0??v3
定理2-6：设A=A(G)是图G的邻接矩阵，则A中的i，j号元表示vi到vj长度为k的轨道的条数。
证明：k=1 显然 设k≤n时 aij(k)
k
表示从vi到vj的轨道的条数 则 aij(n?1)?ai1a1j?ai2a2j???aivavj
(n)(n)(n)而从vi到vj的轨道长为n+1， 可以看成从vi到vk经n步，再从vk到vj(一步)（可能从vk到vj无路，即akj=0。则此时vi经vk到vj的轨道数为0），由归纳假设vi到vk轨道长为n的轨道共有aik条。故vi经vk到vj的轨道共有aikakj条，从而从vi到vj的轨道共有 aij(n?1)(n)
(n)
?ai1a1j?ai2a2j???aivavj条。▋
A?? 其中 0??(n)(n)(n)?0如例27 A=??A?
１０１
?0 0 0 0 0 1 0 1 1 ??0 0 0 0 0 1 1 1 0 ????0 0 0 0 1 0 1 0 0 ???0 0 0 0 0 0 0 0 0 ???A??0 0 1 0 1 0 0 0 0 ??1 1 0 0 0 0 0 0 0 ????0 1 1 0 0 0 0 0 0 ??1 1 0 0 0 0 0 0 0 ??????1 0 0 0 0 0 0 0 0
A1,10?0,A1,10?4,A1,10?68,于是,从v1到v10通过9步 到是不可能的,而经过
(9)(11)(13)11步到的路线由4种,经过13步到的路线由68种.
图论处理问题思想独特，方法变化无穷，非正常思维情况多，要学好图论方法，更好的利用于解决实际问题，要多思考多练习。
１０２