數學家歐拉曾經解決過著名的七橋問題（七橋圖見圖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
巴蜀