Bipartite graphs

المؤلف:  Jean-Claude Fournier

المصدر:  ​Graph Theory and Applications

الجزء والصفحة:  ...

27-7-2016

2299

Agraph G is bipartite if the set of its vertices can be divided into two disjoint subsets such that each edge has an end vertex in each subset. We denote a bipartite graph by G =(X, Y,E), where X and Y are the two subsets of vertices (and so X ∪ Y is the set of all vertices) and E is the set of edges.

Notes.

1) It is important to note that one of the sets X or Y can be empty. As a result, the couple (X, Y ) is not mathematically, strictly speaking, a partition (the sets of a partition should not be empty). Nevertheless the terms “bipartition” and “classes” are often used. It should be noted that with this definition a graph reduced to one vertex, and no edge, is bipartite.

2) A bipartition which defines a graph as bipartite is generally notunique.

3) A bipartite graph has no loops. Indeed a loop would contradict the hypothesis that an edge has its end vertices in different sets. However, a bipartite graph may have multiple edges.

               A bipartite graph G =(X, Y,E)is complete if it is simple and the set of its edges is E = {x y | x ∈ X, y ∈ Y }, that is any pair of a vertex of X And of avertex of Y is an edge of G. It is denoted by K_p,q, where p is the cardinality of X and q the cardinality of Y (see Figure 1.1 for an example).

Bipartite graphs are important in graph theory and for certain applications. They are also interesting as they can be easily characterized by a property  of cycles as in the following classic result.

               Figure 1.1. Two ways of representing the complete bipartite graph K_3,3

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(36-37)