请输入您要查询的百科知识:

 

词条 无向图
释义

【定义】

一个无向图(undirected graph)是一个二元组<V,E>,其中:

1.V是非空集合,称为顶点集

2.E是V中元素构成的无序二元组的集合,称为边集

【解释】

直观来说,若一个图中每条边都是无方向的,则称为无向图。

(1)无向边的表示

无向图中的边均是顶点的无序对,无序对通常用圆括号表示。

【例】无序对(vi,vj)和(vj,vi)表示同一条边。

(2)无向图的表示

【例】下面(b)图中的G2和(c)图中的G3均是无向图,它们的顶点集和边集分别为:

V(G2)={v1,v2,v3,v4}

E(G2)={(vl,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}

V(G3)={v1,v2,v3,v4,v5,v6,v7}

E(G3)={(v1,v2),(vl,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7)}

注意:

在以下讨论中,不考虑顶点到其自身的边。即若(v1,v2)或<vl,v2>是E(G)中的一条边,则要求v1≠v2。此外,不允许一条边在图中重复出现,即只讨论简单的图。

3.图G的顶点数n和边数e的关系

(1)若G是无向图,则0≤e≤n(n-1)/2

恰有n(n-1)/2条边的无向图称无向完全图(Undirected Complete Graph)

(2)若G是有向图,则0≤e≤n(n-1)。

恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

注意:

完全图具有最多的边数。任意一对顶点间均有边相连。

【例】上面(b)图的G2就是具有4个顶点的无向完全图。

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2024/12/23 18:37:10