基础定义

无向图G=<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)}

（3）若G是无向图，则0≤e≤n(n-1)/2

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

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

无向图