# 二分图

m=5和n=3的完全二分图示例
 --趣木木（讨论）注意图的格式规范  查看之前发的表/链接页面 已改


In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $\displaystyle{ U }$ and $\displaystyle{ V }$ such that every edge connects a vertex in $\displaystyle{ U }$ to one in $\displaystyle{ V }$. Vertex sets $\displaystyle{ U }$ and $\displaystyle{ V }$ are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length。

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets {\displaystyle U}U and {\displaystyle V}V such that every edge connects a vertex in {\displaystyle U}U to one in {\displaystyle V}V. Vertex sets {\displaystyle U}U and {\displaystyle V}V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]

 --趣木木（讨论）变量斜体 已修改


The two sets $\displaystyle{ U }$ and $\displaystyle{ V }$ may be thought of as a coloring of the graph with two colors: if one colors all nodes in $\displaystyle{ U }$ blue, and all nodes in $\displaystyle{ V }$ green, each edge has endpoints of differing colors, as is required in the graph coloring problem.[1][2] In contrast, such a coloring is impossible in the case of a non-bipartite 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.

The two sets $\displaystyle{ U }$ and $\displaystyle{ V }$ may be thought of as a coloring of the graph with two colors: if one colors all nodes in $\displaystyle{ U }$ blue, and all nodes in $\displaystyle{ V }$ green, each edge has endpoints of differing colors, as is required in the graph coloring problem.[2] In contrast, such a coloring is impossible in the case of a non-bipartite 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.

One often writes $\displaystyle{ G=(U,V,E) }$ to denote a bipartite graph whose partition has the parts $\displaystyle{ U }$ and $\displaystyle{ V }$, with $\displaystyle{ E }$ denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;[3] in this case, the $\displaystyle{ (U,V,E) }$ notation is helpful in specifying one particular bipartition that may be of importance in an application. If $\displaystyle{ |U|=|V| }$, that is, if the two subsets have equal cardinality, then $\displaystyle{ G }$ is called a balanced bipartite graph.[1] If all vertices on the same side of the bipartition have the same degree, then $\displaystyle{ G }$ is called biregular.

One often writes $\displaystyle{ G=(U,V,E) }$ to denote a bipartite graph whose partition has the parts $\displaystyle{ U }$ and $\displaystyle{ V }$, with $\displaystyle{ E }$ denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;[4] in this case, the $\displaystyle{ (U,V,E) }$ notation is helpful in specifying one particular bipartition that may be of importance in an application. If $\displaystyle{ |U|=|V| }$, that is, if the two subsets have equal cardinality, then $\displaystyle{ G }$ is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then $\displaystyle{ G }$ is called biregular.

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

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

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. 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.[7]

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. 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.[7]

A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.[5]

A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.

More abstract examples include the following:

More abstract examples include the following:

• Every tree is bipartite.[2]
• 每个树状图都是二分的。

• Cycle graphs with an even number of vertices are bipartite.[2]
• 具有偶数个顶点的环图都是二分的

• Every planar graph whose faces all have even length is bipartite. Special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
• 在平面图中，所有面都具有偶数条边，该图为二分图。特殊情况是网格图和方图，其中每个内面都有4个边，每个内顶点至少有4个相邻点。

• The complete bipartite graph on m and n vertices, denoted by Kn,m is the bipartite graph $\displaystyle{ G = (U, V, E) }$, where U and V are disjoint sets of size m and n, respectively, and E connects every vertex in U with all vertices in V. It follows that Km,n has mn edges.
• 在一个完全二分图中，分别由mn的顶点（用Km,n表示）组成的两个不相交的集合UV，连边E由分别在集合UV的两个顶点连接。该二分图表示为G =（U，V，E），并且具有mn条边。另外完全二分图还有一个特例，那就是 冠图Crown graphs。冠图是将一个完全二分图中所有的完美匹配连边去掉后形成的。

• Hypercube graphs, partial cubes, and median graphs are bipartite. In these graphs, the vertices may be labeled by bitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.
• 超立方体图Hypercube graph 局部立方体Partial cube 中位数图Median graph均为二分图。判别方法是将这些图中的顶点用 位向量Bitvector（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树状图和方图都是中位数图，而所有中位数图都是局部立方体。

## Properties 属性

### Characterization 特征表述

Bipartite graphs may be characterized in several different ways:

Bipartite graphs may be characterized in several different ways:

• A graph is bipartite if and only if it does not contain an odd cycle. Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig. For infinite graphs, this result requires the axiom of choice.
• 当且仅当它不包含奇数环的时候，该图为二分图。（定理 2.1.3，p.8.Asratian 等人将这种描述归因于 Dénes Kőnig 的 1916 年论文。对于无限图，这个结果需要 公理选择。）

• A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).
• 当且仅当图是2色系图2-colorable（即，其色数小于或等于2，详见“图着色”）时，该图为二分图。
• The spectrum of a graph is symmetric if and only if it's a bipartite graph.
• 当且仅当它是二分图时，图的频谱是对称的。

### Kőnig's theorem and perfect graphs 柯尼希定理和完美图

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[16][17] 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. 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.[18] 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.

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[16][17] 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. 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.[18] 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.

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. 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. This was one of the results that motivated the initial definition of perfect graphs.

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. 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. This was one of the results that motivated the initial definition of perfect graphs.

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

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

### Degree 度相关问题

For a vertex, the number of adjacent vertices is called the degree of the vertex and is denoted $\displaystyle{ \deg(v) }$.

For a vertex, the number of adjacent vertices is called the degree of the vertex and is denoted $\displaystyle{ \deg(v) }$.

{\displaystyle \sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|\,.}\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts $\displaystyle{ U }$ and $\displaystyle{ V }$. For example, the complete bipartite graph K3,5 has degree sequence $\displaystyle{ (5,5,5),(3,3,3,3,3) }$. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts $\displaystyle{ U }$ and $\displaystyle{ V }$. For example, the complete bipartite graph K3,5 has degree sequence $\displaystyle{ (5,5,5),(3,3,3,3,3) }$. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.

The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)

The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)

 --趣木木（讨论）注意全文是否大写专业名词的首字母  已修改


### Relation to hypergraphs and directed graphs 与超图和有向图的关系

The biadjacency matrix of a bipartite graph $\displaystyle{ (U,V,E) }$ is a (0,1) matrix of size $\displaystyle{ |U|\times|V| }$ that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.[6] Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

The biadjacency matrix of a bipartite graph $\displaystyle{ (U,V,E) }$ is a (0,1) matrix of size $\displaystyle{ |U|\times|V| }$ that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph $\displaystyle{ (U,V,E) }$ may be used to model a hypergraph in which U is the set of vertices of the hypergraph, V is the set of hyperedges, and E contains an edge from a hypergraph vertex v to a hypergraph edge e exactly when v is one of the endpoints of e. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.[7]

A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph $\displaystyle{ (U,V,E) }$ may be used to model a hypergraph in which is the set of vertices of the hypergraph, is the set of hyperedges, and contains an edge from a hypergraph vertex to a hypergraph edge exactly when is one of the endpoints of . Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with n vertices can be any (0,1) matrix of size $\displaystyle{ n\times n }$, which can then be reinterpreted as the adjacency matrix of a bipartite graph with n vertices on each side of its bipartition.

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with vertices can be any (0,1) matrix of size $\displaystyle{ n\times n }$, which can then be reinterpreted as the adjacency matrix of a bipartite graph with vertices on each side of its bipartition.

## Algorithms 算法

### Testing bipartiteness 二分性测试

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

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

Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. 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. 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.

Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. 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. 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.

For the intersection graphs of $\displaystyle{ n }$ line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time $\displaystyle{ O(n\log n) }$, even though the graph itself may have up to $\displaystyle{ O(n^2) }$ edges.

For the intersection graphs of $\displaystyle{ n }$ line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time $\displaystyle{ O(n\log n) }$, even though the graph itself may have up to $\displaystyle{ O(n^2) }$ edges.

### Odd cycle transversal 奇环横贯

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.[27] 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.[28] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. 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. 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.

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.[27] 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.[28] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. 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. 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.

The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also fixed-parameter tractable, and can be solved in time, where k is the number of edges to delete and m is the number of edges in the input graph.

The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also fixed-parameter tractable, and can be solved in time, where k is the number of edges to delete and m is the number of edges in the input graph.

### Matching 匹配

A matching in a graph is a subset of its edges, no two of which share an endpoint. 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.In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[31] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[32] work correctly only on bipartite inputs.

A matching in a graph is a subset of its edges, no two of which share an endpoint. 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.In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[31] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[32] work correctly only on bipartite inputs.

As a simple example, suppose that a set $\displaystyle{ P }$ of people are all seeking jobs from among a set of $\displaystyle{ J }$ jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph $\displaystyle{ (P,J,E) }$ where an edge connects each job-seeker with each suitable job.[8] A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.

As a simple example, suppose that a set $\displaystyle{ P }$ of people are all seeking jobs from among a set of $\displaystyle{ J }$ jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph $\displaystyle{ (P,J,E) }$ where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.

The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.[9]

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

Dulmage–Mendelsohn 分解是二分图的结构分解，可用于寻找最大匹配。

Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. 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 graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. 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.

In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. 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. 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 computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. 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. 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. 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.

In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. 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 dimension, the minimum number of complete bipartite graphs whose union is the given graph
• 二分维度，联合给定图的完全二分图最小量
• Bipartite double cover, a way of transforming any graph into a bipartite graph by doubling its vertices
• 二分双重覆盖，一种通过双重复制顶点使原图形成两个不相交的副本从而将任意图转变为二分图的方法。
• Bipartite matroid, a class of matroids that includes the graphic matroids of bipartite graphs
• 二部拟阵，包括二分图的图形拟阵，属于拟阵的一类。
• Bipartite network projection, a weighting technique for compressing information about bipartite networks
• 二分图投影，一种用于压缩有关双向网络信息的加权技术
• Convex bipartite graph, a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguous
• 凸双枝图，二分图的一种，其顶点可以排序使得相邻顶点是连续的
• Multipartite graph, a generalization of bipartite graphs to more than two subsets of vertices
• 多重图，将二分图延伸到两个以上的顶点子集。
• Parity graph, a generalization of bipartite graphs in which every two induced paths between the same two points have the same parity
• 奇偶性图，具有二分图特性，同时同一点之间的每两个诱导路径具有相同的奇偶性
• 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 graphs
• 准二分图，一种斯坦纳树形Steiner tree问题实例，其中的终端形成一个独立的集合，从而允许近似算法将二分图的规范化
• 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 clique
• 分割图，图中顶点可以分为两个子集，其中一个子集是独立的，另一个成为团。
• Zarankiewicz problem on the maximum number of edges in a bipartite graph with forbidden subgraphs
• Zarankiewicz 问题，关于禁止子图二分图的最大边数问题。

## References 参考文献

1. 脚本错误：没有“Footnotes”这个模块。, p. 7.
2. | year = 2012}}. 引用错误：无效<ref>标签；name属性“s12”使用不同内容定义了多次
3. , 2008 Missing or empty |title= (help).
4. , 2008 Missing or empty |title= (help).
5. Bracey, Robert (2012). "On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins". pp. 65–84.
6. 脚本错误：没有“Footnotes”这个模块。, p. 17.
7. 模板:SpringerEOM
8. 脚本错误：没有“Footnotes”这个模块。, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.
9. 脚本错误：没有“Footnotes”这个模块。.

• 模板:Springer
• 《图，二分图》，Encyclopedia of Mathematics, EMS Press, 2001 [1994]

Category:Graph families

Category:Parity (mathematics)

This page was moved from wikipedia:en:Bipartite graph. Its edit history can be viewed at 二分图/edithistory