设G=，V={v1, v2, v3, v4, v5}，E={(v1,v3) , (v1,v

已知一个无向图G=(V,E),其中V={V1,V2,V3,V4},其邻接矩阵如下

邻接表： v1: v2 - v3 - v4 v2: v1 - v3 - v4 v3: v1 - v2 v4: v1 - v2 深度遍历序列：v1 - v2 - v3 - v4 对应的生成树包含的边是：e12, e24, e23 广度遍历序列：v1 - v2 - v4 - v3 对应的生成树包含的边是：e12, e14, e23

对于一个非连通无向图，共有28条边，则该图至少有多少个顶点？

9个，连通图n(n-1)/2=28，解得n=8，非连通至少还有一个点，一共9个。

证明：

假设有8个顶点，则8个顶点的无向图最多有28条边且该图为连通图

连通无向图构成条件：边=顶点数*（顶点数-1）/2

顶点数>=1，所以该函数存在单调递增的单值反函数

所以边与顶点为增函数关系

所以28个条边的连通无向图顶点数最少为8个

所以28条边的非连通无向图为9个（加入一个孤立点）

无向图的表示

【例】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)}

以上内容参考：百度百科-无向图

无论有向图还是无向图,顶点数n、边数e和度数之间有什么关系？

总度数(D)等于边数(e)的两倍。

D=2e

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

1、若G是无向图，则0≤e≤n(n-1)/2。

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

2、若G是有向图，则0≤e≤n(n-1)。

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

顶点集和边集分别为：

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)}