无向完全图_用n表示图中顶点数目的完全图

无向完全图

用n表示图中顶点数目的完全图

无向完全图是用n表示图中顶点数目的一种完全图，该图中每条边都是无方向的。在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图

定义

用n表示图中顶点数目，用e表示边或弧的数目。若∈VR，则vi≠vj，那么，对于无向完全图，e的取值范围是0到n(n-1)/2，有n(n-1)图。

解释

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

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

注意

在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。

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

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

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

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

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

注意：

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

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

参考资料

最新修订时间：2023-05-05 02:54

条目作者

概述

定义

解释

参考资料