On the computer enumeration of finite topologies
On the computer enumeration of finite topologies
复制标题
有限拓扑的计算机枚举
DOI：
10.1145/363282.363311
复制
发表时间：
1967
期刊：
影响因子：
--
通讯作者：
M. Lynn
中科院分区：
文献类型：
--
作者：
J. W. Evans;F. Harary;M. Lynn
从理论和计算两方面考虑了从有限点集可以形成的拓扑数的枚举问题。某些基本结果的建立，导致枚举有限拓扑的算法，并给出计算结果为N N 7。计算工作的一个有趣的副作用是发现了一个理论错误，这个错误已经被引入文献中;按时间顺序，计算机在组合学中的使用代表了早期的应用，这个副作用强调了它在这一领域的持续有用性。它似乎已成为一个几乎经典的评论，有nre没有有趣的问题，关于拓扑上的tinite munber点。对于一个拓扑学家这可能是真的;然而，从t~ combin~torial的观点来看，确定n个点上有多少个不同的拓扑是有趣的。一句话的解释是为了。实际上有两个不同但相关的计数问题：或者我们可以认为这些点是可区分的（有标号的情况），或者我们可以只计算拓扑空间的同态类的数目（无标号的情况）。我们的目标是枚举n个点的标记拓扑。一个有限拓扑的公理化特征是：取一个具有n个点的集合V的子集的t个规定的集合：~s开，使得两个开集的并和交是<）pen，空集和V本身也是<）pen。一个“标记拓扑”有它的点标记为整数1，“）. ~，，n.两个标号拓扑称为同胚拓扑，如果它们的点集之间存在1-1对应且保持开集。一个“无标号拓扑”或仅仅是一个拓扑是一类有标号拓扑的同胚。本文建立了一些基本结果，从而导出了有限拓扑的计数算法，并给出了n的计算结果。< 7。这项计算工作的一个副作用是发现了以前出现在文献中的错误（见T0-拓扑部分），也许强调了计算机在组合学中的连续有用性。标号拓扑的计数将借助引理来公式化，这是Krish-namurthy [6]所预见的，他用矩阵来表达观察结果。我们使用[4]中给出的有向图的术语。一个有标号的有向图D的n个点的集合V用整数1，.
The problem of enumerating the number of topologies which can be formed from a finite point set is considered both theoretically and computationally. Certain fundamental results are established, leading to an algorithm for enumerating finite topologies, and computed results are given for n N 7. An interesting side result of the computational work was the unearthing of a theoretical error which had been induced into the literature; the use of the computer in combinatorics represents, chronologically, an early application, and this side result underscores its continuing usefulness in this area. It seems to have become an almost classic remark that there nre no interesting problems concerning topologies on a tinite munber of points. To a topologist this may be true; however, from t~ combin~torial point of view, it is irtterest-ing to determine how many different topologies there +are on n points. A word of explauation is in order. There are really two distinct, although related, enumeration problems: either we may consider th.e points as distinguished (the labeled case), or we may only count the number of homaeomorph-ism classes of topological spaces (the unlabeled case). Our object is to enumerate the labeled topologies with n points. A finite topology is characterized axiomatieMly by taking t~ prescribed collection of the subsets of a set V with n points :~s open, such that the union and intersection of two open sets are <)pen, as are the empty set and V itself. A "labeled topology" has its points labeled with the integers 1, ') ... ~, , n. Two labeled topologies arc called homeo-morphic if there is a 1-1 correspondence t.c.txxeen their point sets which preserves open sets. By an "unlabeled Lopology" or just a topology is me~mt a homeomorphism <:lass of labeled topologies. t)l this paper, we estab ish cerlain fundamental results leading to an algorithm for enumerating finite t;opolog'ies and give computed results for n .< 7. A side result of this computational work was to unearth art error which had previously appeared in the literature (see section on T0-Topologies), perhaps underscoring the continuous useful-hess of the computer in combinatorics. The enumeration of labeled topologies will be formulated with the help of a lemma, anticipated by Krish-namurthy [6], who expressed the observation in terms of matrices. We use the terminology of directed graphs given in [4]. A labeled digraph D has its set V of n points labeled with the integers 1, …