跳到内容

判断图是否为二分图

来源: R/bipartite.R
bipartite_mapping.Rd

此函数判断网络的顶点是否可以映射到两种顶点类型，使得同一类型的顶点之间没有连接。

用法

bipartite_mapping(graph)

参数

graph

输入图。

值

具有两个元素的命名列表

res

一个逻辑标量，如果可以二分则为TRUE，否则为FALSE。

type

可能的顶点类型映射，一个逻辑向量。 如果不存在此类映射，则为空向量。

详细信息

igraph 中的二分图具有一个给出两种顶点类型的“type”顶点属性。

此函数只是检查图是否可以为二分图。 它尝试找到一种映射，该映射将顶点可能地划分为两个类，使得同一类的两个顶点不被边连接。

这种映射的存在等价于图中没有奇数长度的回路。 具有自环边的图不能二分。

请注意，映射不一定是唯一的，例如，如果图至少有两个连通分量，则可以独立映射单独分量中的顶点。

参见

二分图 bipartite_projection(), is_bipartite(), make_bipartite_graph()

作者

Gabor Csardi csardi.gabor@gmail.com

is_bipartite().

示例


## Rings with an even number of vertices are bipartite
g <- make_ring(10)
bipartite_mapping(g)
#> $res
#> [1] TRUE
#> 
#> $type
#>  [1] FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE
#> 

## All star graphs are bipartite
g2 <- make_star(10)
bipartite_mapping(g2)
#> $res
#> [1] TRUE
#> 
#> $type
#>  [1] FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
#> 

## A graph containing a triangle is not bipartite
g3 <- make_ring(10)
g3 <- add_edges(g3, c(1, 3))
bipartite_mapping(g3)
#> $res
#> [1] FALSE
#> 
#> $type
#> logical(0)
#>