無向圖指是一個二元組<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個頂點的無向完全圖。