| 第193行： |
第193行： |
| | 对于<math>v^*_j \in V^*</math> 和 <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> 当且仅当 <math>a_{ij} = 1</math>。 | | 对于<math>v^*_j \in V^*</math> 和 <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> 当且仅当 <math>a_{ij} = 1</math>。 |
| | | | |
| − | ==超图着色 Hypergraph coloring== | + | ===超图着色=== |
| − | Classic hypergraph coloring is assigning one of the colors from set <math>\{1,2,3,...\lambda\}</math> to every vertex of a hypergraph in such a way that each hyperedge contains at least two vertices of distinct colors. In other words, there must be no monochromatic hyperedge with cardinality at least 2. In this sense it is a direct generalization of graph coloring. Minimum number of used distinct colors over all colorings is called the chromatic number of a hypergraph.
| + | 经典超图着色是将集合<math>\{1,2,3,...\lambda\}</math>中的其中一种颜色赋予给超图的每个顶点，使每个超边至少包含两个不同颜色的顶点。换句话说，不能存在基数至少为2的单色超边。从此意义上出发，它是广义图着色的直接推广。在所有着色行为中，使用到最小的不同颜色数称为超图的色数。 |
| | | | |
| − | 经典超图着色是将集合<math>\{1,2,3,...\lambda\}</math>中的其中一种颜色赋予给超图的每个顶点，使每个超边至少包含两个不同颜色的顶点。换句话说，不能存在基数至少为2的单色超边。从此意义上出发，它是广义图着色的直接推广。在所有着色行为中，使用到最小的不同颜色数称为超图的色数。
| |
| | | | |
| − | Hypergraphs for which there exists a coloring using up to ''k'' colors are referred to as ''k-colorable''. The 2-colorable hypergraphs are exactly the bipartite ones.
| |
| | 存在着使用多达<math>k </math>种颜色着色的超图称为'''k- 可着色图'''。2-可着色超图就是二分图。 | | 存在着使用多达<math>k </math>种颜色着色的超图称为'''k- 可着色图'''。2-可着色超图就是二分图。 |
| | | | |
| − | There are many generalizations of classic hypergraph coloring. One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed. Some mixed hypergraphs are uncolorable for any number of colors. A general criterion for uncolorability is unknown. When a mixed hypergraph is colorable, then the minimum and maximum number of used colors are called the lower and upper chromatic numbers respectively. See http://spectrum.troy.edu/voloshin/mh.html for details.
| |
| | | | |
| | 经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。 | | 经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。 |