请陈述无向图/有向图的手握手定理(度数和),以及平面图相关的欧拉公式,并简述其推论。
1. 握手定理(Handshaking Lemma):
直观:每条边贡献两个端点度数(或一入一出)。
2. 欧拉定理(平面图欧拉公式):对任意连通平面图,顶点数 V、边数 E、面数 F 满足:
V − E + F = 2
E ≤ 3V − 6;若无三角形,则 E ≤ 2V − 4。可用来证明 K₅、K₃,₃ 不可平面嵌入。3. 其他常用结论:
n(n−1)/2;完全二分图 K_{m,n} 边数 m·n。E = V − 1;任意两顶点间恰有一条路径。这些定理是图算法正确性分析与网络/电路建模的理论基础。
题目与答案就在本页;收藏、批注和错题重练在应用内