第八章习题 证明:∑d()=∑d()=E 2.证明:若有向图G中无有向圈,则o-=o+=0。 3.证明:对每个竞赛图,要么它本身是强连通的,要么可以只改变一条弧的方向而变成强 连通的 4.任何连通图G必有一种定向方式,使得每条有向路的长度不超过△(G)。 5.设非平凡弱连通有向图G满足下列条件: (1)d'(x)-d-(x)=d(y)-d(y)=k (2)d(v)=d(v),(v∈(G)-{x,y})。 证明:G中有k条无公共边且以x为起点以y为终点的有向路。 6.n名棋手进行循环赛,没有出现平局,也没有出现甲胜乙、乙胜丙、丙又胜甲的情况。证 明必有一人在所有比赛中全胜,也必有一人在所有比赛中全败。 7.图有n种昆虫,每两种必有一种能吃掉另一种,证明可以把这些昆虫排序,使得每一种 昆虫能吃掉它前面的那种昆虫。 8在一次围棋擂台赛中,双方各出n名选手。比赛的规则是双方先各自排定一个次序,设甲 方排定的次序为x2x2…xn,乙方排定的次序为y,y2…y。x1与y先比赛,胜的一位 与对方输的下一位选手比赛。按这种方法进行比赛,直到有一方的最后一位选手出场比赛并 且输给对方,比赛结東。问最多进行几场比赛可定其胜负(假定比赛不出现平局)。16 第八章习题 1. 证明： () () vV vV dv dv ε − + ∈ ∈ ∑ ∑= = ； 2. 证明：若有向图 G 中无有向圈，则δ δ 0 − + = = 。 3. 证明：对每个竞赛图，要么它本身是强连通的，要么可以只改变一条弧的方向而变成强 连通的。 4．任何连通图 G 必有一种定向方式，使得每条有向路的长度不超过 Δ( ) G 。 5. 设非平凡弱连通有向图 G 满足下列条件： （1）dx dx dy dy k () () () () +− −+ −=−= ； （2）d v d v v VG xy ( ) ( ), ( ( ) { , }) + − = ∀∈ − 。 证明：G 中有 k 条无公共边且以 x 为起点以 y 为终点的有向路。 6. n 名棋手进行循环赛，没有出现平局，也没有出现甲胜乙、乙胜丙、丙又胜甲的情况。证 明必有一人在所有比赛中全胜，也必有一人在所有比赛中全败。 7. 图有 n 种昆虫，每两种必有一种能吃掉另一种，证明可以把这些昆虫排序，使得每一种 昆虫能吃掉它前面的那种昆虫。 8.在一次围棋擂台赛中，双方各出 n 名选手。比赛的规则是双方先各自排定一个次序，设甲 方排定的次序为 1 2 ,,, n x x x ⋅⋅⋅ ，乙方排定的次序为 1 2 ,,, n y y y ⋅⋅⋅ 。 1 x 与 1 y 先比赛，胜的一位 与对方输的下一位选手比赛。按这种方法进行比赛，直到有一方的最后一位选手出场比赛并 且输给对方，比赛结束。问最多进行几场比赛可定其胜负（假定比赛不出现平局）