打字猴:1.70100977e+09
1701009770
1701009771 如图8-16所示,图是由一些点和连接这些点的若干线段组成的,这些点称为图的顶点,这些线段称为图的边,称如下二元组为图G:
1701009772
1701009773 G=(V(G),E(G))
1701009774
1701009775
1701009776
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
[ 上一页 ]  [ :1.70100977e+09 ]  [ 下一页 ]