关于图的bondage数的一点注记

对B.Hartnell关于图的bondage数的一个定理给出一个新的证明,并得到一些关于平面图的有用的结果.

平面图的Alcuin数

广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数,给出了该类图Alcuin数的完全刻画。

图的同调与上同调定理(英文)

将图视为多面形集合,通过本文作者所建立的图的同调与上同调两个互对偶的定理,直接导出有关图的平面性分别由Lefschetz,MacLane和Whitney沿不同理论路线得到的三个判准,同时还给出了在任何已知亏格(非零)曲面上图的可嵌入性的判准.

基于平面图覆盖的大规模图可达查询处理

随着语义网络、社交网络、生物信息网络等新兴应用的涌现及普及,图数据的规模不断增大,针对大规模图数据的研究成为当今的研究热点和难点。可达查询是图数据处理中频繁使用的基础性查询,一些复杂的查询能够分解成包含多个可达查询的操作集合,其高效处理具有重要意义。针对大规模图的可达查询,提出了一种基于平面图覆盖的大规模图可达查询处理方法。首先给出了一种基于平面图覆盖的可达标签索引方法(planar graph cover based reachability labeling index method,PGCL)。该方法将最优树作为预处理应用于平面图覆盖,通过最优树创建、最优树分解以及树分解平面化处理,得到有向无环图(directed acyclic graph,DAG)的平面图覆盖,最大限度地保留了原图的可达性信息,从而基于覆盖顶点创建二维标签,用于压缩可达传递闭包。设计了基于PGCL的可达查询算法,有效实现了大规模图的可达查询。通过大量实验证明了提出的查询方法在保证查询的高效性情况下,更好地压缩了传递闭包,提高了可达查询的处理效率。

一种求解平面图的最小顶点覆盖算法

最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。

关于图的圈覆盖

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．

Computing the Girth of Knots

We introduce a method to compute the girth of knots, defined by Herne^ndez and Lin, using the Jones and Brandt-Lickorish-Millett-Ho polynomial. We determine the girth of all knots up to 10 crossings.