交大115 線性代數與離散數學第9題｜離散數學 Ch6 圖論

離散數學›Ch6 圖論

第 7 題／共 34 題

7. Hamiltonian cycle、圖論、數學歸納法、完全圖

#LS-06-007難Hamiltonian cycle圖論數學歸納法完全圖

(7 points) A fully connected communication network on $n$ nodes is modeled by the complete graph $K_n$ , where $n \ge 5$ . Let $S \subseteq V(K_n) \cup E(K_n)$ be a set of failed nodes and links with $|S| \le n-3$ , such that no failed link is incident to a failed node. Let $K_n - S$ denote the network obtained after removing all failed nodes (and their incident links) and all failed links. Prove by induction on $n$ that the remaining network $K_n - S$ contains a Hamiltonian cycle. You may not assume any characterization theorem for Hamiltonian graphs.

📄 交大115

▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論

本章題號 · 1–20 / 34