7,129
个编辑
更改
跳到导航
跳到搜索
第2行：
第2行： − {{for|the family of graphs known as paths|Path graph}}+ + − [[File:Snake-in-the-box and Hamiltonian path.svg|thumb|right|+ − 图1：A three-dimensional [[hypercube graph]] showing a [[Hamiltonian path]] in red, and a [[Snake-in-the-box|longest induced path]] in bold black. 一个三维的[超立方体图表显示一个红色的哈密顿图，和一个黑色的最长诱导路径]] − − − − In [[graph theory]], a '''path''' in a [[Graph (discrete mathematics)|graph]] is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]] which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A '''directed path''' (sometimes called '''dipath'''<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>) in a [[directed graph]] is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. − − In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. − − 在[[图论 Graph theory]]中，图中的'''路径 path'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。有向图(有时也称为dipath)中的有向路径，在具有附加条件：所有的边都方向相同时是一个有限或无限的边序列，它连接一系列不同的顶点。 − − − − Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced [[algorithm]]ic topics concerning paths in graphs. − − Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs. − − 路径是图论的基本概念，在大多数图论文本的导论部分都有描述。邦迪和默蒂(1976) ，吉本斯(1985) ，或迪斯特尔(2005)。柯尔特(1990)等人著作中，涵盖了更多关于图中路径的高级算法的话题。 − − --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“涵盖了更多关于图中路径的高级算法的话题。”一句中的“涵盖”改为“涉及” − --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“邦迪和默蒂(1976) ，吉本斯(1985) ，或迪斯特尔(2005)。柯尔特(1990)等人著作中，”一句改为“如在邦迪和默蒂(1976) 、吉本斯(1985) 、迪斯特尔(2005)、柯尔特(1990)等人著作中，” 第36行：
第17行： − +
无编辑摘要
由CecileLi初步审校；于2020.11.19再次审校，若有遗漏敬请谅解。
由CecileLi初步审校；于2020.11.19再次审校，若有遗漏敬请谅解。
[[File:Snake-in-the-box and Hamiltonian path.svg|thumb|right|图1：一个三维的超立方体图表显示一个红色的[[哈密顿图]]，和一个黑色的[[最长诱导路径]]]]
在[[图论 Graph theory]]中，图中的'''路径 path'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。'''有向图 directed path'''（有时也称为dipath<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>）中的有向路径，在具有附加条件：所有的边都方向相同时是一个有限或无限的边序列，它连接一系列不同的顶点。
路径是图论的基本概念，在大多数图论文本的导论部分都有描述，见Bondy and Murty（1976） ， Gibbons（1985），或Diestel（2005）。 Korte（1990）等人著作中，涵盖了更多关于图中路径的高级算法的话题。
== 定义==
== 定义==
* '''步道 Walk'''：是连接一系列[[顶点]]形成的有限或无限的边序列。{{sfn|Bender|Williamson|2010|p=162}}
* '''步道 Walk'''：是连接一系列[[顶点]]形成的有限或无限的边序列。
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a graph. A finite walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} such that {{nowrap begin}}''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}} for {{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the walk. This walk is ''closed'' if {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}}, and ''open'' else. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a graph. A finite walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} such that {{nowrap begin}}''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}} for {{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the walk. This walk is ''closed'' if {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}}, and ''open'' else. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.