無向圖指是一個(gè)二元組<E,V>，其中E是非空集合V是E中元素構(gòu)成的無序二元組的集合。

中文名

無向圖

外文名

undirected graph

邊集

由無向邊構(gòu)成

頂點(diǎn)集

是非空集合

定義

無向圖

其中：

1.V是非空集合，稱為頂點(diǎn)集。

2.E是V中元素構(gòu)成的無序二元組的集合，稱為邊集。

無向圖

解釋

直觀來說，若一個(gè)圖中每條邊都是無方向的，則稱為無向圖。

（1）無向邊的表示

無向圖中的邊均是頂點(diǎn)的無序?qū)Γ瑹o序?qū)νǔＳ脠A括號(hào)表示。

【例】無序?qū)?vi，vj)和(vj，vi)表示同一條邊。

（2）無向圖的表示

【例】下面(b)圖中的

和

圖中的G3均是無向圖，它們的頂點(diǎn)集和邊集分別為：

注意：

在以下討論中，不考慮頂點(diǎn)到其自身的邊。即若

或

是E(G)中的一條邊，則要求

。此外，不允許一條邊在圖中重復(fù)出現(xiàn)，即只討論簡(jiǎn)單的圖。

3．圖G的頂點(diǎn)數(shù)n和邊數(shù)e的關(guān)系

（1）若G是無向圖，則

恰有

條邊的無向圖稱無向完全圖(Undirected Complete Graph)

（2）若G是有向圖，則

恰有n(n-1)條邊的有向圖稱為有向完全圖(Directed Complete Graph)。

注意：

完全圖具有最多的邊數(shù)。任意一對(duì)頂點(diǎn)間均有邊相連。

【例】上面(b)圖的G2就是具有4個(gè)頂點(diǎn)的無向完全圖。