Clique expension和star expension

2023-12-13 08:33:44

Clique expension（团扩展），也叫连通分量扩展。
其含义是：将超边中所有顶点都连接在一起，比如有3个顶点的超边，扩展成普通图时两两相连就会有3条边。以此类推。连接和n个顶点的超边拓展后有C^2_n条边。同一个超边转换成的边具有跟以前边同样的权重。

star expension（星扩展）
也就是在每个超边中加入一个“星星”,连接上其他的点，所以这种方式会在原来的超节点上增加额外的节点，也就是有加点的操作，而团扩展是没有的。加上的点归入一个集合，原来的点归入另一个集合，这个拓展后的普通图是一个二分图了。

文章来源:https://blog.csdn.net/m0_51576139/article/details/134944213
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。