图论术语

维基百科,自由的百科全书
跳转至: 导航搜索

图论中有许多专有名词,此处总结了一些名词的一般意义和用法。

基本术语[编辑]

一个(一般记作 G )由两类元素构成,分别称为“顶点”(或节点、结点)和“”。每条边有两个顶点作为其端点,我们称这条边“连接”了它的两个端点。因此,边可定义为由两个顶点构成的集合(在有向图中为有序对,见下文“方向”一节)。

图也可以用其他模型来表示,如定义在顶点集合上的二元布尔函数,或者方形(0,1)-矩阵

一个顶点一般表示为一个点或小圆圈。一个图 G顶点集(点集)一般记作 V(G) ,当不发生混淆时可简记为 V 。图 G为其顶点数目,亦即 |V(G)| 。

一条一般表示为连接其两个端点的曲线。以两个顶点 uv 为端点的边一般记作 (u,v)\{u,v\}uv 。一条边连接两个顶点uv时,称uv 相邻。图 G 的边集一般记作 E(G) ,当不发生混淆时可简记为 E

一个自环是两个端点为同一顶点的边。如果有多于一条边连接同一对顶点,则它们均被称为重边。一个图的重数是重复次数最多的边的重复次数。如果一个图不含自环或重边,则称为简单图。多数情况下,如无特殊说明,可以假定“图”总是指简单图。

顶点或边上有标号的图称为有标号的,否则为无标号的。它们的区别在于,无标号的图并没有为顶点或边指定一个特定的顺序。

图的标号一般指按某一规则为图的顶点或边指定一个标号。标号通常是自然数,且一般互不相同。

一个有标号的简单图,点集V = {1, 2, 3, 4, 5, 6},边集E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}}。

一个超边是允许连接任意多个(可以多于两个)顶点的“边”。含有超边的“图”称为超图。边可视为恰连接两个顶点的超边,因此图可视为一种特殊的超图。

G补图 \bar{G} 是这样一的图,它的点集与 G 相同,而每条边 (u,v) 存在于 \bar{G} 中当且仅当它不存在于 G 中。

空图秃图是没有边的图。

如果一个图有无穷多的顶点和/或边,则称其为无穷的,否则为有穷的。如果一个图是无穷的,但每个顶点的度(见下)是有限的,则称为局部有穷的。一般假定“图”指有穷图。

两个图 GH ,如果存在 V(G)V(H) 之间的一一对应,使得图 G 中两个顶点相连当且仅当它们在图 H 中的对应顶点相连,则称图 GH 同构,记作 G\simeq H 。类似地,如果仅仅是 V(G)V(H) 的映射而不一定是一一对应,则称此映射是 GH同态

子图[编辑]

两个图 GH ,如果 V(H)V(G)子集E(H)E(G) 的子集(当然, E(H) 中只能包含将 V(H) 中的顶点相连的边)则称 HG子图。如果图 GH 不相等,即 V(H)V(G)真子集E(H)E(G) 的真子集,则称 HG真子图。如果 HG 的子图或者存在一个 G 的子图与 H 同构,则称 G 包含 H

如果图 G 的子图 H 满足 V(H)=V(G) ,即图 H 包含图 G 的所有顶点,则称 HG支撑子图生成子图

如果图 G 的子图 H 满足边 (u,v) 在图 H 中当且仅当边 (u,v) 在图 G 中,即图 H 包含了图 G 中所有两个端点都在 V(H) 中的边,则称 HG导出子图

对于图的某个性质而言,如果图 G 具有此性质而 G 的任一真子图都不具有此性质,则称 G 是具有该性质的极小图。类似地,如果图 G 具有此性质而任一以 G 为真子图的图都不具有此性质,则称 G 是具有该性质的极大图

路径[编辑]

[编辑]

有标号的树,有6个顶点和5条边

连通无圈图称为,一般记为 T 。其中,度数为1的顶点称为叶子,否则称为内点。有时我们会从树中选出一个顶点作为特殊顶点,称之为以示区分,此时称此树为有根树。有根树常作为有向无环图来处理。

T 的连通子图称为 T子树

无环(不一定连通)图称为森林,森林 F 的子图称为 F 的子森林。

如果图 G 的一个生成子图是树,则称该子图为生成树

是仅有一个顶点不是叶子的树。星也可以表示为完全二分图 K1,n

[编辑]

完全图K5

完全图是所有顶点两两相邻的图。 n完全图,记作 Kn 。如图所示为 K5n 阶完全图有 n(n-1)/2 条边。

图中的是由图中两两相邻的顶点构成的集合。

强连通分量[编辑]

[编辑]

缩图[编辑]

嵌入[编辑]

相邻与度数[编辑]

若两个点之间有一条边,则这两个点相邻,一个点连接的边的条数称为是其度数

独立集[编辑]

连通性[编辑]

距离[编辑]

距离是两个顶点之间经过最短路径的边的数目。

亏格[编辑]

带权图与网络[编辑]

图的方向[编辑]

有向无环图[编辑]

图的着色[编辑]

不变量[编辑]

参见[编辑]