The isomorphism problem is a fundamental problem in network analysis, which
involves capturing both low-order and high-order structural information. In
terms of extracting low-order structural information, graph isomorphism
algorithms analyze the structural equivalence to reduce the so
本文提出了关于图同构问题的方法,其中包括跟颜色精细算法和基于 Weisfeiler-Leman 算法的 k 维泛化相关的一些理论。我们证明了,如果对于所有树 T,T 到 G 的同态数量(Write out as Hom (T,G))等于 T 到 H 的同态数量,那么颜色精细算法无法区分二者。而如果我们放弃非负性约束,在二者具有相同长度的路径时,寻找任意实数解的算法存在,且两个图形在分数同构时,颜色精细算法无法区分它们。最后,我们提出了一个几乎线性时间的算法来判定对于给定的图 G 和 H,是否存在一棵树 T 满足 Hom (T,G) = Hom (T,H)。