我有一个基于图论（也与组合数学有关）的问题，如下所示，想知道设计算法来解决它的最佳方法。
给定4个不同的、由6个节点组成的图（通过“不同”，我指的是不同的结构，例如STAR，LINE，COMPLETE等），以及24个唯一的对象，设计一种算法将这些对象分配给这4个图 4次，使得在4次分配中，图上重复邻居的数量最小化。例如，如果在1次分配的4个图中，对象A和B是邻居，则在其他3次分配中，在最好的情况下，A和B将不会再次是邻居。
显然，这种最小化程度取决于给定的特定图结构。但我更感兴趣的是一种通用解决方案，以便在给定任何4个图结构时，这种最小化是算法的结果。
欢迎提供解决此问题的任何建议/想法，并且一些伪代码可能足以说明设计。谢谢。
表述：
你有24个元素，我将这些元素从A到X（前24个字母）命名。每个元素将在4个图表中占据一个位置。我将为4个图表的24个节点分配一个编号，从1到24。
我将通过24元组=(xA1,xA2...,xA24)来确定A的位置，如果我想将A分配给节点号码8，例如，我将写成(xa1,Xa2..xa24)=(0,0,0,0,0,0,0,1,0,0...0)，其中1在第8个位置。
我们可以说A=(xa1,...xa24)
e1...e24是单位向量(1,0...0)到(0,0...1)
关于运算符“.”的注释:
对于A、...X有一些约束条件，使用这些符号:
Xii位于{0,1}中 和
Sum(Xai)=1 ... Sum(Xxi)=1
Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,... Xx24)=1
因为一个元素只能被分配到一个节点。
我将通过定义每个节点的邻居关系来定义一个图形，比如说节点8有邻居节点7和节点10
要检查A和B是否是节点8的邻居，例如我需要:
A.e8=1 and B.e7 or B.e10 =1，然后我只需要A.e8*(B.e7+B.e10)==1
在函数isNeighborInGraphs(A,B)中，我测试每个节点，并根据邻居关系得到1或0。
符号：
A=(0,0...,1,...,0)=(xa1,xa2...xa24)
B=...
...
X=(0,0...,1,...,0)
IsNeigborInGraphs(A,B)=A.e1*B.e2+... //如果1和2在一个图形中是邻居 例如
actualise(L(A)):
for element in [B,X]
if IsNeigbotInGraphs(A,Element)
L(A).append(Element)
endIf
endfor
N(A)=len(L(A))+Sum(IsneigborInGraph(A,i),i in L(A))
...
N(X)= ...
算法描述
目标函数
min(Sum(N(Z),Z=A to X)
约束条件：
Sum(Xai)=1 ... Sum(Xxi)=1
Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,... Xx24)=1
获得最佳解
4.重复步骤2和3，再进行3次。
K_6，那么你能做的最好的事情就是选择四个元素的集合将24个对象划分为每个集合的基数为6，以便任意两个集合的成对交集的基数不超过2。通过选择在Hasse图中距离最远的集合划分来完成这个任务，其中部分顺序由细化给出。一般情况要困难得多，但也许您仍然可以从这个粗略的解决方案开始，并聪明地将哪个顶点分配给哪个对象在四个分配中。假设您不想循环所有组合并每次计算总和并选择最低的组合，您可以实现一个最小化问题（根据您的约束条件使用线性规划求解器即symplex算法引擎或非线性求解器来解决，从时间角度来看更加困难），并对您的变量（24个）进行约束，具体取决于您路径的形状。您还可以使用免费软件如LINGO/LINDO快速创建决策理论模型并测试其正确性（尽管需要决策理论概念）。