7,129
个编辑
更改
跳到导航
跳到搜索
第39行：
第39行： − +
→度序列
一般来说，'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。如果一个序列是<math>k-uniform</math>超图的度序列，那么它即是<math>k</math>-graphic。特别地，<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过'''<font color="#ff8000">Erdős–Gallai定理 Erdős–Gallai Theoreme</font>'''实现，但是当<math>k\ge 3</math>时该问题可转化为'''<font color="#ff8000">NP完全问题 NP-complete</font>'''。<ref>{{Cite journal|last=Deza|first=Antoine|last2=Levin|first2=Asaf|last3=Meesum|first3=Syed M.|last4=Onn|first4=Shmuel|date=January 2018|title=Optimization over Degree Sequences|url=https://epubs.siam.org/doi/10.1137/17M1134482|journal=SIAM Journal on Discrete Mathematics|language=en|volume=32|issue=3|pages=2067–2079|doi=10.1137/17M1134482|issn=0895-4801|arxiv=1706.03951}}</ref>
一般来说，'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。如果一个序列是<math>k</math>-uniform超图的度序列，那么它即是<math>k</math>-graphic。特别地，<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过'''<font color="#ff8000">Erdős–Gallai定理 Erdős–Gallai Theoreme</font>'''实现，但是当<math>k\ge 3</math>时该问题可转化为'''<font color="#ff8000">NP完全问题 NP-complete</font>'''。<ref>{{Cite journal|last=Deza|first=Antoine|last2=Levin|first2=Asaf|last3=Meesum|first3=Syed M.|last4=Onn|first4=Shmuel|date=January 2018|title=Optimization over Degree Sequences|url=https://epubs.siam.org/doi/10.1137/17M1134482|journal=SIAM Journal on Discrete Mathematics|language=en|volume=32|issue=3|pages=2067–2079|doi=10.1137/17M1134482|issn=0895-4801|arxiv=1706.03951}}</ref>
<br>
<br>