什么是“一笔画问题”？

一笔画问题

数学家欧拉曾经解决过著名的七桥问题（七桥图见图1.3-5　⑴图）。下面写出七桥问题的描述：城市中有一条河，河中有A、D两个岛，河上有七座桥来连接两个岛及河的B、C两岸，问：⑴能否刚好经过每座桥一次，既无重复也无遗漏？⑵能否经过桥一次后又回到原来出发点上来？

图1.3-5

七桥问题可以画成图1.3-5中的⑵图的形式，这样七桥问题的第一问就转化成了能否一笔画成一个图的问题。

一个图能否一笔画成需要满足以下条件：先根据图的邻接矩阵求出每个顶点的度数。如果没有度数为奇数的顶点，则可以从任一点开始一笔画成一个图。如果有两个度数为奇数的顶点，则可从这两个奇数顶点中的任一点开始一笔画成一个图。如果度数为奇数的顶点超过两个，则这个图不能够一笔画出。

图1.3-6

对于图1.3-5的⑵图或是1.3-6所示的无向图，可以用数组graph存储图的邻接矩阵，用数组degree存储每个顶点的度数，用变量Total_d存储总的度数，用变量Odd_num存储度数为奇数的顶点个数，用变量start存储一笔画的起始顶点。

一笔画程序如下：

program stroke(input,output);

var graph:array[1..20,1..20] of 0..1;

degree:array[1..20] of integer;

odd_num,vn,vi,vj,start,total_d:integer;

begin

odd_num:=0;total_d:=0;start:=1;

write('please input the number of vertex:');

readln(vn);

writeln('please input the data:');

for vi:=1 to vn do

begin

degree[vi]:=0;

for vj:=1 to vn do

begin

read(graph[vi,vj]); ｛读入邻接矩阵｝

degree[vi]:=degree[vi]+graph[vi,vj]｛求每个顶点的度数｝

end;

total_d:=total_d+degree[vi];　｛求总的度数｝

if odd(degree[vi]) then　

begin

odd_num:=odd_num+1; ｛统计奇数顶点的个数｝

start:=vi　　｛确认从奇数顶点出发｝

end

end;

if odd_num>2 then writeln('no solution')｛奇数顶点超过两个显示无解｝

　else

begin

write('the road is: ',start);　

vi:=0;

while total_d>2 do

begin

repeat vi:=vi+1 until graph[start,vi]<>0;｛找连接的相邻点｝

if degree[vi]>1 then　｛先画度数大于1的顶点｝

begin

write('->',vi);

graph[start,vi]:=0;

graph[vi,start]:=0;

degree[vi]:=degree[vi]-1;

degree[start]:=degree[start]-1;

total_d:=total_d-2;

start:=vi;

vi:=0

end

end;

repeat vi:=vi+1 until graph[start,vi]<>0;　｛确认最后一笔｝

writeln('->',vi)

end

end.

输入图1.3-6所示的无向图，程序运行结果如下：

please input the number of vertex:6

please input the data:

0 1 1 0 0 0

1 0 1 1 0 1

1 1 0 0 1 1

0 1 0 0 1 1

0 0 1 1 0 1

0 1 1 1 1 0

the road is: 5->3->1->2->3->6->2->4->5->6->4

巴蜀