1701009806
我和数学有约：趣味数学及算法解析 [:1701004260]
1701009807
8.4.2 路和回路
1701009808
1701009809
1701009810
1701009811
1701009812
1701009813
1701009814
1701009815
1701009816
在有向图G＝（V，A）中，对于连接和的一条链，如果链上每一条弧的箭线方向与链行进方向一致，称链为一条以为始点、以为终点的路。如果又有，则称之为回路。
1701009817
1701009818
对于无向图和有向图，链的概念是一致的。但对路和回路要求路和回路中边的方向一致。
1701009819
1701009820
我和数学有约：趣味数学及算法解析 [:1701004261]
1701009821
8.4.3 连通图
1701009822
1701009823
任意两点之间至少有一条链直接连起来相通的图叫做连通图，否则称为非连通图。连通图中不存在任何孤立点。任何一个不连通图都可以分为若干连通子图，每一个称为原图的一个分图。若图的任意两点之间均有边相连，则称该图为强连通图。如图8-16所示即为一连通图。
1701009824
1701009825
我和数学有约：趣味数学及算法解析 [:1701004262]
1701009826
8.4.4 无向图邻接矩阵
1701009827
1701009828
用邻接矩阵AG表示如图8-17无向图G时，aij定义为：
1701009829
1701009830
1701009831
1701009832
1701009833
具体的一个无向图如图8-17所示。
1701009834
1701009835
1701009836
1701009837
1701009838
图8-17 无向图
1701009839
1701009840
由图8-17所示，其邻接矩阵如下：
1701009841
1701009842
1701009843
1701009844
1701009845
我和数学有约：趣味数学及算法解析 [:1701004263]
1701009846
8.4.5 有向图邻接矩阵
1701009847
1701009848
用邻接矩阵AD表示如图8-18所示的有向图D时，aij定义为：
1701009849
1701009850
1701009851
1701009852
1701009853
由图8-18所示，其邻接矩阵如下：
1701009854
1701009855
