图论--边和环
发布网友
发布时间：2024-09-09 15:13
共1个回答
热心网友
时间：2024-11-13 00:30
（1）线图：在有向图D中有两条有向边[公式]和[公式]，则在新的图 L(D) 中画一条从代表边[公式]的顶点到代表边[公式]的顶点的有向边，得到的L(D)就称作D的线图。无向图G的线图 L(G) 也类似的定义
（2）k-边着色：图G的 k-边着色是一个标号映射 [公式] ，其中 [公式] （通常取 S=[k]），S中的标号称为颜色。
真 k-边着色：图G有一个 k-边着色，使得相邻边有不同的颜色，即同色的边子集 [公式] 都是G中的匹配（1-因子），称为正常 k-边着色，也称为真 k-边着色。若图G有一个真 k-边着色，则称图G是可 k-边着色的。可k-边着色就是对边集的一个 k-划分，划分成 k 个边同色的匹配集。对正则图G进行真 k-边着色就相当于将G分解成 k 个1-因子。
图的边色数（色指数）：无圈图G的边色数 [公式] 是使得G可 k-边着色的最小整数 k，也称为色指数。注意带圈图没有真的边着色，所以只考虑无圈图，但允许有重边的情况
（3）重数：在有重边的图G中，如果顶点对 x, y 之间有 m 条边，则称 xy 是重数为 m 的边，重数记作 [公式] 。用 [公式] 表示G中边的重数的最大值
（4）1-因子分解：将正则图G分解成若干个1-因子的分解，称为G的一个1-因子分解。有1-因子分解的图是可1-因子分解的
（5）用色指数对图分类：简单图G如果满足[公式] ，则称它是第一类，如果满足 [公式] ，则称它是第二类
（6）超溢子图：简单图G的一个子图H是超溢子图，如果 n(H) 是奇数并且[公式]
（7）三角形的奇偶性：图G中的三角形T，如果对某个[公式] ， [公式] 是奇数，则称T是奇的。如果对任意 [公式] ， [公式] 是偶数，则称T是偶的。
双三角：即风筝图，由共享一条边的两三角形构成
（8）Hamilton回路（Hamilton环）：历经图G的每个顶点恰好一次的路径[公式]（路径表示其中的 k+1 个顶点[公式]互不相同）称为G的Hamilton路径，闭的Hamilton路径称为Hamilton回路，也称为Hamilton环。若一个图存在哈密顿回路，就称为哈密顿图。也可以等价地定义为哈密顿图是有生成环的图，生成环也称为哈密顿环，生成路径则称为哈密顿路径
（9）连通分量个数：图G的连通分量个数记作 c(G)
（10）坚韧度：如果图G中，对任意割集 [公式] 都有 [公式] ，则称G是 t-坚韧的，G的坚韧度是使得G是 t-坚韧图的最大 t 值
（10）闭包：对图G，在G中递归地添加一些边来连接满足 [公式] 的不相邻的顶点对 u, v ，直到没有这样的顶点对为止，这样得到一个顶点集为 V(G) 的新图，称它是G的（哈密顿）闭包，记作 C(G)
（11）图的幂：简单图G的 k 次幂[公式] ，是顶点集为 V(G) ，边集为 [公式] 的简单图
（12）哈密顿连通性：如果简单图G的每一对顶点 u, v 之间都存在一条从 u 到 v 的哈密顿路径，则图G是哈密顿连通的
（13）有向图的严格性：如果有向图没有圈并且对每个有序顶点对只有一个拷贝是边，则称它是严格的
（14）真k-面着色：2-边连通平面图的一个真面着色，是为其各个面分配颜色使得在边界上具有公共边的面有不同的颜色。存在真k-面着色的图，也称为可 k-面着色的
（15）广义Petersen图：记作 P(n, k)，顶点为[公式] 和 [公式] ，边为 [公式] 、 [公式] 和 [公式] ，其中的加法对 n 取模。Petersen图本身是 P(5, 2)
（16）无桥图：没有割边的图。
立方图：即3-正则图。
平凡割边：是一条割边，删除它后将孤立某一个顶点，其他边割则是非平凡的
（17）鲨鱼图：不可3-边着色的2-边连通3-正则图，并且要求围长至少为5而且没有非平凡3
