更改

跳到导航 跳到搜索
添加157字节 、 2020年9月6日 (日) 17:50
第180行: 第180行:  
If edges, <math>M</math> in a random graph, <math>G_M</math> is large enough to ensure that almost every <math>G_M</math> has minimum degree at least 1, then almost every <math>G_M</math> is connected and, if <math>n</math> is even, almost every <math>G_M</math> has a perfect matching. In particular, the moment the last isolated vertex vanishes in almost every random graph, the graph becomes connected.
 
If edges, <math>M</math> in a random graph, <math>G_M</math> is large enough to ensure that almost every <math>G_M</math> has minimum degree at least 1, then almost every <math>G_M</math> is connected and, if <math>n</math> is even, almost every <math>G_M</math> has a perfect matching. In particular, the moment the last isolated vertex vanishes in almost every random graph, the graph becomes connected.
   −
如果随机图中的边 <math>M</math>,<math>G_M</math> 足够大以确保几乎每个 <math>G_M</math> 的最小阶数至少为1,那么几乎每个 <math>G</math> 是连通的,如果 <math>n</math> 是偶数,则几乎每个 <math>G_M</math> 都有一个完美的匹配。特别是,在几乎每个随机图中,最后一个孤立点消失的那一刻,图成为连通的。
+
如果随机图中的边 <math>M</math>,<math>G_M</math> 足够大以确保几乎每个 <math>G_M</math> 的最小阶数至少为1,那么几乎每个 <math>G</math> 是连通的,如果 <math>n</math> 是偶数,则几乎每个 <math>G_M</math> 都有一个'''<font color="#FF8000">完美匹配 Perfect Matching </font>'''。特别是,在几乎每个随机图中,最后一个孤立点消失的那一刻,图会变连通。
      第188行: 第188行:  
Almost every graph process on an even number of vertices with the edge raising the minimum degree to 1 or a random graph with slightly more than <math>\tfrac{n}{4}\log(n)</math> edges and with probability close to 1 ensures that the graph has a complete matching, with exception of at most one vertex.
 
Almost every graph process on an even number of vertices with the edge raising the minimum degree to 1 or a random graph with slightly more than <math>\tfrac{n}{4}\log(n)</math> edges and with probability close to 1 ensures that the graph has a complete matching, with exception of at most one vertex.
   −
几乎每个偶数顶点上的最小度提高到1的图或稍大于 <math>\tfrac{n}{4}\log(n)</math> 边且概率接近1的随机图都能确保图有完全匹配,但最多只有一个顶点。
+
几乎每个偶数顶点上的最小度提高到1的图或稍大于 <math>\tfrac{n}{4}\log(n)</math> 边且概率接近1的随机图都能确保图有'''<font color="#FF8000">完全匹配 Complete Matching </font>''',但最多只有一个顶点。
      第196行: 第196行:  
For some constant <math>c</math>, almost every labeled graph with <math>n</math> vertices and at least <math>cn\log(n)</math> edges is Hamiltonian. With the probability tending to 1, the particular edge that increases the minimum degree to 2 makes the graph Hamiltonian.
 
For some constant <math>c</math>, almost every labeled graph with <math>n</math> vertices and at least <math>cn\log(n)</math> edges is Hamiltonian. With the probability tending to 1, the particular edge that increases the minimum degree to 2 makes the graph Hamiltonian.
   −
对于某些常数 c </math > ,几乎所有带有 < math > n </math > 顶点和至少 < math > cn log (n) </math > 边的标记图都是 Hamiltonian 的。在概率趋于1的情况下,将最小度增加到2的特殊边使图具有哈密顿性。
+
对于某些常数 <math>c</math> ,几乎所有带有 <math>n</math> 顶点和至少 <math>cn\log(n)</math> 边的标记图都是 '''<font color="#FF8000">哈密尔顿环 Hamiltonian Cycle </font>'''的。在概率趋于1的情况下,将最小度增加到2的特殊边会使图成为哈密尔顿图。
     
274

个编辑

导航菜单