更改

The biadjacency matrix of a bipartite graph <math>(U,V,E)</math> is a (0,1) matrix of size <math>|U|\times|V|</math> 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.

The biadjacency matrix of a bipartite graph <math>(U,V,E)</math> is a (0,1) matrix of size <math>|U|\times|V|</math> 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.

一个二分图（U，V，E）的双邻矩阵是大小为|V| 的（0,1）矩阵，其分别代表了每对相邻顶点集合和非相邻顶点的集合（全零矩阵）。双邻接矩阵可用于描述二分图，超图和定向图之间的等价关系。

一个二分图''（U，V，E）''的双邻矩阵是大小为|''V''| 的（0,1）矩阵，其分别代表了每对相邻顶点集合和非相邻顶点的集合（全零矩阵）。双邻接矩阵可用于描述二分图，超图和定向图之间的等价关系。

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 <math>(U,V,E)</math> 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 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 <math>(U,V,E)</math> 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.

超图是一种组合结构，类似于无向图，它具有顶点和连边，但是其中的边可以是任意子集组的顶点，而不必具有两个端点。可以使用二分图（U，V，E）来建模超图，其中U是超图的其中一个顶点集，V是该超图的连边集（称为超边集），E包含的连边定义为：从一个超图顶点v到超图连边e恰好当v是e的端点集之一时。在这种对应关系下，二分图的双邻矩阵正好是其相应超图的关联矩阵。作为二分图和超图之间这种对应关系的特例，任何'''<font color="#ff8000"> 多重图Multigraph</font>'''（即在相同两点之间可能存在的多条边的图）都可以解释为其中一些超边具有相同端点集的超图，并且由不具有多个邻接关系的二分图表示，其中二分图的同边顶点的度均为2。

超图是一种组合结构，类似于无向图，它具有顶点和连边，但是其中的边可以是任意子集组的顶点，而不必具有两个端点。可以使用二分图''（U，V，E）''来建模超图，其中''U''是超图的其中一个顶点集，''V''是该超图的连边集（称为超边集），''E''包含的连边定义为：从一个超图顶点''v''到超图连边''e''恰好当''v''是''e''的端点集之一时。在这种对应关系下，二分图的双邻矩阵正好是其相应超图的关联矩阵。作为二分图和超图之间这种对应关系的特例，任何'''<font color="#ff8000"> 多重图Multigraph</font>'''（即在相同两点之间可能存在的多条边的图）都可以解释为其中一些超边具有相同端点集的超图，并且由不具有多个邻接关系的二分图表示，其中二分图的同边顶点的度均为2。

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 <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with  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 <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with  vertices on each side of its bipartition.

关于'''<font color="#ff8000"> 邻接矩阵adjacency matrices</font>'''的另一个相似解释可以被用于展示有向图和均衡二分图（二分子集顶点数相等）之间的一一对应关系（在给定数量的标记顶点上，允许自循环）。例如，具有n个顶点的有向图的邻接矩阵可以是大小为nxn的任何（0,1）矩阵，然后可以将其重新解释为：具有相同顶点数n的同边子集的二分图的邻接矩阵。通过这种构建方式，二分图可以被解释为是一个有向图的'''<font color="#ff8000"> 二分双重覆盖bipartite double cover</font>'''。

关于'''<font color="#ff8000"> 邻接矩阵adjacency matrices</font>'''的另一个相似解释可以被用于展示有向图和均衡二分图（二分子集顶点数相等）之间的一一对应关系（在给定数量的标记顶点上，允许自循环）。例如，具有''n''个顶点的有向图的邻接矩阵可以是大小为''n''×''n''的任何（0,1）矩阵，然后可以将其重新解释为：具有相同顶点数n的同边子集的二分图的邻接矩阵。通过这种构建方式，二分图可以被解释为是一个有向图的'''<font color="#ff8000"> 二分双重覆盖bipartite double cover</font>'''。

 

== Algorithms 算法 ==

== Algorithms 算法 ==