1701009850
1701009851
1701009852
1701009853
由图8-18所示，其邻接矩阵如下：
1701009854
1701009855
1701009856
1701009857
1701009858
1701009859
1701009860
1701009861
图8-18 有向图
1701009862
1701009863
我和数学有约：趣味数学及算法解析 [:1701004264]
1701009864
8.4.6 有向图弧长邻接矩阵
1701009865
1701009866
对如图8-19所示的有向图也可用弧长矩阵来表示。
1701009867
1701009868
1701009869
1701009870
1701009871
图8-19 有向图弧长
1701009872
1701009873
由图8-19所示，其弧长邻接矩阵如下：
1701009874
1701009875
1701009876
1701009877
1701009878
其中∞其表示两点之间没有弧连接。
1701009879
1701009880
了解这些概念后，我们继续回到七桥问题来。
1701009881
1701009882
【问题】对于七桥问题，有人提出这样一个问题：能不能一次走遍所有的七座桥，而每座桥只准经过一次？
1701009883
1701009884
【分析】
1701009885
1701009886
问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。最后，人们只好把这个问题向俄国科学院院士欧拉提出，请他帮助解决。
1701009887
1701009888
公元1737年，欧拉接到了“七桥问题”。他连试了好几种走法都不行，这问题可真不简单！
1701009889
1701009890
聪明的欧拉终于想出一个巧妙的办法。他用A代表岛区，B、C和D分别代表北、东和西三区，并用曲线弧或直线段表示七座桥，这样一来，七座桥的问题，就转变为数学分支“图论”中的一个一笔画问题，即能不能一笔不重复地画出上面的这个图形，具体如图8-16所示。
1701009891
1701009892
欧拉集中精力研究了这个图形，发现中间每经过一点，总有画到那一点的一条线和从那一点画出来的一条线。这就是说，除起点和终点以外，经过中间各点的线必然是偶数。像上面这个图，因为是一个封闭的曲线，因此，经过所有点的线都必须是偶数才行。
1701009893
1701009894
如图8-16所示，经过A点的线有五条，经过B、C和D三点的线都是三条，没有一个是偶数，从而说明，无论从哪一点出发，最后总有一条线没有画到，也就是有一座桥没有走到。欧拉终于证明了，要想一次不重复地走完七座桥，那是不可能的。
1701009895
1701009896
欧拉提出了自己的见解，即著名的欧拉定理。
1701009897
1701009898
一个连通图能够一笔画的充分必要条件是图中奇点个数为0或2。如图8-16所示的七桥模型，奇点个数为4，因此无法一笔画，因此不能一次走遍所有的七座桥。
1701009899