1701009763
1701009764
1701009765
1701009766
1701009767
图8-16 七桥模型树形图
1701009768
1701009769
哥尼斯堡七桥问题就是一个典型的例子,简化的树形图如图8-16所示。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连接起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
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
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
1701009807
8.4.2 路和回路
1701009808
1701009809
1701009810
1701009811
1701009812
[
上一页 ]
[ :1.701009763e+09 ]
[
下一页 ]