图论数学学科中,图标号(英语:Graph labeling)是对图的和/或顶点的编号(传统上用整数表示)进行赋值[1]

其正式定义为:给定图G = (V, E)顶点标号(Vertex labeling)是V 中一个标号集的函数。这样定义出来的函数图被称为顶点标号图(Vertex-labeled graph)。同样地,边标号(Edge labeling)是E中一个标号集的函数,其对应函数图被称为边标号图(Edge-labeled graph)。

当边标号是有序集(例如实数)的成员时,它可被称为加权图(Weighted graph)。

在没有限定条件时,术语标号图通常是指所有标号都不同的顶点标号图。这样的图可以等价地用连续整数{1,…,|V|}来标记,其中|V|是图中顶点的数量[1]。在许多应用中,边或顶点常常被赋予在关联域中有意义的标号。例如可以为边指定遍历事件顶点的表示“花费”的权重[2]

在以上定义中,图被看作是一个有限的无向简单图。然而,标号的概念可以应用于图的所有扩展和泛化领域。例如,在自动机理论形式语言理论中,对带标号的多重图进行研究会更方便,其中标号指的是连队顶点对之间带标号的边[3]

历史

大多数图标号的起源可以追溯到亚历克斯·罗萨(Alex Rosa)在1967年的论文中提出的标号问题[4]。他确定了三种类型的标号,分别称为α-、β-和ρ-标号。β-labelings后来被所罗门·格伦布更名为优美(Graceful),之后这个名称开始变得流行起来[5]

特殊案例

优美标号

 
优美标号实例之一,其中顶点标号为黑色的,边标号为红色的。

当一个图的顶点被从0到|V|(所有顶点)标号时,该图被认为是优美的,这些标号还使得边拥有了从1到|E|的边标号。对于任意边e, e的标号是其两个顶点之间的编号差的绝对值。换句话说,如果e与编号为i和j的顶点相关联,e将被标记为|i - j|。因此,当且仅当存在一个输入能使得边集E所映射的正数最大值不超过一个|E|时认为图G = (V, E)是优美的。

罗萨在他的原始论文中证明了所有大小等价于1或2(除以4取模)的欧拉图都不是优美的。图的某些族是否优美是图论研究的一个重要领域。可以说,图标号中最大的未经证实猜想是Ringel-Kotzig猜想,其假设了所有的树都是优美的。这个猜想目前已经在道路结构、毛虫树结构和一些其他无限树族中被证明。Kotzig自己也把努力证明这个猜想的过程称为“疾病”[6]

边优美标号

在简单图(没有自环重边)中,针对p个顶点和q条边的边优美标号是指将边分别标号为{1, …, q} ,并取定顶点标号为与其直接连接的边数,因此所有顶点标号的取值范围为从0到p − 1。如果图G使用的标号为边优美标号,那么该图被称为边优美。

边优美标号是由S. Lo在1985年首次引入的[7]

在Lo的理论中,判断一个图是边优美的有以下必要条件:

 

协调标号

图G的协调标号是指从G的顶点集输入到整数系数k(G的边数),通过将边(x,y)的边标号取为两个顶点x,y的标号之和(除以k取模),在G的边与整数系数k之间形成一个映射。协调图是指有协调标号的图。正如佩特森图所示,奇数周期是和谐的。据推测如果一个顶点标签允许被重复使用,那么所有树都是和谐的[8]。七页的书图中,K1,7 × K2提供了一个图为不和谐的例子[9]

图着色

图着色是图标号的一个子类。顶点着色为对相邻顶点分配不同的标号;边着色为对相邻边分配不同的标号。

幸运标号

图G的幸运标号是将正整数赋值给G的顶点,如果用Sv)表示v邻域上的标号之和,那么S便是G的顶点着色。若G的最小幸运数字为k,那么其幸运标号为整数{1,…,k}的集合[10]

参考文献

  1. ^ 1.0 1.1 Weisstein, Eric W. (编). Labeled graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  2. ^ "Different Aspects of Coding Theory", by Robert Calderbank (1995) ISBN 0-8218-0379-4, p. 53"
  3. ^ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
  4. ^ Gallian, J. A Dynamic Survey of Graph Labelings, 1996-2005. The Electronic Journal of Combinatorics. 
  5. ^ Rosa, A. On certain valuations of vertices in a graph. 
  6. ^ Vietri, Andrea. Sailing towards, and then against, the graceful tree conjecture: some promiscuous results. Bull. Inst. Comb. Appl. 2008, 53: 31–46. ISSN 1183-1278. Zbl 1163.05007. 
  7. ^ Lo, Sheng-Ping. On edge-graceful labelings of graphs. Congressus Numerantium. 1985, 50: 231–241. Zbl 0597.05054. 
  8. ^ Guy (2004) pp.190–191
  9. ^ Gallian, Joseph A., A dynamic survey of graph labeling, Electronic Journal of Combinatorics, 1998, 5: Dynamic Survey 6 [2019-05-27], MR 1668059, (原始内容存档于2019-11-08) .
  10. ^ Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor. Lucky labelings of graphs. Inf. Process. Lett. 2009, 109: 1078–1081. Zbl 1197.05125.