526
个编辑
更改
→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]
自觉选用二分图的另一个例子是（NP-完全问题）铁路优化问题，其中输入项是火车的时间表及其停靠点，目标是找到尽可能小的火车站集合，以便每个火车都可以停靠至少一个选定的火车站。我们可以运用建模将这个问题转化为一个二分图中的主导集合问题，该图中每辆列车和每个车站都被看作是一个顶点，而当某列车停靠在某车站的时候，它们所形成的关系可看作一条连边。
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.
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.
第三个例子涉及到货币金融学领域。古代的硬币被设计为正反两面，不同时期和地区的政府会使用不同的正反面组合，因此，将所有可能的组合画成图就是一个二分图的结构。
* Every [[tree (graph theory)|tree]] is bipartite.<ref name="s12"/>
* Every [[tree (graph theory)|tree]] is bipartite.<ref name="s12"/>
* 每棵树都是二分的。
* 每个树状图都是二分的。
* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite. Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite. Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
* 平面图（图论）中，所有面都具有偶数条边，该图为二分图。特殊情况是网格图和方图，其中每个内面都有4个边，每个内顶点都有4个或更多的相邻点。
* 在平面图（图论）中，所有面都具有偶数条边，该图为二分图。特殊情况是网格图和方图，其中每个内面都有4个边，每个内顶点至少有4个相邻点。