1701009777
式中称为顶点集，V中元素的个数称为图G的顶点数；图G的顶点个数又被称为图的阶，只有一个顶点的图称为平凡图；称为边集，E中元素的个数称做图G的边数。在不致混淆的情况下，可以将顶点集和边集简记为V和E，图可简记为G=（V，E）。V和E都是有限集的图称为有限图；否则称为无限图。
1701009778
1701009779
我和数学有约：趣味数学及算法解析 [:1701004259]
1701009780
8.4.1 有向图与无向图
1701009781
1701009782
1701009783
1701009784
1701009785
1701009786
如果对于，均有，称该图为无向图；否则对于该图有，即图中的边具有方向性，是一个有序对，称该图为有向图。对于有向图称如下二元组为有向图G：
1701009787
1701009788
G=（V，A）
1701009789
1701009790
1701009791
1701009792
1701009793
1701009794
1701009795
1701009796
称为图G的顶点集，通常称有向图的边为弧，称为图G的弧集，A中的每一个元素al，即V中某两个元素Vi，Vj的有序对可以记为，被称为该图的一条从Vi到Vj的弧。对于，存在如下关系：且。
1701009797
1701009798
对于有向图G=（V，A），存在着顺序映射关系：
1701009799
1701009800
1701009801
1701009802
1701009803
1701009804
边（vi，vj）的两节点vi和vj可以表示为，称vj是vi的直接后继，而vi是vj的直接先导。当弧al＝（vi，vj）时，称vi为al的尾，vj为al的头，并称弧al为vi的出弧，为vj的入弧。
1701009805
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 无向图邻接矩阵