标签: bipartite

例如,假设我有一个图G =(V,E)其中

V = {A,B,C,D}
E = {(A,B),(A,D),(C,D)}

该图是二分的,因此可以分成两个不相交的集合{A,C}和{B,D}.我的第一个猜测是我可以简单地走图形并为每个顶点指定交替的颜色.是这种情况,还是比这更复杂/更简单？有没有任何已知的算法？

有没有人知道Python中用于计算最佳二分匹配的任何模块？我尝试了以下两个:

1. 的Munkres
2. 匈牙利

有什么建议？

给定是二分图,我们想列出所有最大完全二分子图.

例如,

顶点集L = {A,B,C,D}

顶点集R = {a,b,c,d,e}

边缘:Aa,Ab,Ba,Bb,Cc,Cd,Dc,Dd,De

最大完全二分是:

{A,B} - {a,b}

{C,D} - {c,d}

{D} - {c,d,e}

我找到了一个强力算法,O(2 ^ n).我不知道是否有一些近似算法或随机算法.

我目前正在编写一个将学生映射到课程的程序.目前,我正在使用SAT-Solver,但我正在尝试实现一个多项式时间/非贪心算法,它解决了以下子问题:

• 有学生(50-150)
• 有科目(10-20),例如'数学','生物','艺术'
• 每个科目(至少一门)都有课程,例如'math-1','math-2','biology-1','art-1','art-2','art-3'
• 学生选择一些(固定的)科目(10-12),并且对于每个科目,学生必须被分配到现有的一门课程(如果可能的话).选择哪个课程'math-1'或'math-2'并不重要.
• 这些课程允许的学生人数最多(20-34)
• 每门课程都在一个固定的区块内(=时间段1到13)
• 学生可能不会被分配到同一区块的课程

我现在描述到目前为止我所做的事情.

(1)忽略课程 - 学生限制

我能够用匈牙利算法/二分匹配来解决这个问题.每个学生可以通过如下建模来单独计算:

• 左节点代表主题'数学','生物','艺术'(学生)
• 右节点表示块'1','2',....'13'
• 从"主题"到"阻止"的每个过程插入一条边

通过这种方式,学生被分配到课程的每个科目,而不参加同一区块的课程.但课程限制被忽略了.

(2)忽略学生的选定科目

我能够用max-flow-algorithm解决这个问题.对于每个学生,建模如下:

• 第1层:从源到每个学生,流量为13
• 第2层:从每个学生到他/她的个人区块,流量为1
• 第3层:从每个学生块到该块中的每个课程,流程为1
• 第4层:通过'max-student-limit'从每个球场到水槽

通过这种方式,学生选择任意课程,并且课程限制已满.但是他/她可能不幸并被分配到'数学-1','数学-2'和'数学-3'而无视主题'生物'和'艺术'.

(3)贪婪的匈牙利人

我的另一个想法是一次匹配一个学生与匈牙利算法并调整权重,以便"更多空课程"是首选.例如,可以建模:

• 左节点是学生的主题
• 右边节点是块
• 对于每个球场,插入一个边缘从主体到球场的块重量=自由座位数

然后计算最大权重匹配.

我真的很感激任何建议/帮助.

谢谢!

我的问题很简单：

如何在Gephi中绘制二分图，其布局与您在所附图像中看到的布局类似？

我真的无法在Gephi的选项中找到合适的布局

谢谢

我正在学习使用networkx python模块对二分图进行一些匹配。模块中有两个函数可以提供图形的最大基数匹配：

1. nx.maximal_matching()
2. nx.bipartite.maxmum_matching()

请注意，尽管其名称为maximal_matching，但其文档确实声明“在图中找到最大基数匹配”。

由于我的图是二分图，因此我假设这2个图将给出相同的结果，至少两个都具有相同的边数。但是，我的代码似乎暗示nx.maximal_matching()给出了错误的答案：正如所nx.bipartite.maxmum_matching()暗示的，可能还有一个优势。

下面是我的工作代码：

import networkx as nx
from networkx import bipartite    

def plotGraph(graph,ax,title):    
    pos=[(ii[1],ii[0]) for ii in graph.nodes()]
    pos_dict=dict(zip(graph.nodes(),pos))
    nx.draw(graph,pos=pos_dict,ax=ax,with_labels=True)
    ax.set_title(title)
    return   

if __name__=='__main__':    
    #---------------Construct the graph---------------
    g=nx.Graph()
    edges=[
            [(1,0), (0,0)],
            [(1,0), (0,1)],
            [(1,0), (0,2)],
            [(1,1), (0,0)],
            [(1,2), (0,2)],
            [(1,2), (0,5)],
            [(1,3), (0,2)],
            [(1,3), (0,3)],
            [(1,4), (0,3)],
            [(1,5), (0,2)],
            [(1,5), (0,4)],
            [(1,5), (0,6)],
            [(1,6), (0,1)],
            [(1,6), (0,4)],
            [(1,6), (0,6)]
            ]

    for ii in edges:
        g.add_node(ii[0],bipartite=0)
        g.add_node(ii[1],bipartite=1)

    g.add_edges_from(edges)

    #---------------Use maximal_matching--------------- …

我有K组数据点,我想制作大小为K的组,以最小化组内距离的总和.我熟悉匹配算法与二分图,但我想这两个以上.

有任何想法吗？

编辑:

每组将由每组中的一个元素组成,不允许重复.

例如:你有{a1,a2,a3},{b1,b2,b3},{c1,c2,c3}你想创建组,例如{a1,b3,c3},{a2,b1,c2}, {a3,b2,c1}最小化组内距离的总和.

我正在使用NetworkX使用nx.bipartite.random_graph或生成二分图nx.bipartite.gnmk_random_graph,如下所示:

B = bipartite.gnmk_random_graph(5,6,10)
bottom_nodes, top_nodes = bipartite.sets(B)

但是,我收到一个错误:

networkx.exception.AmbiguousSolution: Disconnected graph: Ambiguous solution for bipartite sets.

它只是一行,所以我不确定我是怎么做错的,以及为什么他们的包会返回(我假设是)一个无效的二分图.

谢谢.

编辑:我刚刚意识到我需要为第三个参数指定最小边数/概率.

例如bipartite.random_graph(5,6,0.6),p>0.5摆脱了错误.同样,bipartite.gnmk_random_graph(5,6,11)在哪里k>n+m.我没有意识到这种情况,因为我假设如果边缘的数量低于连接每个顶点所需的边数,那么就会有一些浮动顶点.

谢谢你的帮助!

我有一个断开的二分无向图.我想完全断开图表.只有我可以执行的操作是删除节点.删除节点将自动删除其边缘.任务是最小化要删除的节点数.图中的每个节点最多有4个边.

通过完全断开图形,我的意思是不应该通过链接连接两个节点.基本上是一个空边集.

我试图解决以下问题,但我的算法太慢了.那是因为我使用Edmonds - Karp算法来找到最大流量,当应用于二分图时,它也会产生最大匹配.它的运行时间是n ^ 5.我想知道任何更快的算法来解决这个问题(特别是对于二分图).我目前正在研究的一种算法是Relabel to Front,它是n ^ 3.