图论小词典

图论是什么? 它是干什么的? 对于许多人来说，可能并不了解。在填数游戏中，我们用到的图论知识并不多，主要是涉及一些名词。所以，在这一节我们就来介绍图论的一些名词。

【图】 在中学的《几何学》课本上，点被定义为是没有长度、没有宽度、没有厚度的图形。线被定义为是点任意移动的图形，可以是直线，可以是曲线。在图论里，把点称为顶点，把两顶点之间的连线称为边，由若干个不同的顶点V1，V2，…，Vn与连接其中某些顶点的边e1，e2，…，em所组成的图形就称为图。一个有n个顶点、m条边的图常记为(n，m)图或称n阶图。

通常，图用G表示，记为G=(V，E)。顶点的集合，记为V(G) ={Vi}，边的集合记为E(G) ={ek}。在图中，我们关注的只是顶点与边的多少以及这些边连接哪些顶点，而与顶点的位置以及边的形状不是我们关注的内容。

【简单图】 设a，b是两个顶点，e是连接a，b的边，记e=(a，b)，称顶点a，b是边e的端点，称边e关联于顶点a和b，并称a，b是邻接的。如果一条边的两个端点重合，称为自回路或自环。两顶点间若有n(n＞1)条边，则称这些边为平行边。不含平行边和自回路的图称为简单图。

【完全图】 如果G是一个简单图，并且每两个顶点之间都有一条边关联，我们就称G为完全图。

图1-1(a)是3阶完全图，图1-1(b)是6阶完全图。

图1-1 完全图

如果两个图G、G'的顶点个数相同，且两个图的各顶点之间存在一一对应关系，而且这种对应关系保持了顶点间的邻接关系，则称这两个图是同构的。

在图1-2中，图1-2(a)和图1-2(b)是同构的。

可以把一个图变换成同构的另一个图，这样的变换称为拓扑变换。

图G中与某个顶点V相关联的边数称为该顶点的度数，记为d(V)。

度数为0的顶点称为孤立点。

图1-2 同构图

顶点都是孤立点的图称为零图。

【补图】 设G是n阶简单图，在G中添加一些边后，可使G成为n阶完全图，由这些添加边和n个顶点构成的图称为图G的补图，记为G。

图1-3(a)和图1-3(b)互为补图。

图1-3 补图

【通路】 设n为正整数，V0，V1，…，Vn是图G的顶点，e1， e2，…，en是图G的边，并且Vi-1和Vi分别是ei的起点和终点(i=1，2，…，n)，则称序列V0e1V1e2，…，Vn-1enVn为图G中从V0至Vn的通路，n称为该通路的长度。如果V0=Vn，则称该通路为闭的，否则称为开的。

【连通图】 设V1和V2是图G的顶点。如果在G中存在从V1至V2的通路，则称在G中从V1可达V2。如果图G的任意两个顶点都是可达的，则称G是连通图。

起点与终点重合的通路称为回路。

【树】 不含回路的连通图称为树。树中的边称为树枝。树中度数为1的顶点称为树叶，度数大于1的顶点称为枝点。通常，树用T表示。显然，若树T有n个顶点和m条边，则m=n-1。