来自当知百科
跳转到: 导航搜索

  【定义】

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

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

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

  【解释】

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

  (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个顶点的无向完全图。

个人工具
名字空间

变换
查看
操作
导航
工具箱