Bipartite graph

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Examples Bipartite graph_section_0

When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. Bipartite graph_sentence_0

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, is a natural example of an affiliation network, a type of bipartite graph used in social network analysis. Bipartite graph_sentence_1

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. Bipartite graph_sentence_2

This problem can be modeled as a dominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station. Bipartite graph_sentence_3

A third example is in the academic field of numismatics. Bipartite graph_sentence_4

Ancient coins are made using two positive impressions of the design (the obverse and reverse). Bipartite graph_sentence_5

The charts numismatists produce to represent the production of coins are bipartite graphs. Bipartite graph_sentence_6

More abstract examples include the following: Bipartite graph_sentence_7

Properties Bipartite graph_section_1

Characterization Bipartite graph_section_2

Bipartite graphs may be characterized in several different ways: Bipartite graph_sentence_8

Bipartite graph_unordered_list_0

  • A graph is bipartite if and only if it does not contain an odd cycle.Bipartite graph_item_0_0
  • A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).Bipartite graph_item_0_1
  • The spectrum of a graph is symmetric if and only if it's a bipartite graph.Bipartite graph_item_0_2

Kőnig's theorem and perfect graphs Bipartite graph_section_3

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem. Bipartite graph_sentence_9

An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. Bipartite graph_sentence_10

In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices. Bipartite graph_sentence_11

Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices. Bipartite graph_sentence_12

Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Bipartite graph_sentence_13

Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. Bipartite graph_sentence_14

This was one of the results that motivated the initial definition of perfect graphs. Bipartite graph_sentence_15

Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree. Bipartite graph_sentence_16

According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. Bipartite graph_sentence_17

The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem. Bipartite graph_sentence_18

Degree Bipartite graph_section_4

The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. Bipartite graph_sentence_19

(Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.) Bipartite graph_sentence_20

Relation to hypergraphs and directed graphs Bipartite graph_section_5

Algorithms Bipartite graph_section_6

Testing bipartiteness Bipartite graph_section_7

It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. Bipartite graph_sentence_21

The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. Bipartite graph_sentence_22

This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. Bipartite graph_sentence_23

In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. Bipartite graph_sentence_24

If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. Bipartite graph_sentence_25

However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite. Bipartite graph_sentence_26

Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Bipartite graph_sentence_27

Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. Bipartite graph_sentence_28

If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. Bipartite graph_sentence_29

If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite. Bipartite graph_sentence_30

Odd cycle transversal Bipartite graph_section_8

Main article: Odd cycle transversal Bipartite graph_sentence_31

Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite. Bipartite graph_sentence_32

The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k. The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Bipartite graph_sentence_33

Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. Bipartite graph_sentence_34

In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph. Bipartite graph_sentence_35

Matching Bipartite graph_section_9

Main article: Matching (graph theory) Bipartite graph_sentence_36

A matching in a graph is a subset of its edges, no two of which share an endpoint. Bipartite graph_sentence_37

Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage. Bipartite graph_sentence_38

In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs, and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching work correctly only on bipartite inputs. Bipartite graph_sentence_39

The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings. Bipartite graph_sentence_40

Additional applications Bipartite graph_section_10

Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Bipartite graph_sentence_41

Factor graphs and Tanner graphs are examples of this. Bipartite graph_sentence_42

A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors. Bipartite graph_sentence_43

A factor graph is a closely related belief network used for probabilistic decoding of LDPC and turbo codes. Bipartite graph_sentence_44

In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. Bipartite graph_sentence_45

A system is modeled 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. Bipartite graph_sentence_46

There are additional constraints on the nodes and edges that constrain the behavior of the system. Bipartite graph_sentence_47

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. Bipartite graph_sentence_48

In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. Bipartite graph_sentence_49

Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their girth must be six or more. Bipartite graph_sentence_50

See also Bipartite graph_section_11

Bipartite graph_unordered_list_1

  • Bipartite dimension, the minimum number of complete bipartite graphs whose union is the given graphBipartite graph_item_1_3
  • Bipartite double cover, a way of transforming any graph into a bipartite graph by doubling its verticesBipartite graph_item_1_4
  • Bipartite hypergraph, a generalization of bipartiteness to hypergraphs.Bipartite graph_item_1_5
  • Bipartite matroid, a class of matroids that includes the graphic matroids of bipartite graphsBipartite graph_item_1_6
  • Bipartite network projection, a weighting technique for compressing information about bipartite networksBipartite graph_item_1_7
  • Convex bipartite graph, a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguousBipartite graph_item_1_8
  • Multipartite graph, a generalization of bipartite graphs to more than two subsets of verticesBipartite graph_item_1_9
  • Parity graph, a generalization of bipartite graphs in which every two induced paths between the same two points have the same parityBipartite graph_item_1_10
  • Quasi-bipartite graph, a type of Steiner tree problem instance in which the terminals form an independent set, allowing approximation algorithms that generalize those for bipartite graphsBipartite graph_item_1_11
  • Split graph, a graph in which the vertices can be partitioned into two subsets, one of which is independent and the other of which is a cliqueBipartite graph_item_1_12
  • Zarankiewicz problem on the maximum number of edges in a bipartite graph with forbidden subgraphsBipartite graph_item_1_13

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: graph.