7,129
个编辑
更改
跳到导航
跳到搜索
第13行：
第13行： − A [[metric space]] defined over a set of points in terms of distances in a graph defined over the set is called a '''graph metric'''.+ − A metric space defined over a set of points in terms of distances in a graph defined over the set is called a graph metric. − 定义在一组点上的度量空间,是 − 根据在该集合上定义的图上的距离定义的，称为图度量。 − 根据'''<font color="#ff8000">[[度量空间 metric space]]</font>'''定义，+ − 在一个由集合组成的图中，集合内点上的度量空间距离被称为'''<font color="#ff8000">图度量 Graph Metric</font>'''。 − − The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is [[connected (graph theory)|connected]]. − − 当且仅当图是连通的时，(无向图的)顶点集和距离函数构成度量空间。 第40行：
第32行： − + − − − − A '''pseudo-peripheral vertex''' <math>v</math> has the property that for any vertex <math>u</math>, if <math>v</math> is as far away from <math>u</math> as possible, then <math>u</math> is as far away from <math>v</math> as possible. Formally, a vertex ''u'' is pseudo-peripheral, − − A pseudo-peripheral vertex <math>v</math> has the property that for any vertex <math>u</math>, if <math>v</math> is as far away from <math>u</math> as possible, then <math>u</math> is as far away from <math>v</math> as possible. Formally, a vertex u is pseudo-peripheral, − − '''<font color="#ff8000">伪周边顶点 Pseudo-Peripheral Vertex</font>''' <math>v</math>具有这样的属性：对于任何顶点 <math>u</math>，如果<math>v</math>距离<math>u</math>越远，那么 <math>u</math>距离 <math>v</math>越远。即，一个顶点''u''是伪周边顶点,如果对于每个顶点''v''都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>。 − − if for each vertex ''v'' with <math>d(u,v) = \epsilon(u)</math> holds <math>\epsilon(u)=\epsilon(v)</math>. − − if for each vertex v with <math>d(u,v) = \epsilon(u)</math> holds <math>\epsilon(u)=\epsilon(v)</math>. − − − − − − The [[partition of a set|partition]] of a graph's vertices into subsets by their distances from a given starting vertex is called the [[level structure]] of the graph. − The partition of a graph's vertices into subsets by their distances from a given starting vertex is called the level structure of the graph. − 图的顶点依据与它们与给定顶点之间的距离划分成子集的过程称为'''<font color="#ff8000">图的层次结构 Level Structure of The Graph</font>'''。+ + − A graph such that for every pair of vertices there is a unique shortest path connecting them is called a '''geodetic graph'''. For example, all [[Tree (graph theory)|trees]] are geodetic.<ref>[[Øystein Ore]], Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104</ref> − A graph such that for every pair of vertices there is a unique shortest path connecting them is called a geodetic graph. For example, all trees are geodetic.+ − 如果对于每一对顶点，有一条唯一的最短路径连接它们，那么这样的图称为'''<font color="#ff8000">测地图 Geodetic Graph</font>'''。例如，所有的树状图都是测地图。+
→相关概念
==相关概念==
==相关概念==
一个由点集根据图中点集的距离定义的度'''<font color="#ff8000">[[度量空间 metric space]]</font>'''被称为<font color="#ff8000">图度量 Graph Metric</font>'''。
当且仅当图是连接的时，（无向图的）顶点集和距离函数构成度量空间。
在直径为<math>d</math>的图中，'''边缘顶点 peripheral vertex''' 是离心率为 <math>d</math>顶点，即距离等于直径的顶点。形式上，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。
在直径为<math>d</math>的图中，'''边缘顶点 peripheral vertex''' 是离心率为 <math>d</math>顶点，即距离等于直径的顶点。定义，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。
'''<font color="#ff8000">伪周边顶点 Pseudo-Peripheral Vertex</font>''' <math>v</math>具有这样的属性：对于任何顶点 <math>u</math>，如果<math>v</math>距离<math>u</math>越远，那么<math>u</math>距离 <math>v</math>越远。定义，如果一个顶点''u''对于每个顶点''v''都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>，则''u''是伪周边顶点。
依据图的顶点到给定起始顶点的距离将集合划分成多个子集称为'''<font color="#ff8000">图的层次结构 Level Structure of The Graph</font>'''。
对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为'''<font color="#ff8000">测地图 geodetic graph</font>'''。例如，所有的树状图都是测地图。<ref>[[Øystein Ore]], Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104</ref>
<br>
==Algorithm for finding pseudo-peripheral vertices 寻找伪周边的算法==
==Algorithm for finding pseudo-peripheral vertices 寻找伪周边的算法==