29-08-2016, 10:06 AM
1451242571-Abstract.docx (Size: 20.42 KB / Downloads: 6)
Abstract:
The main purpose of bipartite graph is to make the relation between nodes.
It is a graph whose vertices can be divided into two disjoint sets and (that is, and are each independent sets) such that every edge connects a vertex in to one in . Vertex set and are often denoted as partite sets.
A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.
A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.
Introduction:
A complete bipartite graph is a bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of graph vertices in the two sets are adjacent. If there are and graph vertices in the two sets, the complete bipartite graph (sometimes also called a complete bigraph) is denoted .
A graph may be tested in the Wolfram Language to see if it is a bipartite graph using Bipartite graph.
Programing:
bool isBipartite(int G[][V], int src)
{ int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
colorArr[src] = 1;
queue <int> q;
q.push(src);
while (!q.empty())
{int u = q.front();
q.pop();
for (int v = 0; v < V; ++v)
{if (G[u][v] && colorArr[v] == -1)
{colorArr[v] = 1 - colorArr[u];
q.push(v);
}
else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}}
return true;
}
int main()
{
int G[][V] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
isBipartite(G, 0) ? cout << "Yes" : cout << "No";
return 0;
Uses and Examples:
When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club.
Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations.
Conclusion:
Bipartite graph include the following:Every tree is bipartite. Cycle graphs with an even number of vertices are bipartite. Every planar graph whose faces all have even length is bipartite.Hypercube graphs, partial cubes, and median graphs are bipartite.A graph is bipartite if and only if it does not contain an odd cycle. A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2). The spectrum of a graph is symmetric if and only if it's a bipartite graph