1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/bipartite.R
\name{bipartite_mapping}
\alias{bipartite_mapping}
\title{Decide whether a graph is bipartite}
\usage{
bipartite_mapping(graph)
}
\arguments{
\item{graph}{The input graph.}
}
\value{
A named list with two elements: \item{res}{A logical scalar,
\code{TRUE} if the can be bipartite, \code{FALSE} otherwise.} \item{type}{A
possible vertex type mapping, a logical vector. If no such mapping exists,
then an empty vector.}
}
\description{
This function decides whether the vertices of a network can be mapped to two
vertex types in a way that no vertices of the same type are connected.
}
\details{
A bipartite graph in igraph has a \sQuote{\code{type}} vertex attribute
giving the two vertex types.
This function simply checks whether a graph \emph{could} be bipartite. It
tries to find a mapping that gives a possible division of the vertices into
two classes, such that no two vertices of the same class are connected by an
edge.
The existence of such a mapping is equivalent of having no circuits of odd
length in the graph. A graph with loop edges cannot bipartite.
Note that the mapping is not necessarily unique, e.g. if the graph has at
least two components, then the vertices in the separate components can be
mapped independently.
}
\examples{
## Rings with an even number of vertices are bipartite
g <- make_ring(10)
bipartite_mapping(g)
## All star graphs are bipartite
g2 <- make_star(10)
bipartite_mapping(g2)
## A graph containing a triangle is not bipartite
g3 <- make_ring(10)
g3 <- add_edges(g3, c(1, 3))
bipartite_mapping(g3)
}
\seealso{
Bipartite graphs
\code{\link{bipartite_projection}()},
\code{\link{is_bipartite}()},
\code{\link{make_bipartite_graph}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{bipartite}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Bipartite.html#igraph_is_bipartite}{\code{igraph_is_bipartite()}}.}
|
