Namespaces
Variants
Actions

Difference between revisions of "Graph, bipartite"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: isbn link)
 
(8 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 +
 +
{{MSC|05C}}
 +
 
''bichromatic graph''
 
''bichromatic graph''
  
A graph whose set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448801.png" /> of vertices can be partitioned into two disjoint sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448802.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448803.png" /> (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448804.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448805.png" />) so that each edge connects some vertex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448806.png" /> with some vertex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448807.png" />. A graph is bipartite if and only if all its simple cycles have even length. Another frequently used definition of a bipartite graph is a graph in which two subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448808.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g0448809.png" /> of vertices (parts) are given in advance. Bipartite graphs are convenient for the representation of binary relations between elements of two different types — e.g. the elements of a given set and a subset of it yield the relation of  "membership of an element to a subset" , for executors and types of jobs one has the relation  "a given executor can carry out a given job" , etc.
+
A [[graph]] whose set $V$ of vertices can be partitioned into two disjoint sets $V'$ and $V''$ (i.e. $V=V'\cup V''$, $V'\cap V''=\emptyset$) so that each edge connects some vertex of $V'$ with some vertex of $V''$. A graph is bipartite if and only if all its simple cycles have even length. Another frequently used definition of a bipartite graph is a graph in which two subsets $V'$ and $V''$ of vertices (parts) are given in advance. Bipartite graphs are convenient for the representation of binary relations between elements of two different types — e.g. the elements of a given set and a subset of it yield the relation of  "membership of an element to a subset", for executors and types of jobs one has the relation  "a given executor can carry out a given job", etc.
  
 
An important problem concerning bipartite graphs is the study of matchings, that is, families of pairwise non-adjacent edges. Such problems occur, for example, in the theory of scheduling (partitioning of the edges of a bipartite graph into a minimal number of disjoint matchings), in the problem of assignment (finding the maximum number of elements in a matching), etc. The cardinality of the maximum matching in a bipartite graph is
 
An important problem concerning bipartite graphs is the study of matchings, that is, families of pairwise non-adjacent edges. Such problems occur, for example, in the theory of scheduling (partitioning of the edges of a bipartite graph into a minimal number of disjoint matchings), in the problem of assignment (finding the maximum number of elements in a matching), etc. The cardinality of the maximum matching in a bipartite graph is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488010.png" /></td> </tr></table>
+
$$|V'|-\max_{A'\subseteq V'}(|A'|-|V''(A')|),$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488011.png" /> is the number of vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488012.png" /> adjacent to at least one vertex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488013.png" />. A complete bipartite graph is a bipartite graph in which any two vertices belonging to different subsets are connected by an edge (e.g. the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488014.png" />, see [[Graph, planar|Graph, planar]], Figure 1).
+
where $V''(A')$ is the number of vertices of $V''$ adjacent to at least one vertex of $A'$. A complete bipartite graph is a bipartite graph in which any two vertices belonging to different subsets are connected by an edge (e.g. the graph $K_{3,3}$, see [[Graph, planar|Graph, planar]], Figure 1).
  
A generalization of the concept of a bipartite graph is the concept of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488016.png" />-partite graph, i.e. a graph in which the vertices are partitioned into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044880/g04488017.png" /> subsets so that each edge connects vertices belonging to different subsets.
+
A generalization of the concept of a bipartite graph is the concept of a multipartite or $k$-partite graph, i.e. a graph in which the vertices are partitioned into $k$ subsets so that each edge connects vertices belonging to different subsets.
  
 
====References====
 
====References====
Line 17: Line 21:
  
 
====Comments====
 
====Comments====
 +
The complete bipartite graph on vertex sets of size $a,b$ is denoted $K_{a,b}$.  Similarly the complete multipartite graph on $k$ vertex sets of sizes $a_1,\ldots,a_k$ is denoted $K_{a_1,\ldots,a_k}$.  The complement of a complete multipartite $K_{a_1,\ldots,a_k}$ is a disjoint union of [[complete graph]]s $K_{a_1} \sqcup \cdots \sqcup K_{a_k}$.
  
 +
====References====
 +
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Wilson,  "Introduction to graph theory" , Longman  (1985)</TD></TR>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top"> Biggs, Norman ''Algebraic graph theory'' 2nd ed. Cambridge University Press (1994) {{ISBN|0-521-45897-8}} {{ZBL|0797.05032}}</TD></TR>
 +
</table>
  
====References====
+
[[Category:Graph theory]]
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Wilson,  "Introduction to graph theory" , Longman  (1985)</TD></TR></table>
 

Latest revision as of 13:16, 25 November 2023


2020 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]

bichromatic graph

A graph whose set $V$ of vertices can be partitioned into two disjoint sets $V'$ and $V''$ (i.e. $V=V'\cup V''$, $V'\cap V''=\emptyset$) so that each edge connects some vertex of $V'$ with some vertex of $V''$. A graph is bipartite if and only if all its simple cycles have even length. Another frequently used definition of a bipartite graph is a graph in which two subsets $V'$ and $V''$ of vertices (parts) are given in advance. Bipartite graphs are convenient for the representation of binary relations between elements of two different types — e.g. the elements of a given set and a subset of it yield the relation of "membership of an element to a subset", for executors and types of jobs one has the relation "a given executor can carry out a given job", etc.

An important problem concerning bipartite graphs is the study of matchings, that is, families of pairwise non-adjacent edges. Such problems occur, for example, in the theory of scheduling (partitioning of the edges of a bipartite graph into a minimal number of disjoint matchings), in the problem of assignment (finding the maximum number of elements in a matching), etc. The cardinality of the maximum matching in a bipartite graph is

$$|V'|-\max_{A'\subseteq V'}(|A'|-|V''(A')|),$$

where $V''(A')$ is the number of vertices of $V''$ adjacent to at least one vertex of $A'$. A complete bipartite graph is a bipartite graph in which any two vertices belonging to different subsets are connected by an edge (e.g. the graph $K_{3,3}$, see Graph, planar, Figure 1).

A generalization of the concept of a bipartite graph is the concept of a multipartite or $k$-partite graph, i.e. a graph in which the vertices are partitioned into $k$ subsets so that each edge connects vertices belonging to different subsets.

References

[1] O. Ore, "Theory of graphs" , Amer. Math. Soc. (1962)


Comments

The complete bipartite graph on vertex sets of size $a,b$ is denoted $K_{a,b}$. Similarly the complete multipartite graph on $k$ vertex sets of sizes $a_1,\ldots,a_k$ is denoted $K_{a_1,\ldots,a_k}$. The complement of a complete multipartite $K_{a_1,\ldots,a_k}$ is a disjoint union of complete graphs $K_{a_1} \sqcup \cdots \sqcup K_{a_k}$.

References

[a1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[a2] R.J. Wilson, "Introduction to graph theory" , Longman (1985)
[b1] Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032
How to Cite This Entry:
Graph, bipartite. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_bipartite&oldid=16372
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article