无向图指是一个二元组<E,V>，其中E是非空集合V是E中元素构成的无序二元组的集合。

中文名

无向图

外文名

undirected graph

边集

由无向边构成

顶点集

是非空集合

定义

无向图

其中：

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

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

无向图

解释

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

（1）无向边的表示

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

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

（2）无向图的表示

【例】下面(b)图中的

和

图中的G3均是无向图，它们的顶点集和边集分别为：

注意：

在以下讨论中，不考虑顶点到其自身的边。即若

或

是E(G)中的一条边，则要求

。此外，不允许一条边在图中重复出现，即只讨论简单的图。

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

（1）若G是无向图，则

恰有

条边的无向图称无向完全图(Undirected Complete Graph)

（2）若G是有向图，则

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

注意：

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

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