Provides detailed, human-like …

# 离散数学期末考前辅导

> 说明：你提到“3道题”，但消息中只写明2道，我先完整解答这两道；若还有第三题，请补充题目内容，我再解答。

一、图G（5顶点、8条边）存在欧拉路径的条件

欧拉路径判定定理：非平凡连通图G存在欧拉路径 ⟺ G中恰有0个或2个奇度顶点。

证明思路：

• 必要性：若存在欧拉路径，每经过一个中间顶点一进一出，贡献2度；起点、终点（若不同）各多贡献1度。故除可能的起点、终点外，其余顶点度数均为偶数，奇度顶点数为0或2。
• 充分性：若奇度顶点为0或2且图连通，可从一奇度顶点（或任一顶点）出发，每次沿未走过的边行走，可证明能构造出经过所有边的路径（Fleury思路：不走桥，除非别无选择）。
• 本题具体分析：5个顶点8条边时，度数之和 = 2×8 = 16。16为偶数，符合握手定理。但要注意：“5顶点8边”本身不能保证存在欧拉路径——还需满足图连通、且度数序列恰有0或2个奇数。例如度数序列若为 (4,4,4,2,2)（全偶）则存在欧拉回路；若为 (4,4,3,3,2)（恰两个奇数）则存在欧拉路径；若为 (5,4,3,2,2)（四个奇数）则不存在。

结论：G存在欧拉路径 ⟺ G连通且奇度顶点数为0或2。

二、真值表验证 (p→q)∧r ≡ (p∧r)→q

| p | q | r | p→q | (p→q)∧r | p∧r | (p∧r)→q |

|---|---|---|-----|---------|-----|---------|

| T | T | T | T | T | T | T |

| T | T | F | T | F | F | T |

| T | F | T | F | F | T | F |

| T | F | F | F | F | F | T |

| F | T | T | T | T | F | T |

| F | T | F | T | F | F | T |

| F | F | T | T | T | F | T |

| F | F | F | T | F | F | T |

对比第5、6列：(p→q)∧r 与 (p∧r)→q 在所有8种赋值下真值完全一致，故二者逻辑等价。∎

三、备考建议

• 欧拉相关题记牢“奇度顶点0或2”口诀，注意区分路径与回路。
• 真值表题务必列全 2ⁿ 行，逐列推导避免跳步。

如有第三道题，欢迎随时发来！