正在加载图片...
上面图(a)与图(b)初看起来似乎是不同的两个图,如果我们正确的确定 它们顶点之间的对应关系: Vb V3 Vd. v4 那么,它们边与边间的对应关系就有: (V1,v2H(Vc, Vb), (V1, V3)-(Vc, Va)(v1, v4(Vc, va) (v2, v3)-(Vb, Vd), (v3, v4)--(Vd, va) 从以上分析可以得出:图(a)和图(b实质上是一个图,只不过表现的形 式不同。 设图G=(VE)与G=(V,E),若它们的顶点存在一一对应,且保持同样 相邻关系,则称G和G'同构,记为G≡G。 5顶点的次。以点ⅴ为端点的边数称为点v的次,记为d(v)。图1中 d(v2)=1,d(v3)=3d(v1)=5。 次数为1的点称为悬挂点,连结悬挂点的边称为悬挂边 次数为0的点称为孤立点,如图1中的点vs 次为奇数的点称为奇点,次为偶数的点称为偶点。 在任何图中,顶点的次数与边数有如下性质: (1)∑d()=2q(其中p为G中顶点数,q为边数) 2)次为奇数的顶点必为偶数个 在有向图D=(VA)中,以v为始点的边数称为点v的出次,记为dt(v) 以v为终点的边数称为点v的入次,记为d(v)。显然d(v)=dt(v)+d(v) 且∑d(v,)=∑d(m,) 5网络。在实际问题中,只用图来描述所研究对象之间的关系往往是 不够的。与图联系在一起,通常还有与点或边有关的某些数量指标,通常 称之为“权”。权可以表示为:距离、费用、通过能力(数量)等。称含 有数量指标的赋权图为网络。与无向图和有向图相对应,网络可分为无向22 上面图(a)与图(b)初看起来似乎是不同的两个图,如果我们正确的确定 它们顶点之间的对应关系: v1 vc,v2 vb,v3 vd,v4 va 那么,它们边与边间的对应关系就有: (v1,v2) (vc,vb),(v1,v3) (vc,vd)(v1,v4) (vc,va), (v2,v3) (vb,vd),(v3,v4) (vd,va)。 从以上分析可以得出:图(a)和图(b)实质上是一个图,只不过表现的形 式不同。 设图 G=(V,E)与 G=(V,E),若它们的顶点存在一一对应,且保持同样 相邻关系,则称 G 和 G同构,记为 G  G。 5.顶点的次。以点 v 为端点的边数称为点 v 的次,记为 d(v)。图 1 中, d(v2)=1,d(v3)=3,d(v1)=5。 次数为 1 的点称为悬挂点,连结悬挂点的边称为悬挂边。 次数为 0 的点称为孤立点,如图 1 中的点 v5。 次为奇数的点称为奇点,次为偶数的点称为偶点。 在任何图中,顶点的次数与边数有如下性质: (1) = = p i d vi q 1 ( ) 2 (其中 p 为 G 中顶点数,q 为边数) (2)次为奇数的顶点必为偶数个。 在有向图 D=(V,A)中,以 vi 为始点的边数称为点 vi 的出次,记为 d + (vi), 以 vi 为终点的边数称为点 vi 的入次,记为 d - (vi)。显然 d(vi)=d+ (vi)+d- (vi)。 且   + − = i i i i d (v ) d (v )。 5.网络。在实际问题中,只用图来描述所研究对象之间的关系往往是 不够的。与图联系在一起,通常还有与点或边有关的某些数量指标,通常 称之为“权”。权可以表示为:距离、费用、通过能力(数量)等。称含 有数量指标的赋权图为网络。与无向图和有向图相对应,网络可分为无向
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有