In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Mathematics and Computer science, a graph is the basic object of study in Graph theory. For other uses see Vertex. In Graph theory, a vertex (plural vertices) or node is the fundamental unit out In Mathematics, two sets are said to be disjoint if they have no element in common In Mathematics and Computer science, a graph is the basic object of study in Graph theory. In Graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent Equivalently, a bipartite graph is a graph that does not contain any odd-length cycle. Cycle in Graph theory and Computer science has several meanings A closed walk with repeated vertices allowed
The two sets U and V may be thought of as the colors of a coloring of the graph with two colors: if we color all nodes in U blue, and all nodes in V green, each edge has endpoints of differing colors, as is required in the graph coloring problem. In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a In contrast, such a coloring is impossible in the case of a nonbipartite graph, such as a triangle): after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. Some of the finite structures considered in Graph theory have names sometimes inspired by the graph's topology and sometimes after their discoverer
One often writes G = (U, V, E) to denote a bipartite graph whose partition has the parts U and V. If |U| =|V|, that is, if the two subsets have equal cardinality, then G is called a balanced bipartite graph. In Mathematics, the cardinality of a set is a measure of the "number of elements of the set"
Contents |
Examples
- Every tree is bipartite. In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path.
- Cycle graphs with an even number of vertices are bipartite. In Graph theory, a cycle graph is a graph that consists of a single cycle, or in other words some number of vertices connected in a closed chain
Testing bipartiteness
If a bipartite graph is connected, its bipartition can be defined by the parity of the distances from any arbitrarily chosen vertex v: one subset consists of the vertices at even distance to v and the other subset consists of the vertices at odd distance to v. In Mathematics and Computer science, connectivity is one of the basic concepts of Graph theory. In Mathematics, the parity of an object states whether it is even or odd
Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets U and V, separately within each connected component of the graph, and then examine each edge to verify that it has endpoints assigned to different subsets.
Applications
Bipartite graphs are useful for modelling matching problems. In the Mathematical discipline of Graph theory a matching or edge independent set in a graph is a set of edges without common vertices An example of bipartite graph is a job matching problem. Suppose we have a set P of people and a set J of jobs, with not all people suitable for all jobs. We can model this as a bipartite graph (P, J, E). If a person px is suitable for a certain job jy there is an edge between px and jy in the graph. The marriage theorem provides a characterization of bipartite graphs which allow perfect matchings. In Mathematics, the marriage theorem (1935 usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing In the Mathematical discipline of Graph theory a matching or edge independent set in a graph is a set of edges without common vertices
Bipartite graphs are extensively used in modern Coding theory, especially to decode codewords received from the channel. Coding theory is one of the most important and direct applications of Information theory. In Telecommunication, a code word is an element of a Code. Each code word is a Sequence of symbols assembled in accordance with the specific rules of Factor graphs and Tanner graphs are examples of this. In Mathematics, a factor graph is an XF- Bipartite graph where X=\{X_1X_2\dotsX_n\} is a set of variables and F=\{f_1f_2\dotsf_m\} A Tanner graph is a Bipartite graph used to specify constraints or equations which specify Error correcting codes.
In computer science, a Petri net is a mathematical modelling tool used in analysis and simulations of concurrent systems. A Petri net (also known as a place/transition net or P/T net) is one of several Mathematical Modeling languages for the description of discrete A system is modelled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.
In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. Projective geometry is a non- metrical form of Geometry, notable for its principle of duality. In Combinatorics a Levi graph or incidence graph is a Bipartite graph associated with an Incidence structure. In Mathematics, specifically Projective geometry, a configuration consists of a finite set of points and a finite set of lines such that each point is incident to
Properties
- A graph is bipartite if and only if it does not contain an odd cycle. ↔ In Graph theory, a cycle graph is a graph that consists of a single cycle, or in other words some number of vertices connected in a closed chain Therefore, a bipartite graph cannot contain a clique of size 3 or more. In Graph theory, a clique in an Undirected graph G is a set of vertices V such that for every two vertices in V there exists an edge connecting
- A graph is bipartite if and only if it is 2-colorable, (i. e. its chromatic number is less than or equal to 2). In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a
- The size of minimum vertex cover is equal to the size of the maximum matching (König's theorem). In Computer science, the vertex cover problem or node cover problem is an NP-complete problem and was one of Karp's 21 NP-complete problems. In the Mathematical discipline of Graph theory a matching or edge independent set in a graph is a set of edges without common vertices In the mathematical area of Graph theory, König's theorem describes an equivalence between the Maximum matching problem and the minimum Vertex cover
- The size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In Graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent In the Mathematical discipline of Graph theory a matching or edge independent set in a graph is a set of edges without common vertices
- For a connected bipartite graph the size of the minimum edge cover is equal to the size of the maximum independent set. In Mathematics and Computer science, connectivity is one of the basic concepts of Graph theory. In the mathematical discipline of Graph theory, a covering (or cover) of a graph is a set of vertices (or edges such that each edge (vertex In Graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent
- For a connected bipartite graph the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices. In Mathematics and Computer science, connectivity is one of the basic concepts of Graph theory. In the mathematical discipline of Graph theory, a covering (or cover) of a graph is a set of vertices (or edges such that each edge (vertex In Computer science, the vertex cover problem or node cover problem is an NP-complete problem and was one of Karp's 21 NP-complete problems.
- Every bipartite graph is a perfect graph. In Graph theory, a perfect graph is a graph in which the chromatic number of every Induced subgraph equals the clique number of that
See also
External links
- Eric W. Weisstein, Bipartite Graph at MathWorld. In the Mathematical field of Graph theory, a complete bipartite graph or biclique is a special kind of Bipartite graph where every In Graph theory, the Dulmage-Mendelsohn decomposition is a method used to create a maximal Matching on a Bipartite graph. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic