763
个编辑
更改
跳到导航
跳到搜索
第202行：
第202行： − + − A partition theorem due to E. Dauber<ref>E. Dauber, in ''Graph theory'', ed. F. Harary, Addison Wesley, (1969) p. 172.</ref> states that, for an edge-transitive hypergraph <math>H=(X,E)</math>, there exists a [[partition of a set|partition]]+ − − :<math>(X_1, X_2,\cdots,X_K)</math> − − of the vertex set <math>X</math> such that the subhypergraph <math>H_{X_k}</math> generated by <math>X_k</math> is transitive for each <math>1\le k \le K</math>, and such that − − :<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math> − − where <math>r(H)</math> is the rank of ''H''. − − As a corollary, an edge-transitive hypergraph that is not vertex-transitive is bicolorable. − − 由E. Dauber<ref>E. Dauber, in ''Graph theory'', ed. F. Harary, Addison Wesley, (1969) p. 172.</ref>所提出的一个定理表明，对于边传递超图 <math>H=(X,E)</math>存在一个'''划分 partition'''：<math>(X_1, X_2,\cdots,X_K)</math>对于顶点集 <math>X</math>使得由<math>X_k</math>生成的子超图<math>H_{X_k}</math>在<math>1\le k \le K</math>时是可传递的，并且使得<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math>，其中<math>r(H)</math>是 <math>H</math>的秩。 − − − [[Graph partitioning]] (and in particular, hypergraph partitioning) has many applications to IC design<ref>{{Citation |title=Multilevel hypergraph partitioning: applications in VLSI domain |author=Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |date=March 1999 |volume=7 |issue=1 |pages=69–79 |doi=10.1109/92.748202 |postscript=.|citeseerx=10.1.1.553.2367 }}</ref> and parallel computing.<ref>{{Citation |doi=10.1016/S0167-8191(00)00048-X |title=Graph partitioning models for parallel computing |author= Hendrickson, B., Kolda, T.G. |journal=Parallel Computing | year=2000 |volume=26 |issue=12 |pages=1519–1545 |postscript=.|url=https://digital.library.unt.edu/ark:/67531/metadc684945/ |type=Submitted manuscript }}</ref><ref>{{Cite conference |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=A Hypergraph Model for Mapping Repeated Sparse Matrix-Vector Product Computations onto Multicomputers |conference=Proc. International Conference on Hi Performance Computing (HiPC'95) |year=1995}}</ref><ref>{{Citation |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication |journal=IEEE Transactions on Parallel and Distributed Systems |volume=10 |issue=7 |pages=673–693 |year=1999|doi=10.1109/71.780863 |postscript=. |citeseerx=10.1.1.67.2498 }}</ref> Efficient and Scalable [[Graph partition|hypergraph partitioning algorithms]] are also important for processing large scale hypergraphs in machine learning tasks.<ref name=hyperx>{{citation|last1=Huang|first1=Jin|last2=Zhang|first2=Rui|last3=Yu|first3=Jeffrey Xu|journal=Proceedings of the IEEE International Conference on Data Mining|title=Scalable Hypergraph Learning and Processing|year=2015}}</ref>
→划分 Partitions
经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。
经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。
==划分 Partitions==
===划分===
由E. Dauber<ref>E. Dauber, in ''Graph theory'', ed. F. Harary, Addison Wesley, (1969) p. 172.</ref>所提出的一个定理表明，对于边传递超图 <math>H=(X,E)</math>存在一个'''划分 partition'''：<math>(X_1, X_2,\cdots,X_K)</math>对于顶点集 <math>X</math>使得由<math>X_k</math>生成的子超图<math>H_{X_k}</math>在<math>1\le k \le K</math>时是可传递的，并且使得<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math>，其中<math>r(H)</math>是 <math>H</math>的秩。
作为推论，不是点传递的边传递超图则是2可着色的。
作为推论，不是点传递的边传递超图则是2可着色的。