更改

添加15字节 、 2020年9月24日 (四) 00:56
第70行: 第70行:  
The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm.  
 
The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm.  
   −
一个给定的度序列是否可以用一个简单的图进行表示,是一个具有挑战性的问题。这个问题也称为'''<font color="#ff8000">图实现 Graph Realization Problem</font>'''问题,可以用'''<font color="#ff8000">Erdős–Gallai定理 Erdős–Gallai Theoreme</font>'''解决,也可以用'''<font color="#ff8000">Havel-Hakimi算法 Havel–Hakimi Algorithm</font>'''解决。
+
“一个给定的度序列是否可以用一个简单的图进行表示”是一个具有挑战性的问题。这个问题也称为'''<font color="#ff8000">图实现 Graph Realization Problem</font>'''问题,但它可以用'''<font color="#ff8000">Erdős–Gallai定理 Erdős–Gallai Theoreme</font>'''解决,也可以用'''<font color="#ff8000">Havel-Hakimi算法 Havel–Hakimi Algorithm</font>'''解决。
    
The problem of finding or estimating the  number of graphs with a given degree sequence is a problem from the field of [[graph enumeration]].
 
The problem of finding or estimating the  number of graphs with a given degree sequence is a problem from the field of [[graph enumeration]].
第84行: 第84行:  
More generally, the degree sequence of a hypergraph is the non-increasing sequence of its vertex degrees. A sequence is <math>k</math>-graphic if it is the degree sequence of some <math>k</math>-uniform hypergraph. In particular, a <math>2</math>-graphic sequence is graphic. Deciding if a given sequence is <math>k</math>-graphic is doable in polynomial time for <math>k=2</math> via the Erdős–Gallai theorem but is NP-complete for all <math>k\ge 3</math> (Deza et al., 2018 ).
 
More generally, the degree sequence of a hypergraph is the non-increasing sequence of its vertex degrees. A sequence is <math>k</math>-graphic if it is the degree sequence of some <math>k</math>-uniform hypergraph. In particular, a <math>2</math>-graphic sequence is graphic. Deciding if a given sequence is <math>k</math>-graphic is doable in polynomial time for <math>k=2</math> via the Erdős–Gallai theorem but is NP-complete for all <math>k\ge 3</math> (Deza et al., 2018 ).
   −
一般来说,'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。一个序列是<math>k-graphic</math>,如果它是一些<math>k-uniform</math>超图的度序列。特别是<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过Erdős–Gallai定理实现,但是当<math>k\ge 3</math>时该问题可转化为'''<font color="#ff8000">NP完全问题 NP-complete</font>'''(Deza et al. ,2018)。
+
一般来说,'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。如果一个序列是<math>k-uniform</math>超图的度序列,那么它即是<math>k-graphic</math>。特别地,<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过Erdős–Gallai定理实现,但是当<math>k\ge 3</math>时该问题可转化为'''<font color="#ff8000">NP完全问题 NP-complete</font>'''(Deza et al. ,2018)。
    
==Special values==
 
==Special values==
526

个编辑