更改

删除2,518字节 、 2020年4月23日 (四) 10:08
第202行: 第202行:  
经典超图着色有许多推广。在允许单色边情况下,混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时,其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。
 
经典超图着色有许多推广。在允许单色边情况下,混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时,其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。
   −
==划分 Partitions==
+
===划分===
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]]
+
由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>的秩。
 
  −
:<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>的秩。
      
作为推论,不是点传递的边传递超图则是2可着色的。
 
作为推论,不是点传递的边传递超图则是2可着色的。
  −
  −
[[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>
       
763

个编辑