無向圖

邊沒有方向的圖稱為無向圖。

基本信息

• 中文名：無向圖
• 英文名：undirected graph

• 頂點集：是非空集合
• 邊集：由無向邊構成

定義

無向圖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)

注意：完全圖具有最多的邊數。任意一對頂點間均有邊相連。