[科普中国]-简单图

定义

设G=(V，E)是图，若G中既无吊环又无多重边，则称G是简单图(simplegraph)，如下图，图1是简单图，图2是彼得森(Petersen，1831—1910)图，它是一个有着特殊性质的简单图，一种妖怪图(snark graph)。2

几种简单图举例完全无向图设 是n阶简单无向图，若G中任意节点都与其余n一1个节点邻接，则称G为n阶完全无向图(Complete Graph)，记为 。2

图3所示分别是、 和。

将n阶完全无向图 的边任意加一个方向所得到的有向图称为n阶竞赛图。

设 是n阶简单有向图，若G中任意节点都与其余n-1个节点邻接，则称G为n阶完全有向图。显然，n阶完全有向图 的任意两个节点都是相互邻接的，其边是成对出现的。容易证明，n阶完全无向图 的边数为

补图设 是n阶简单无向图，由G的所有节点以及由能使G成为 需要添加的边构成的图称为G的补图，记为 。2

如图4所示的图互为补图，它们是相对于完全图而言的。

显然，对于任意节点u和v，若u和v在G中不邻接，则u和v在 中邻接，若u和v在G中邻接，则u和v在 中不邻接。2

相关知识点图G(graph)主要由如下两部分组成。

(1)节点集合V，其中的元素v称为节点(vertex或node)；

(2)边集合E，其中的元素称为边(edge)。

通常将图G记为 ，一个图是一个集合上的一种二元关系，这个集合的元素称为图的节点，若两节点之间有这种确定的二元关系，则称有一条边连这两个节点，一个图的节点的数目称为这个图的阶；图的边的数目称为它的度。在文献中，总是将一般的图记为 ，其中， 和 分别表示G的节点集和边集。3

需要说明的是：

①节点又可以称为点、顶点或结点，常用一个实心点或空心点表示，但在实际应用中还可以用诸如方形、圆形、菱形等符号，为了方便可以在这些符号的旁边或内部写上表意名称，如图5所示是一个典型的贝叶斯网络(Bayesian networks)。

②边及其的表示．在图6中的边如 是没有方向的，称为无向边，可以认为A是起点B是终点，也可以认为B是起点A是终点，这时A和B称为边 的端点(endvertices)，在不致混淆时可将边 ，简记为AB、BA、{A，B}或{B，A}，表示边的集合{A，B}={B，A}中的两元素可以相同，是可重集合，与通常的集合有所不同．有方向的边，称为有向边或弧(arc)。

所有边都是无向边的图称为无向图(graph或undirected graph)，所有边都是有向边的图称为有向图(digraph或directed graph)。

③图的拓扑不变性质。需要注意的是，我们讨论的图不但与节点位置无关，而且与边的形状和长短也无关。2

若有一条边连一个图的某两个节点，则称这两个节点相邻，并称这两个节点为这条边的端点；若某一节点是某一条边的端点，则称这个节点和这条边关联；若两条边和同一节点关联，则称这两条边相邻；两个端点是同一个节点的边称为环；若某条边的两个端点不是同一个节点，且只有一条边连这两个节点，则称这条边为杆。

只有一个节点而没有边的图称为平凡图；没有边的图称为孤立图；以某两节点为端点的边可能不止一条，这时称连这两个节点的边为重边，既可以有环，也可以有重边的图称为准图；没有环而可能有重边的图称为带重图；没有重边而可能有环的图称为带环图；既没有重边也没有环的图称为简单图；若一个图的阶是有限的，则称这个图为有限图，否则称这个图为无限图；每两个节点都相邻的简单图称为完全图；若一个n阶图的节点用1，2，…，n来代表，则称它为标定图；若在图的每一条边上赋以一个实数或者对于每个节点赋以一个实数，则称它为赋权图。3