7,129
个编辑
更改
跳到导航
跳到搜索
第45行：
第45行： − + − Often peripheral [[sparse matrix]] algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:+ − Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:+ − + − 通常周边稀疏矩阵算法需要一个高离心率的起始点。一个外围的顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，可以很容易地找到伪周边顶点:+ − − − − − − Choose a vertex <math>u</math>. − − − − − − Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal degree. − − − − − − If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex. − −
→Algorithm for finding pseudo-peripheral vertices 寻找伪周边的算法
<br>
<br>
==Algorithm for finding pseudo-peripheral vertices 寻找伪周边的算法==
==寻找伪周边的算法 Algorithm for finding pseudo-peripheral vertices ==
通常,外围[[稀疏矩阵 sparse matrix]]算法需要具有高离心率的起始点。外围顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，能轻松找到伪周边顶点:
# 选择顶点 <math>u</math>。
# 在所有尽可能远离<math>u</math>的顶点中，让<math>v</math>是一个最小度的顶点。
# 如果<math>\epsilon(v) > \epsilon(u)</math>，那么令 <math>u=v</math> 并重复步骤2，否则 <math>u</math>是一个伪周边顶点。
# Choose a vertex <math>u</math>.
选择顶点<math>u</math>。
# Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal [[degree (graph theory)|degree]].
在所有尽可能远离<math>u</math>的顶点中，令<math>v</math>是一个最小度的顶点。
# If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex.
如果<math>\epsilon(v) > \epsilon(u)</math>那么令 <math>u=v</math>并重复步骤2，否则 <math>u</math>是一个伪周边顶点。
==See also 另请参见==
==See also 另请参见==