526
个编辑
更改
跳到导航
跳到搜索
第117行：
第117行： − 如果路径包含每一对顶点，则图是连通的。+ − 如果一个有向图中存在包含每对顶点的相对有向路径，那么这个有向图就是强连通的。+ − 没有图的边连接两个不连续的路径顶点的路径称为'''<font color="#ff8000">诱导路径 Induced Path</font>'''。+ 第129行：
第129行： − 如果两条路径没有任何共同的内部顶点，则它们与顶点无关(或者，内部顶点不相交)。类似地，如果两条路径没有任何共同的内边，则它们是边独立的(或边不相交)。两条内部顶点不相交的路径是边不相交的，但反过来也不一定是正确的。+ 第136行：
第136行： −
→Examples 例子
* A graph is [[Connectivity (graph theory)|connected]] if there are paths containing each pair of vertices.
* A graph is [[Connectivity (graph theory)|connected]] if there are paths containing each pair of vertices.
如果路径包含每一对顶点，那么图就是连通的。
* A directed graph is [[Strongly-connected digraph|strongly connected]] if there are oppositely oriented directed paths containing each pair of vertices.
* A directed graph is [[Strongly-connected digraph|strongly connected]] if there are oppositely oriented directed paths containing each pair of vertices.
如果一个有向图中存在包含每对顶点的相对有向路径，那么这个有向图就是紧密连通的。
* A path such that no graph edges connect two nonconsecutive path vertices is called an [[induced path]].
* A path such that no graph edges connect two nonconsecutive path vertices is called an [[induced path]].
没有边连接两个不连续的路径顶点的路径称为'''<font color="#ff8000">诱导路径 Induced Path</font>'''。
* A path that includes every vertex of the graph is known as a [[Hamiltonian path]].
* A path that includes every vertex of the graph is known as a [[Hamiltonian path]].
* Two paths are ''vertex-independent'' (alternatively, ''internally vertex-disjoint'') if they do not have any internal vertex in common. Similarly, two paths are ''edge-independent'' (or ''edge-disjoint'') if they do not have any internal edge in common. Two internally vertex-disjoint paths are edge-disjoint, but the converse is not necessarily true.
* Two paths are ''vertex-independent'' (alternatively, ''internally vertex-disjoint'') if they do not have any internal vertex in common. Similarly, two paths are ''edge-independent'' (or ''edge-disjoint'') if they do not have any internal edge in common. Two internally vertex-disjoint paths are edge-disjoint, but the converse is not necessarily true.
如果两条路径没有任何共同的内部顶点，那么它们与顶点无关(换言之，内部顶点不相交)。类似地，如果两条路径没有任何共同的内边，那么它们是边独立的(或边不相交)。两条内部顶点不相交的路径的边也不相交，但反之未必正确的。
* The [[Distance (graph theory)|distance]] between two vertices in a graph is the length of a shortest path between them, if one exists, and otherwise the distance is infinity.
* The [[Distance (graph theory)|distance]] between two vertices in a graph is the length of a shortest path between them, if one exists, and otherwise the distance is infinity.
* The diameter of a connected graph is the largest distance (defined above) between pairs of vertices of the graph.
* The diameter of a connected graph is the largest distance (defined above) between pairs of vertices of the graph.
连接图的直径是图的顶点对之间的最大距离（如上定义）。
连接图的直径是图的顶点对之间的最大距离（如上定义）。
== Finding paths 路径寻找==
== Finding paths 路径寻找==