第17行: |
第17行: |
| 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 <math>U</math> and <math>V</math> such that every edge connects a vertex in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.<ref>{{citation | | 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 <math>U</math> and <math>V</math> such that every edge connects a vertex in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.<ref>{{citation |
| | | |
− | 在图论的数学领域中,二部图(或称二部图)是一种图,它的顶点可以分为两个不相交的独立集合。顶点集 < math > u </math > 和 < math > v </math > 通常被称为图的部分。等价地,二部图是一个不包含任何奇数长度圈的图
| + | 在图论的数学领域中,二分图(或二部图)内的所有顶点可以分为两个不相交且独立的集合U和集合V,并且每个连边(无向或有向)的两个顶点分别在集合U和集合V当中。通常集合U和集合V被称为该二分图的子集。同时,二分图中不包含任何形式的奇数环,即:集合U和集合V构造的点集所形成的循环圈边数不为奇数。 |
| | | |
− | | last1 = Asratian
| |
| | | |
− | | last1 = Asratian
| |
| | | |
− | 1 = Asratian
| + | The two sets <math>U</math> and <math>V</math> may be thought of as a [[graph coloring|coloring]] of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="adh98-7"/><ref name="s12"> | year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a [[Gallery of named graphs|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. |
| | | |
− | | first1 = Armen S. | + | The two sets <math>U</math> and <math>V</math> may be thought of as a coloring of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="s12">{{citation | year = 2012}}.</ref> 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. |
| | | |
− | | first1 = Armen S.
| + | 通常可以将集合U和集合V视为被着色的两类图集:如果其中一类所有顶点为蓝色,另外一类为绿色,那么每条连边的两端必须具有不同的颜色。这是二分图中必须满足的条件。相反,在非二分图(例如三角形)的情况下,这种着色要求是不可能达到的:因为一个顶点为蓝色,另一个为绿色,其三角形剩下的第三个顶点将需要同时连接这两个颜色,很明显这是不可能达到的,因为它违背了要求:二分图中所有顶点必须分为两个不相交且独立的集合U和V。 |
| | | |
− | 1 = Armen s.
| |
| | | |
− | | last2 = Denley
| |
| | | |
− | | last2 = Denley | + | One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not [[connected graph|connected]], it may have more than one bipartition;<ref>{{citation | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal [[cardinality]], then <math>G</math> is called a ''balanced'' bipartite graph.<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> If all vertices on the same side of the bipartition have the same [[Degree (graph theory)|degree]], then <math>G</math> is called [[biregular graph|biregular]]. |
| | | |
− | 2 = Denley
| + | One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;<ref>{{citation | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal cardinality, then <math>G</math> is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then <math>G</math> is called biregular. |
| | | |
− | | first2 = Tristan M. J.
| + | 对于二分图常用的表达方式是G=(U,V,E),其中U和V分别代表子集,E代表二分图中的连边。如果有一个二分图内部不是连通的,则它可能具有多个二分图;在这种情况下,(U,V,E)标注有助于指定一个特殊的二分图。在实际的应用当中,这无比重要。如果|U|=|V|,即这两个子集具有相同的基数,此时G被称为均衡二分图。如果在二分图中同一侧(同一个子集)所有的顶点都具有相同的度数,则G被称为双正则。 |
| | | |
− | | first2 = Tristan M. J.
| |
− |
| |
− | 2 = Tristan m. j.
| |
− |
| |
− | | last3 = Häggkvist
| |
− |
| |
− | | last3 = Häggkvist
| |
− |
| |
− | | last3 = Häggkvist
| |
− |
| |
− | | first3 = Roland
| |
− |
| |
− | | first3 = Roland
| |
− |
| |
− | 3 = Roland
| |
− |
| |
− | | isbn = 9780521593458
| |
− |
| |
− | | isbn = 9780521593458
| |
− |
| |
− | 9780521593458
| |
− |
| |
− | | publisher = Cambridge University Press
| |
− |
| |
− | | publisher = Cambridge University Press
| |
− |
| |
− | 剑桥大学出版社
| |
− |
| |
− | | series = Cambridge Tracts in Mathematics
| |
− |
| |
− | | series = Cambridge Tracts in Mathematics
| |
− |
| |
− | | 系列 = 剑桥数学丛书
| |
− |
| |
− | | title = Bipartite Graphs and their Applications
| |
− |
| |
− | | title = Bipartite Graphs and their Applications
| |
− |
| |
− | | title = 二部图及其应用
| |
− |
| |
− | | volume = 131
| |
− |
| |
− | | volume = 131
| |
− |
| |
− | 131
| |
− |
| |
− | | year = 1998
| |
− |
| |
− | | year = 1998
| |
− |
| |
− | 1998年
| |
− |
| |
− | | url-access = registration
| |
− |
| |
− | | url-access = registration
| |
− |
| |
− | | url-access = registration
| |
− |
| |
− | | url = https://archive.org/details/bipartitegraphst0000asra
| |
− |
| |
− | | url = https://archive.org/details/bipartitegraphst0000asra
| |
− |
| |
− | Https://archive.org/details/bipartitegraphst0000asra
| |
− |
| |
− | }}.</ref>
| |
− |
| |
− | }}.</ref>
| |
− |
| |
− | } . </ref >
| |
− |
| |
− |
| |
− |
| |
− | The two sets <math>U</math> and <math>V</math> may be thought of as a [[graph coloring|coloring]] of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="adh98-7"/><ref name="s12">{{citation
| |
− |
| |
− | The two sets <math>U</math> and <math>V</math> may be thought of as a coloring of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="s12">{{citation
| |
− |
| |
− | 这两个集合 < math > u </math > 和 < math > v </math > 可以被看作是两种颜色的图的着色: 如果 < math > u </math > 蓝色中的所有节点都有一种颜色,而 < math > v </math > 绿色中的所有节点都有一种颜色,那么每个边的端点都有不同颜色的端点,就像图着色问题中所要求的那样。12"> { citation
| |
− |
| |
− | | last = Scheinerman | first = Edward R. | authorlink = Ed Scheinerman
| |
− |
| |
− | | last = Scheinerman | first = Edward R. | authorlink = Ed Scheinerman
| |
− |
| |
− | 作者: Ed Scheinerman | last = Scheinerman | first = Edward r | authorlink = Ed Scheinerman
| |
− |
| |
− | | edition = 3rd
| |
− |
| |
− | | edition = 3rd
| |
− |
| |
− | 3 rd
| |
− |
| |
− | | isbn = 9780840049421
| |
− |
| |
− | | isbn = 9780840049421
| |
− |
| |
− | 9780840049421
| |
− |
| |
− | | page = 363
| |
− |
| |
− | | page = 363
| |
− |
| |
− | 363
| |
− |
| |
− | | publisher = Cengage Learning
| |
− |
| |
− | | publisher = Cengage Learning
| |
− |
| |
− | 2012年3月24日 | publisher = 圣智学习出版公司
| |
− |
| |
− | | title = Mathematics: A Discrete Introduction
| |
− |
| |
− | | title = Mathematics: A Discrete Introduction
| |
− |
| |
− | | title = 数学: 离散介绍
| |
− |
| |
− | | url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
| |
− |
| |
− | | url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
| |
− |
| |
− | Https://books.google.com/books?id=dzbhgd2seywc&pg=pa363
| |
− |
| |
− | | year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a [[Gallery of named graphs|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.
| |
− |
| |
− | | year = 2012}}.</ref> 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.
| |
− |
| |
− | 2012}}.相比之下,对于非二部图,如三角形,这样的着色是不可能的: 在一个节点被着成蓝色和另一个绿色之后,三角形的第三个顶点连接到两种颜色的顶点上,这样就不能给它分配任何一种颜色。
| |
− |
| |
− |
| |
− |
| |
− | One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not [[connected graph|connected]], it may have more than one bipartition;<ref>{{citation
| |
− |
| |
− | One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;<ref>{{citation
| |
− |
| |
− | 人们经常用 < math > g = (u,v,e) </math > 来表示一个二部图,其分区由 < math > u </math > 和 < math > v </math > 组成,用 < math > e </math > 表示图的边。如果一个二部图是不连通的,它可能有一个以上的二部图
| |
− |
| |
− | | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| |
− |
| |
− | | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| |
− |
| |
− | 1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| |
− |
| |
− | | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
| |
− |
| |
− | | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
| |
− |
| |
− | | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (图论学家)
| |
− |
| |
− | | isbn = 9781584888000
| |
− |
| |
− | | isbn = 9781584888000
| |
− |
| |
− | 9781584888000
| |
− |
| |
− | | page = 223
| |
− |
| |
− | | page = 223
| |
− |
| |
− | 223
| |
− |
| |
− | | publisher = CRC Press
| |
− |
| |
− | | publisher = CRC Press
| |
− |
| |
− | | publisher = CRC Press
| |
− |
| |
− | | series = Discrete Mathematics And Its Applications
| |
− |
| |
− | | series = Discrete Mathematics And Its Applications
| |
− |
| |
− | 系列 = 离散数学及其应用
| |
− |
| |
− | | title = Chromatic Graph Theory
| |
− |
| |
− | | title = Chromatic Graph Theory
| |
− |
| |
− | 彩色图论
| |
− |
| |
− | | url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
| |
− |
| |
− | | url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
| |
− |
| |
− | Https://books.google.com/books?id=_l4cjq46mxwc&pg=pa223
| |
− |
| |
− | | volume = 53
| |
− |
| |
− | | volume = 53
| |
− |
| |
− | 53
| |
− |
| |
− | | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal [[cardinality]], then <math>G</math> is called a ''balanced'' bipartite graph.<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> If all vertices on the same side of the bipartition have the same [[Degree (graph theory)|degree]], then <math>G</math> is called [[biregular graph|biregular]].
| |
− |
| |
− | | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal cardinality, then <math>G</math> is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then <math>G</math> is called biregular.
| |
− |
| |
− | 2008}}.在这种情况下,< math > (u,v,e) </math > 符号有助于指定一个特定的双分区,这个双分区在应用程序中可能非常重要。如果 < math > | u | = | v | </math > ,也就是说,如果两个子集具有相等的基数,那么 < math > g </math > 被称为平衡二部图。如果二分区同一侧的所有顶点都具有相同的度数,那么 < math > g </math > 称为二正则。
| |
− |
| |
− |
| |
− |
| |
− | ==Examples==
| |
| | | |
| | | |
| + | == Examples == |
| | | |
| 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]].<ref>{{citation | | 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]].<ref>{{citation |