763
个编辑
更改
跳到导航
跳到搜索
第219行：
第219行： − + − Many [[theorem]]s and concepts involving graphs also hold for hypergraphs. [[Ramsey's theorem]] and [[Line graph of a hypergraph]] are typical examples. Some methods for studying symmetries of graphs extend to hypergraphs.+ − Two prominent theorems are the [[Erdős–Ko–Rado theorem]] and the [[Kruskal–Katona theorem]] on uniform hypergraphs. − − 许多涉及图的定理和概念也适用于超图，典型的例子有拉姆齐定理 Ramsey's theorem和超图的线图 Line graph of a hypergraph。一些研究图的对称性的方法也被扩展到超图。
→定理 Theorems
图划分(特别是超图划分)在集成电路设计 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> 和并行计算 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>中有很多应用。此外，在机器学习任务中，高效、可扩展的超图划分算法对于处理大规模超图也很重要。<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>
图划分(特别是超图划分)在集成电路设计 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> 和并行计算 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>中有很多应用。此外，在机器学习任务中，高效、可扩展的超图划分算法对于处理大规模超图也很重要。<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>
==定理 Theorems==
==定理==
许多涉及图的定理和概念也适用于超图，典型的例子有拉姆齐定理 Ramsey's theorem和超图的线图 Line graph of a hypergraph。一些研究图的对称性的方法也被扩展到超图。
一致超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。
一致超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。