论文标题
带有琐碎基本组的三价2层的字符串表示
String representation of trivalent 2-stratifolds with trivial fundamental group
论文作者
论文摘要
我们提供了一个Python程序，该程序能够通过琐碎的基本组来计算和打印所有独特的三价2层图形图。我们的算法使用三个基本操作从任何一组给定图表构建新图形。我们迭代此过程以构建所有所需的图。该算法包括一个优化，以减少生成图的重复，这是通过识别自动形态下图的等效的白色顶点来完成的。我们使用AHU算法的变体来识别这些顶点，并在线性时间内区分同构图。来自AHU算法的返回的字符串还用作哈希功能，以搜索摊销恒定时间的重复图。
We give a Python program that is capable to compute and print all the distinct trivalent 2-stratifold graphs up to $N$ white vertices with trivial fundamental group. Our algorithm uses the three basic operations to construct new graphs from any set of given graphs. We iterate this process to construct all the desired graphs. The algorithm includes an optimization that reduces the repetition of generated graphs, this is done by recognizing equivalent white vertices of a graph under automorphism. We use a variation of the AHU algorithm to identify those vertices and as well to distinguish isomorphic graphs in linear time. The returned string from the AHU algorithm is also used as a hashing function to search for repeated graphs in amortized constant time.
