961
个编辑
更改
跳到导航
跳到搜索
第17行：
第17行： − 在图论的数学领域中，二部图(或称二部图)是一种图，它的顶点可以分为两个不相交的独立集合。顶点集 < math > u </math > 和 < math > v </math > 通常被称为图的部分。等价地，二部图是一个不包含任何奇数长度圈的图+ − | last1 = Asratian − | last1 = Asratian − 1 = Asratian+ − + − | first1 = Armen S.+ − 1 = Armen s. − | last2 = Denley − + − 2 = Denley+ − | first2 = Tristan M. J.+ − | 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== +
无编辑摘要
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
在图论的数学领域中，二分图（或二部图）内的所有顶点可以分为两个不相交且独立的集合U和集合V，并且每个连边（无向或有向）的两个顶点分别在集合U和集合V当中。通常集合U和集合V被称为该二分图的子集。同时，二分图中不包含任何形式的奇数环，即：集合U和集合V构造的点集所形成的循环圈边数不为奇数。
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.
通常可以将集合U和集合V视为被着色的两类图集：如果其中一类所有顶点为蓝色，另外一类为绿色，那么每条连边的两端必须具有不同的颜色。这是二分图中必须满足的条件。相反，在非二分图（例如三角形）的情况下，这种着色要求是不可能达到的：因为一个顶点为蓝色，另一个为绿色，其三角形剩下的第三个顶点将需要同时连接这两个颜色，很明显这是不可能达到的，因为它违背了要求：二分图中所有顶点必须分为两个不相交且独立的集合U和V。
| 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]].
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.
对于二分图常用的表达方式是G=(U,V,E)，其中U和V分别代表子集，E代表二分图中的连边。如果有一个二分图内部不是连通的，则它可能具有多个二分图；在这种情况下，(U,V,E)标注有助于指定一个特殊的二分图。在实际的应用当中，这无比重要。如果|U|=|V|，即这两个子集具有相同的基数，此时G被称为均衡二分图。如果在二分图中同一侧（同一个子集）所有的顶点都具有相同的度数，则G被称为双正则。
== 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