欧拉路径与哈密顿路径，紧密关联 | 离散数学 §10.5 回顾

1. 字幕依据
   观察依据

   板书文字将欧拉路径定义为一条恰好经过每条边一次的路线。

2. 声音
   观察依据

   讲述者说：“从欧拉路径开始，恰好经过每条边一次。”

Euler

图中一条恰好经过每条边一次的路线。

图

1. 字幕依据
   观察依据

   板书文字将哈密顿路径定义为一条恰好经过每个顶点一次的路线。

2. 声音
   观察依据

   讲述者说：“哈密顿路径关注的是顶点而非边，即一条恰好经过每个顶点一次的路线。”

Hamilton

图中一条恰好访问每个顶点一次的路线。

图

1. 字幕依据
   观察依据

   板书文字写道：“检验方法：统计奇度顶点的个数”，并在顶点 c 和 d 旁标注其度数为3。

2. 声音
   观察依据

   讲述者说：“圈出所有度数为奇数的顶点，然后仅统计它们的个数。”

degree

与一个顶点关联的边的条数；此处用于识别奇度顶点。

图中的顶点

1. 图示
   观察依据

   这座房子形状的图有五个顶点，标记为 a、b、c、d、e。

a, b, c, d, e

示例中房子形状图的顶点标记。

示例图中的顶点

1. 图示
   观察依据

   所绘制的房子图显示了边 ab、bc、cd、da、ac、ce、de。

1. 边集由图示读出，而非在屏幕上明确写出。

ab, bc, cd, da, ac, ce, de

示例中房子形状图的边。

示例图中的边

1. 声音
   观察依据

   主讲人说“顶点度数至少为 2 分之 n”以及“不相邻顶点的度数之和至少为 n”。

2. 字幕依据
   观察依据

   屏幕文字显示：“狄拉克条件（度数 ≥ $n/2$）”和“奥尔条件仅提供保证”。

n

图中顶点的个数

正整数

1. 字幕依据
   观察依据

   板书文字：“欧拉路线：每条边恰好经过一次；欧拉回路会回到起点；欧拉路径可在任意顶点结束。”

2. 声音
   观察依据

   旁白：“欧拉回路会回到它出发的地方；欧拉路径可在任意位置结束。”

欧拉路线是一条恰好经过图中每条边一次的路线。视频区分了两种情况：欧拉回路会返回其起始顶点，而欧拉路径可能终止于另一个不同的顶点。

1. 该路线必须恰好经过每条边一次。

2. 对于欧拉回路，路线会回到起始顶点。

3. 对于欧拉路径，路线可在任意位置结束。

1. 字幕依据
   观察依据

   板书文字：“哈密顿：一条经过每个顶点恰好一次的路线。”

2. 声音
   观察依据

   旁白：“哈密顿关注的是顶点而非边，即一条经过每个顶点恰好一次的路线。”

哈密顿路线被定义为一条经过每个顶点恰好一次的路线。视频中将其呈现为以顶点为基础、对应于以边为基础的欧拉问题。

1. 该路线必须经过每个顶点恰好一次。

1. 字幕依据
   观察依据

   板书文字：“检验方法：统计奇度顶点个数”以及“0个奇度顶点 → 欧拉回路；2个奇度顶点 → 欧拉路径；更多 → 两者皆无”

2. 声音
   观察依据

   旁白：“零个奇度顶点意味着存在欧拉回路；恰好两个奇度顶点意味着存在连接这两个顶点的欧拉路径；多于两个则两者都不可能存在。”

要判断一个图是否具有欧拉回路或欧拉路径，需统计奇度顶点的个数：若奇度顶点个数为零，则该图存在欧拉回路；若奇度顶点个数恰好为两个，则该图存在连接这两个顶点的欧拉路径；若奇度顶点个数多于两个，则该图既不存在欧拉回路，也不存在欧拉路径。

1. 该检验法适用于视频中所示的图。

2. 结论仅取决于奇度顶点的数量。

1. 欧拉路线、欧拉回路与欧拉路径的定义
2. 为何欧拉路径中的内部访问迫使顶点度数为偶数

1. 字幕依据
   观察依据

   板书文字：“原因：每次经过一个顶点会消耗2条边（进入 + 离开）→ 为偶数。”

2. 声音
   观察依据

   讲述者：“每当一条路径经过一个顶点时，它都会使用两条边：一条进入，一条离开。因此，这些顶点的度数必然为偶数。”

欧拉路径在途经某个顶点（非起点或终点）时，每次均使用一条边进入、一条边离开。因此，每一次这样的途经都会消耗两条与该顶点关联的边，故仅被途经（而不作为端点）的顶点必须具有偶度。

1. 该论证适用于路径中被进入又离开的顶点。

2. 它解释了为何欧拉路径中非端点的顶点度数必为偶数。

1. 欧拉路线、欧拉回路与欧拉路径的定义

1. 字幕依据
   观察依据

   开场幻灯片文字：“欧拉问题 = 遍历每条边（简单） vs 哈密顿问题 = 遍历每个顶点（困难）”

2. 声音
   观察依据

   讲述者：“其中一个结果出人意料地简单，另一个则真正困难。”

视频通过指出二者听似相似、实则难度迥异来对比欧拉问题与哈密顿问题：欧拉问题容易，因其可通过度数统计判定；而哈密顿问题困难。

1. 这是在回顾环节中陈述的概念性对比。

2. 本片段未给出难度的严格证明。

1. 欧拉路线、欧拉回路与欧拉路径的定义
2. 哈密顿路线的定义

1. 字幕依据
   观察依据

   屏幕文字：“哈密顿回路：一条恰好经过每个顶点一次的路径”。

2. 声音
   观察依据

   主讲人说“不存在简单的度数判定法……”，此处指哈密顿回路。

哈密顿回路是图中一条恰好经过每个顶点一次的路径。

1. 必须经过每一个顶点

2. 必须恰好经过每个顶点一次

1. 字幕依据
   观察依据

   屏幕文字：“狄拉克条件（度数 ≥ $n/2$）与奥尔条件仅提供充分性保证——充分但非必要”。

2. 声音
   观察依据

   主讲人解释狄拉克条件与奥尔条件基于度数条件给出充分性保证。

狄拉克定理指出：若每个顶点的度数至少为 $n/2$，则图中必存在哈密顿回路。奥尔定理则考察不相邻顶点的度数之和。二者均为充分但非必要条件。

1. 哈密顿回路存在的充分条件

2. 并非必要条件

1. 哈密顿回路的定义

1. 字幕依据
   观察依据

   屏幕文字：“判定哈密顿回路是否存在 = NP-完全问题”

2. 声音
   观察依据

   主讲人指出：判定一个图中是否存在哈密顿回路是 NP-完全问题。

判定任意图是否包含哈密顿回路是一个 NP-完全问题，意味着该问题在计算上是困难的。

1. 适用于一般图

1. 哈密顿回路的定义

1. 字幕依据
   观察依据

   屏幕文字：“接下来：在每条边上挂一个 WEIGHT——即一段距离或一项费用”

2. 声音
   观察依据

   主讲人提到：在每条边上标注一个数字，代表距离或费用。

加权图是一种图，其中每条边都被赋予一个数值，通常表示距离、成本或权重。

1. 边具有关联的数值

1. 字幕依据
   观察依据

   屏幕文字：'最短哈密顿 = 旅行商问题（TSP）'。

2. 声音
   观察依据

   主讲人指出，最短哈密顿回路即为旅行商问题。

旅行商问题要求在加权图中找出总权重最小的哈密顿回路。

1. 图必须是加权图

2. 寻求最小总权重

1. 哈密顿回路的定义
2. 赋权图

1. 字幕依据
   观察依据

   欧拉路径（边）：每条边恰好经过一次；其存在性可立即通过统计奇度顶点个数（$0 / 2$ / 更多）判定

欧拉路径恰好遍历图中每一条边一次。其存在性可通过统计奇度顶点的个数立即判定。

1. 该图必须恰好有0个或2个奇度顶点。

1. 字幕依据
   观察依据

   哈密顿路径（顶点）：每个顶点恰好经过一次；无简易判定法——仅有若干排除性条件及Dirac定理/Ore定理，且该问题是NP完全的

哈密顿路径恰好访问图中每一个顶点一次。与欧拉路径不同，目前不存在简单而充要的判定条件；判定其是否存在是一个NP完全问题。

1. 目前已知的仅是一些充分条件，例如Dirac定理或Ore定理，可用于排除不存在性。

1. 字幕依据
   观察依据

   黑板文字：“0个奇数度顶点 → 欧拉回路”

2. 声音
   观察依据

   解说员：“零个奇数度顶点意味着存在欧拉回路。”

1. 该片段未明确说明连通性假设。

若一个图有0个奇数度顶点，则它存在欧拉回路。

1. 该图属于本视频欧拉讨论中所考虑的图类型。

针对当前所讨论的图。

1. 字幕依据
   观察依据

   黑板文字：“2个奇数度顶点 → 欧拉路径”

2. 声音
   观察依据

   解说员：“恰好两个奇数度顶点意味着存在一条连接这两个顶点的欧拉路径。”

1. 该片段未明确说明连通性假设。

如果一个图恰好有2个奇度顶点，那么它存在一条连接这两个顶点的欧拉路径。

1. 该图属于本视频欧拉问题讨论中所考虑的图类型。

针对当前所讨论的图。

1. 字幕依据
   观察依据

   黑板文字：“更多 → 两者皆不可”

2. 声音
   观察依据

   解说员：“只要出现‘更多’，就意味着两者都不可能。”

如果一个图的奇度顶点数量超过2个，那么它既不存在欧拉回路，也不存在欧拉路径。

1. 该图属于本视频欧拉问题讨论中所考虑的图类型。

针对当前所讨论的图。

1. 字幕依据
   观察依据

   黑板文字：“柯尼斯堡的4个奇数陆地 → 两者皆不可——该行走无法实现”

2. 声音
   观察依据

   解说员：“这正是柯尼斯堡拥有四块奇数陆地，导致其七桥行走问题无解的根本原因。”

哥尼斯堡的四个奇数度陆地区域使得七桥漫步问题无解。

1. 哥尼斯堡问题设定中有4个奇数度陆地区域。

视频中提到的哥尼斯堡桥梁示例。

1. 字幕依据
   观察依据

   黑板文字：“听起来像欧拉——其实完全不是一回事”。

2. 声音
   观察依据

   旁白：“听起来像是欧拉问题的一个微小变体，但实际上绝非如此。”

尽管哈密顿问题听起来像是欧拉问题的一个小变体，但二者在本质上截然不同。

视频中陈述的一般性比较。

1. 字幕依据
   观察依据

   屏幕文字：'——充分但非必要（C5两条都不满足）'。

2. 声音
   观察依据

   主讲人说：'但这些条件只是充分的，而非必要的。平面五边形环不满足任一条件，却仍存在一个完美的回路。'

狄拉克定理与奥尔定理中的度数条件可保证哈密顿回路的存在，但并非存在哈密顿回路所必需的条件。

1. 图满足狄拉克条件或奥尔条件

对所有图而言

1. 图示
   观察依据

   房屋图以顶点 a、b、c、d、e 和边 ab、bc、cd、da、ac、ce、de 绘制。

2. 字幕依据
   观察依据

   黑板随后将顶点 c 和 d 标记为奇数度顶点，并标注其度数为3。

1. 中间的度数计算是从所绘制的图中推断得出，而非在屏幕上逐步写出。

1. 公式

   $$\deg(a)=2$$
   解释

   顶点 a 与边 ab 和 ad 关联。

   步骤依据

   在所画出的图中统计关联边的数量。

   依据视频推导
2. 公式

   $$\deg(b)=2$$
   解释

   顶点 b 与边 ab 和 bc 关联。

   步骤依据

   在所画出的图中统计关联边的数量。

   依据视频推导
3. 公式

   $$\deg(c)=3$$
   解释

   顶点 c 与边 bc、ac 和 ce 关联。

   步骤依据

   在所画出的图中统计关联边的数量。

   依据视频推导
4. 公式

   $$\deg(d)=3$$
   解释

   顶点 d 与边 cd、ad 和 de 关联。

   步骤依据

   在所画出的图中统计关联边的数量。

   依据视频推导
5. 公式

   $$\deg(e)=2$$
   解释

   顶点 e 与边 ce 和 de 关联。

   步骤依据

   在所画出的图中统计关联边的数量。

   依据视频推导
6. 公式

   $$\text{odd-degree vertices} = \{c,d\}$$
   解释

   仅有 c 和 d 的度为奇数。

   步骤依据

   将计算所得的度与奇偶性进行比较。

   视频直接表达

示例的房屋图恰好有两个奇度顶点，即〔c〕和〔d〕。

1. 字幕依据
   观察依据

   板书文字：“原因：每次经过一个顶点会消耗2条边（进入 + 离开）→ 为偶数”

2. 声音
   观察依据

   讲述者解释说，进入和离开各使用一条边。

1. 公式

   $$\text{one pass through a vertex} = \text{enter} + \text{leave}$$
   解释

   一条经过某顶点的路径，使用一条边进入、一条边离开。

   步骤依据

   视频中直接陈述。

   视频直接表达
2. 公式

   $$\text{edges spent per internal pass} = 2$$
   解释

   每次内部访问消耗两条关联边。

   步骤依据

   源自‘进入—离开’的描述。

   视频直接表达
3. 公式

   $$\text{internal vertices have \text{偶数} degree}$$
   解释

   由于欧拉路径在内部顶点处成对地使用关联边，因此这些顶点的度必须为偶数。

   步骤依据

   视频中将其作为度数检验依据而陈述。

   视频直接表达

欧拉路径中的内部顶点必须具有偶度，这引出了奇度顶点计数检验。

1. 图示
   观察依据

   黑板上画出一个房屋形状的图，其顶点为〔a〕、〔b〕、〔c〕、〔d〕、〔e〕。

2. 字幕依据
   观察依据

   黑板上写着：“检验方法：统计奇度顶点的个数”，以及“此处有两个奇度顶点（c、d）”。

3. 声音
   观察依据

   讲述者将该规则应用于此图，并得出结论：图中有两个奇度顶点。

判断所展示的房屋形状图是否具有欧拉回路、欧拉路径，或两者皆无。

1. 图的顶点为：a、b、c、d、e。

2. 图中可见的边为：ab、bc、cd、da、ac、ce、de。

利用欧拉度数检验法对图进行分类。

1. 公式

   $$\deg(a)=2,\ \deg(b)=2,\ \deg(c)=3,\ \deg(d)=3,\ \deg(e)=2$$
   解释

   根据所画出的图，计算每个顶点的度数。

   步骤依据

   在图中统计各顶点的关联边数。

   依据视频推导
2. 公式

   $$\text{odd-degree vertices} = \{c,d\}$$
   解释

   找出哪些顶点具有奇度。

   步骤依据

   对已计算出的各顶点度数进行奇偶性检验。

   视频直接表达
3. 公式

   $$2 \text{ odd} \rightarrow \text{Euler path}$$
   解释

   应用视频中所述的规则：当且仅当存在恰好两个奇度顶点时……

   步骤依据

   板书规则与旁白。

   视频直接表达

房屋图具有一条欧拉路径，该路径在两个奇度顶点 c 和 d 之间运行。

结果与屏幕上的陈述“此处有两个奇度顶点（c, d）”以及规则“2个奇度顶点 → 存在欧拉路径”相吻合。

1. 字幕依据
   观察依据

   屏幕文字：‘（C5均不满足）’。

2. 声音
   观察依据

   说话人提到：‘平面五边形环图不满足任一条件，却仍具有一个完美的环路。’

环图 C5是否满足狄拉克定理或奥尔定理关于哈密顿环路的条件？

1. C5是含5个顶点的环图

检验狄拉克条件或奥尔条件是否成立

1. 解释

   C5有5个顶点，故 $n = 5$。每个顶点的度数为2。

   步骤依据

   环图的定义

   依据视频推导
2. 解释

   狄拉克条件要求每个顶点的度数 ≥ $5/2 = 2.5$。由于$2 < 2.5$，狄拉克条件不成立。

   步骤依据

   狄拉克定理的条件

   依据视频推导
3. 解释

   奥尔定理要求任意两个不相邻顶点的度数之和 ≥ 5。在图 C5 中，最大度数之和为 $2+2=4 < 5$，因此不满足奥尔定理条件。

   步骤依据

   奥尔定理的条件

   依据视频推导
4. 解释

   尽管不满足这两个条件，图 C5 本身却是一个哈密顿回路。

   步骤依据

   哈密顿回路的定义

   视频直接表达

图 C5 两个条件均不满足，但仍存在哈密顿回路。

直接观察图 C5 的结构可知，它是一个遍历所有顶点的单一回路。

1. 图示
   观察依据

   标题幻灯片显示：“欧拉与哈密顿”、“遍历每条边，或遍历每个顶点”，以及“欧拉 = 遍历每条边（简单） vs 哈密顿 = 遍历每个顶点（困难）”。

1. 标题文字

2. 副标题文字

3. 对比说明行

4. 引述框

1. 幻灯片保持静止，同时旁白介绍这两个问题。

1. ‘边’（EDGE）与‘顶点’（VERTEX）之间的视觉对比保持固定。

开场幻灯片将整段视频定调为欧拉问题与哈密顿问题的对比。

1. 图示
   观察依据

   黑板风格画面展示一个房屋形状的图以及欧拉定义。

2. 动画
   观察依据

   约51秒时，顶点c和d周围出现红色圆圈，并添加文字：“此处有两个奇度顶点（c、d）”。

1. 房屋形状的图

2. 顶点标签为a、b、c、d、e

3. 欧拉定义文字

4. 奇度标注

5. 规则框

1. 首先引入该图。

2. 接着高亮显示奇度顶点c和d。

3. 随后出现规则框及说明性文字。

1. 在欧拉部分内容中，底层图结构保持不变。

该可视化序列展示了度数判别法如何应用于一个具体的图。

1. 图示
   观察依据

   一张米色幻灯片出现，上面写着“孪生问题”、“外观相同，命运相反”，以及“遍历每个顶点而非每条边——难度却彻底反转”。

1. 标题文字

2. 副标题文字

3. 分隔线

1. 画面从黑板上的欧拉示例切换至一张新的标题卡片。

1. 该信息强调了表述相似性与难度差异之间的对比。

这张幻灯片标志着概念重心从边覆盖转向顶点覆盖。

1. 图示
   观察依据

   一个新的黑板场景展示了一个内部带十字的菱形图，并配有哈密顿路径的定义文字。

1. 带内部十字的菱形图

2. 哈密顿定义文本

3. 与欧拉的对比文本

1. 黑板引入哈密顿定义，并立即将其与欧拉进行对比。

1. 本片段中未完成任何哈密顿问题的演算示例。

最终画面确立哈密顿为基于顶点的问题，并强调它绝非欧拉问题的一个微小变体。

1. 动画
   观察依据

   展示了一个含 4 个顶点和 5 条边的图。随后，在一个类似图的各条边上出现了权重（数字）。

1. 无权图

2. 带权图

1. 边被赋予数值权重

1. 顶点保持不变

说明了从无权连通性问题向带权优化问题的转变。

1. 图示
   观察依据

   一张静态总结幻灯片，标题为“每条边都容易，每个顶点都困难”，包含三个文本框，分别对比欧拉路径、哈密顿路径以及加权图的后续主题。

1. 标题文字

2. 三个信息文本框

1. 该幻灯片的视觉布局和文字在整个2秒片段中完全保持静止。

该幻灯片在视觉上对比了基于边的遍历（欧拉）与基于顶点的遍历（哈密顿）在计算难度上的差异，并预示了向加权图算法的过渡。

1. 字幕依据
   观察依据

   开场引语：“两个听起来像双胞胎的谜题——一个只需观察各顶点度数即可解决，另一个却是我们所知最难的问题之一。”

2. 声音
   观察依据

   解说员：“在纸面上，它们听起来几乎一模一样。”

由于欧拉问题与哈密顿问题的表述方式相似，人们可能认为它们几乎是同一个问题。

视频着重指出：二者仅在听感上相似；欧拉问题可通过度数统计轻松解决，而哈密顿问题则真正困难。

1. 字幕依据
   观察依据

   黑板文字：“听起来像欧拉——实则毫无相似之处。”

2. 声音
   观察依据

   解说员：“它听起来像是欧拉问题的一个微小变体。但它绝对不是。”

人们或许会认为，把“边”换成“顶点”只会带来细微的变化。

视频明确否定了这种看法：哈密顿问题在难度和行为特征上被呈现为根本不同。

1. 字幕依据
   观察依据

   屏幕文字：“没有简单的度数判定法。”

2. 声音
   观察依据

   说话人开头说道：“不存在简单的度数判定法……”

人们可能误以为存在一种基于顶点度数的简单判定法，用以判断哈密顿回路是否存在，就像欧拉回路那样。

并不存在这样的简单判定法；目前仅有若干阻碍条件和充分条件（如狄拉克条件或奥尔条件），且该问题是 NP-完全的。

1. 字幕依据
   观察依据

   表面相似的问题，实际难度相反

误以为欧拉路径问题与哈密顿路径问题看起来相似（两者都涉及在图中无重复地遍历），因此它们具有相同的计算难度。

欧拉路径的判定是容易的（可通过奇度数计数在多项式时间内完成），而哈密顿路径是NP完全问题，代表了截然相反的计算难度层级。

1. 字幕依据
   观察依据

   欧拉部分介绍了奇度数计数检验。

2. 声音
   观察依据

   讲述者指出，整个问题仅凭度数统计即可判定。

度数统计法被用于判断欧拉回路与欧拉路径的存在性。

1. 字幕依据
   观察依据

   板书给出的理由是：“每次经过一个顶点消耗2条边（进 + 出）→ 为偶数”。

奇偶性解释支撑了奇度数计数检验为何适用于欧拉路线。

1. 字幕依据
   观察依据

   开场幻灯片对比了“遍历每条边（简单）”与“遍历每个顶点（困难）”。

2. 字幕依据
   观察依据

   最后的板书写道：哈密顿问题“听起来像欧拉问题——实则毫无相似之处”。

视频反复对比欧拉基于边的问题与哈密顿基于顶点的问题。

1. 图示
   观察依据

   在讲解欧拉规则时使用了房屋图。

2. 字幕依据
   观察依据

   黑板上将 c 和 d 标记为本例中的奇顶点。

房屋图示例说明了欧拉度数检验在实际中如何应用。

1. 字幕依据
   观察依据

   屏幕文字：“每条边容易，每个顶点困难”，以及欧拉回路与哈密顿回路的对比表格。

2. 声音
   观察依据

   说话人将欧拉回路（易解，关注边）与哈密顿回路（难解，关注顶点）进行对比。

欧拉回路（遍历所有边）的判定是容易的，而哈密顿回路（遍历所有顶点）的判定是困难的（NP-完全）。

1. 字幕依据
   观察依据

   每条边都容易，每个顶点都困难

视频明确对比了欧拉路径（仅凭顶点度数即可即时判定）与哈密顿路径（属于NP完全问题）在可判定性上的差异。

1. 字幕依据
   观察依据

   接下来，每条边都带有权重。

通过给边赋予权重，图遍历的概念得以拓展，从而引出迪杰斯特拉算法和旅行商问题等优化算法。

1. 字幕依据
   观察依据

   黑板文字定义了欧拉图（EULER）。

1. 欧拉路线、欧拉回路与欧拉路径的定义

1. 字幕依据
   观察依据

   黑板文字定义了哈密顿图（HAMILTON）。

1. 哈密顿路线的定义

1. 字幕依据
   观察依据

   黑板文字给出规则：0奇，2奇，更多。

1. 欧拉回路与欧拉路径的度数统计检验法

1. 字幕依据
   观察依据

   黑板文字解释：入度加出度 → 偶数。

1. 为何欧拉路径中的内部访问迫使顶点度数为偶数

1. 图示
   观察依据

   展示了房屋图及奇顶点标注。

1. 房屋图的欧拉性检验
2. 欧拉回路与欧拉路径的度数统计检验法

1. 字幕依据
   观察依据

   板书文字提到柯尼斯堡的4个奇数度顶点。

1. 柯尼斯堡七桥行走问题无解
2. 欧拉回路与欧拉路径的度数统计检验法

1. 字幕依据
   观察依据

   开场幻灯片与结尾板书对比了简单的欧拉问题与困难的哈密顿问题。

1. 欧拉问题与哈密顿问题在难度上的对比
2. 将哈密顿问题视为欧拉问题的一个微小调整

1. 字幕依据
   观察依据

   屏幕文字：“判定哈密顿回路是否存在 = NP-完全”。

1. 哈密顿回路问题的 NP-完全性

1. 字幕依据
   观察依据

   屏幕文字：“狄拉克条件（deg ≥ $n/2$）与奥尔条件仅提供保证。”

1. 狄拉克定理与奥尔定理

1. 字幕依据
   观察依据

   仅通过统计奇度顶点个数（$0 / 2$ / 更多）即可即时判定

1. 欧拉路径存在条件

1. 字幕依据
   观察依据

   没有简单的判定方法——仅有若干必要条件（如狄拉克定理、奥尔定理）及已知的障碍，且该问题是NP完全的

1. 哈密顿路径的计算复杂性