更改

二分图 (查看源代码)

2021年11月2日 (二) 21:08的版本

删除741字节、 2021年11月2日 (二) 21:08

→‎案例

第15行：第15行：

== 案例 ==

−

When modelling [[heterogeneous relation|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.

−

在建立两类不同对象之间的关系时，人们常常会很自然地选择二分图。以建立足球运动员和俱乐部的关系图为例，如果该球员曾为该俱乐部效力，那么在运动员和俱乐部之间就形成了一条边。这是二分图在建立隶属关系网络中的应用示例。在社交网络分析中，隶属关系便形成一种二分图。<ref>{{citation | last1 = Wasserman | first1 = Stanley | last2 = Faust | first2 = Katherine | isbn = 9780521387071 | pages = 299–302 | publisher = Cambridge University Press

| series = Structural Analysis in the Social Sciences | title = Social Network Analysis: Methods and Applications | url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299 | volume = 8 | year = 1994}}.</ref>

第38行：第33行：

* ''' 超立方体图 Hypercube graph'''，''' 局部立方体 Partial cube'''和''' 中位数图 Median graph'''均为二分图。判别方法是将这些图中的顶点用''' 位向量Bitvector'''（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树状图和方图都是中位数图，而所有中位数图都是局部立方体。<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.</ref>

+

<br>

== 属性 ==

薄荷

7,129

个编辑