更改

图距离 (查看源代码)

2020年10月30日 (五) 16:08的版本

删除1,224字节、 2020年10月30日 (五) 16:08

→‎Algorithm for finding pseudo-peripheral vertices 寻找伪周边的算法

第45行：第45行：

<br>

−

==Algorithm for finding pseudo-peripheral vertices ~~寻找伪周边的算法~~==

+

==寻找伪周边的算法 Algorithm for finding pseudo-peripheral vertices ==

−

~~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:

+

通常,外围[[稀疏矩阵 sparse matrix]]算法需要具有高离心率的起始点。外围顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，能轻松找到伪周边顶点:

−

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:

+

# 选择顶点 <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>.~~

−

~~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]].~~

−

~~Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal 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.~~

−

~~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 另请参见==

薄荷

7,129

个编辑