Set A有n个设备.B组有m个设备.A中的某些设备与B中的设备兼容,B中的某些设备与A中的设备兼容.
我希望尽可能多的兼容设备相互连接.(没有必要让A中的设备a和B中的b相互兼容.)
为清晰起见编辑:任何设备都可以链接到0,1或2个其他设备,但不能链接到自身.
最终所有设备(或除了两个,如果"结束"不符合)应该在1对1链接在一起.可以将任何一个设备链接到任何其他设备.但是A中的任何设备都不与A中的任何设备兼容(但它们是可链接的),并且B中的设备也是如此.
If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3
a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1
然后是图G
a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1
是一个最佳图表.
G不必是循环的,但也可以.
有没有聪明的方法来解决这个问题？