1

我希望找到称为紊乱图的特殊类型凯莱图的所有最大团。我在 GAP 工作，我目前使用 GRAPE 包来建立以下内容：

#This is a nice example to work with.
grp := PrimitiveGroup(8,2);
n := LargestMovedPoint(grp);

#The derangement graph of grp
derang := [];
for x in grp do 
    if NrMovedPoints(x) = n then
        AddSet(derang, x);
    fi;
od;

#This uses the GRAPE package.
Cay:=CayleyGraph(grp, derang);

#The following function returns a set of complete subgraphs of Cay (of size n) which are maximal.
#The cliques are returned as vertices of Cay.
max_clique_indices := CompleteSubgraphs(Cay,n,1);

#We convert the vertices of Cay into permutations of grp.
max_clique_perms := [];
for x in max_clique_indices do
    Add(max_clique_perms, Cay.names{x});
od;

#To find all maximum cliques, we perform the following "right translation" action.
#This is where the inefficiency is (I think). We get so many duplicates that must be removed.
maximum_cliques := [];
for x in grp do
    for cl in max_clique_perms do
        Add(maximum_cliques, x*cl);
    od;
od;

maximum_cliques := AsSet(List(maximum_cliques, AsSet));

我已经多次阅读 GRAPE 文档，但找不到生成所有最大派系的命令。在 Sage 中，可以调用 cliquer 命令 ( https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/cliquer.html )，它可以相当快速有效地找到所有最大 cliques (对于根据我的经验，订单 < 3000）。GAP中有这样的选择吗？

注意：我也尝试使用 YAGS 包来使用“CompletesOfGivenOrder(Cay,n)”命令，但我发现它非常慢。

4

1 回答 1

2

几点说明：

  • 要“找到所有最大团”（即具有最大可能大小的团），您可以要求 Grape 计算（G 轨道代表）所有最大团，然后从那些具有最大大小的团中挑选

  • 你的测试程序对我来说运行在几毫秒内，所以我能提供的任何优化都是假设性的；最好知道您有哪些输入在几毫秒内没有完成？

  • 为了测试，我试过了PrimitiveGroup(15,2)；第一个瓶颈是找到最大的派系（在该示例中需要 10 秒）。这可以通过使用digraphs包来克服（只需要 200 毫秒）。但这是否适合您的情况取决于您感兴趣的实际输入。

  • Grape 默认只返回派系 G 轨道的代表；对于凯莱图中的许多问题，处理这些就足够了。由于你没有说你想对这些集团做什么，我不能说你的情况是否有这种方法，但我建议你考虑一下这种可能性，因为到目前为止（如果可能的话）最有效的方法

  • 您确定为低效的位基本上是执行轨道枚举，但实际上是以一种非常低效的方式。要克服这个问题，只需使用 GAP 丰富的轨道功能来解决这个问题。

这是计算所有最大团的程序的修改版本。它在我的计算机上运行几毫秒，但当然对于较大的输入会慢得多。

LoadPackage("grape");

grp := PrimitiveGroup(8,2);
n := LargestMovedPoint(grp);

# the derangement graph of grp; this uses the GRAPE package
Cay := CayleyGraph(grp, Filtered(grp, x -> NrMovedPoints(x) = n));

# compute a set of maximal cliques in Cay which is guaranteed to contain
# at least one representative from each orbit of maximal cliques;
# returned as lists of indices into Cay
max_clique_indices := CompleteSubgraphs(Cay,-1,1);

# compute the size of maximum clique
msize := Maximum(List(max_clique_indices, Length));

# discard all cliques which are not maximum
max_clique_indices:=Filtered(max_clique_indices, c -> Length(c) = msize);

# convert the vertices of Cay into permutations of grp.
max_clique_perms := List(max_clique_indices, i->AsSet(Cay.names{i}));

# we want all maximum cliques, so compute the orbits of the orbit representatives;
# we act on sets by right multiplication
maximum_clique_orbs := Orbits(grp, max_clique_perms, {set,perm} -> AsSet(set*perm));

# finally merge all the orbits into one
maximum_cliques := Concatenation(maximum_clique_orbs);

你也可以试试有向图；如上所述计算 Cay，然后像这样进行：

LoadPackage("digraph");
dig:=Digraph(Cay);
max_clique_indices := DigraphMaximalCliquesReps(dig);
msize := Maximum(List(max_clique_indices, Length));
max_clique_indices:=Filtered(max_clique_indices, c -> Length(c) = msize);
maximum_clique_orbs := Orbits(AutomorphismGroup(dig), max_clique_indices, OnSets);
maximum_cliques := List(Union(maximum_clique_orbs), i->AsSet(Cay.names{i}));
于 2020-07-14T10:27:06.693 回答