1、第 1章 图论预备知识 1.1 解： (1) p= ,a,b,c,a,b,a,c,b,c,a,b,c (2) p= ,a,b,c,a,b,c (3) p= , (4) p= , , , , (5)p= ,a,b,a,a,b,a,b,a,b,a,b,a,a,b,a,b,a,b,a,b,a,b,a,a,b,a,b,a,b 1.2 解： (1) 真 (2) 假 (3)假 (4)假 1.3 解： (1) 不成立， A=1 B=1,2 C=2 (2) 不成立， A=1 B=1,2 C=1,3 1.4 证明：设 (x,y) (A B)X(C D) 说明 x A B,y C D 由于 x A,y C 所以
2、(x,y) A X C 由于 x B,y D 所以 (x,y) B X D 所以 (x,y) （ A X C） （ B X D） 反过来，如果（ x,y） (A X C) （ B X D） 由于 (x,y) （ A X C）所以 x A,y C 由于 (x,y) （ B X D）所以 x B,y D 所以 x (A B) y (C D) 所以 (x,y) (A B)X(C D) 所以 (A B)X(C D)= (A X C) （ B X D） 1.5 解： Hasse 图 24 12 4 10 5 2 3 9 极大元 9,24,10,7 极小元 3,2,5,7 最大元 24 最小元 2 1.6
3、 解 (1)R=|x 整除 y (2)关系图为： (3)不存在最大元，最小元为 2 1.7 解： (1)R=, (2)略 (3)IA R 故 R 是自反的。 R R 但是 R 故不满足传递性 1.8 解： (1) 不成立 A=1 B=2 C=3 D=4 则左式 =，, 右式 =, (2) 不成立 A=1,3 B=1 C=2,4 D=2 则左式 = 右式 =, (3) 不成立 A=1 B=2 C=3 D=4 则左式 =, 右式 =, (4) 成立 证明：设 (A-B)X C x (A-B) y C x A x B y C A X C B X C (A X C)-(B XC) 故得 （ A-B）
4、X C=（ A X C） -（ B X C） 8 10 5 1 7 2 9 6 4 1.9 略 1.10 略 1.11 解： A 为 n 个元素的优先级和， A 上有 2n2 个 不同的二元关系，理由为：设 A， B 为集合， AXB 的任何子集所定义的二元关系称作从 A 到 B 的二元关系，特别当 A=B 时，称作 A 上的二元关系，若 |A|=n，则 |AXA|=n2，那么 A 上共有2n2 个不同的二元关系。 1.12 略 1.13 解： 1)真 .由于 R1 和 R2 和 R2 都是自反的 ,因而对任何 ,都有 (x,x) R1,(x,x) R2.因此 ,对任何 x A,都有 (x,x
5、) R1R2.所以 R1R2 是自反的 。 2)假 .令 A=a,b,R1=(a,b),R2=b,a.那么 R1R2=(a,a),它就不是 A 上的反自反关系 . 3)假 .令 A=a,b,c,R1=(a,b),(b,a),R2=(b,c),(c,b).那末 R1R2=(a,c),就不是 A的对称关系 . 4)假 .令 A=a,b,c,d,R1=(a,c),(b,c),R2=(c,b),(d,a)易证 R1,R2 都是反对称关系 .但是 R1R2=(a,b),(b,a)就不是 A 上的反对称关系 . 5)假 .令 A=a,b,c,R1=(a,c),(b,a),(b,c),R2=(c,b),(a
6、,c),(a,b),易证 R1 和 R2 都是传递关 系 ,但 R1R2=(a,b),(b,b),(b,c)就不是 A 上的传递关系 . 1.14 证明：由任意的 a，存在一个 b，使得 R,由对称性所以 R,由传递性 R,所以 R 是等价关系。 1.15 证明： x A， R, S R S，所以 R S 有自反性； x,y A,因为 R,S 是反对称的， R S R S( R S) ( R S)( R R) ( S S)x=y y=xx=y 所以， R S 有反对称性。 x,y,z A,因为 R,S 是传递的， R S R S R S R SR R S S R S R S 所以， R S 有
7、传递性。 所以 R S 也是 A 上的偏序关系。 1.16 解：r(R)=, s(R)=, t(R)=, 1.17 (1)证明： 对任意 a,b,a+b=a+b,故得 (a,b)R(a,b),关系 R 具有 自反性 ; 如果 (a,b)R(c,d),则 a+d=b+c,c+b=d+a,故得 (c,d)R(a,b), 关系 R 具有对称性 ; 如果 (a,b)R(c,d),(c,d)R(e,f),则 a+d=b+c,c+f=d+e, 故得 a+f=b+e,(a,b)R(e,f),关系 R 具有传递性 ; 于是关系 R 是 等价关系 . 1.18 略 1.19 略 1.20 解： (1) 单射 (
8、2) 满射 (3) 既不是单射，也不是满射 (4) 满射 (5) 双射 1.21 解： (1) O(n3) (2) O(n5) (3) O(n3n!) 第 2 章 图 2.1 解： (1) (2) 2.2 解： 构成无向图的度序列： (1)、 (2)、 (3)、 (4)、 (6) 构成无向简单图的度序列： (2)、 (3)、 (4) 2.3 解： 补图为 ： 2.4 a b c d e a b c d e a:出度为 3、入度为 1 b:出度为 2、入度为 2 c:出度为 2、入度为 3 d:出度为 2、入度为 3 e:出度为 2、入度为 2 a:出度为 3、入度为 1 b:出度为 1、入度为
9、 2 c:出度为 3、入度为 3 d:出度为 3、入度为 2 e:出度为 0、入度为 3 解： 设图 G 中结点数为 n,则有 3x4+3x(n-3)=2x12.求得 n=7,即图 G 有 7 个结点 . 2.5 证明 将习图 2.2 的两图顶点标号为如下的 (a)与 (b)图 作映射 f : f(vi)ui (1 i 10) 容易证明，对 vivjE(a),有 f(vivj)uiujE(b) (1 i 10, 1j 10 ) 由图的同构定义知，两个图是同构的。 2.6 解： 同构对应关系： a 8、 b 7、 c 4、 d 9、 e 5、 f 6、 g 1、 h 2、 i 10、j 3. 2
10、.7 证：设在一有向完全图 G 中，边数为 n.则可知 +()= ()= .即所有结点的入度和等于所有节点的出度和，即所有结点的入度的平方和等于所有节点的出度的平方和。 2.8 ( a ) v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 u1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 ( b ) 解： (1) (2) 2.9 证明：用反证法。 设无向图 G 只有两个奇点 u,v，若 u,v 不连通，即它们之间没任何通路，则G 至少有两个连通分支 G1,G2，且 u,v 分别属于 G1 和 G2，于是 G1 和 G2 中各有一个奇
11、度结点，与握手定理矛盾，因此 u,v 必连通。 2.10 解：点割集为： v1， v3、 v4、 v6 割点为： v4、 v6 2.11 解：强连通图： (a） 单相连通图：（ b）（ c）（ d） 弱连通图：（ a）（ b）（ c）（ d） 2.12 证明 :设 v0v1vk 为 G 中一条最长路，则 v0 的邻接顶点一定在该路上，否则，与假设矛盾。现取与 v0 相邻的脚标最大者，记为 l，则 l,于是得圈 v0v1v2vlv0,该圈长为 l+1，显然不小于 +1。 2.13 证明：证其逆否命题： e 不是割边当且仅当 e 含在 G 的某个圈中。 必要性：设 e=xy 不是割边。假定 e 位
12、于 G 的某个连通分支 G1 中，则 G1-e 仍连通。故在 G1_e 中有 (x,y)路 P， P+e 便构成 G1 中一个含有 e 的圈。 充分性：设 e 含在 G 的某个圈 C 中，而 C 含于某连通分支 G1 中，则 G1-e 仍连通。故 W(G-e)=W(G)，这说明 e 不是割边 ,证毕。 2.14 证明：用数学归纳法证明： （ 1） n=1 时， G 为平凡图，显然 G 连通。 （ 2） n=2 时， ( )( ) = 此时 G 为 K2，当然连通 。 （ 3）假设当 n=k（ k 2） 时， ( )( ) 结论成立 。 当 n=k+1 时，若此时每个结点度数为 k，则结论显然成
13、立，否则必存在一个结点v 度数至多只有 k-1 度，即这个结点最多只有 k-1 条边和它相连。因为此时总的边数 ( ),则其它 k 个结点之间的边数 ( ) ( ) =( )( )。根据归纳假设，显然这 k 个结点之间是连通的，而根据上面我们知道，至少有一条边使 v 和其它结点相连，所以此时这个图是连通的 ,结论成立。 2.15 证明： （ 1） 因为 G 连通，且 G 无割边，所以任意两个结点 u,v，都存在简单道路 p=uwv.又因为 G 无割边，所以，删除边 wv 后，子图依然连通，即 w,v 存在简单道路 ,以此类推，可以找到一条和 p 每条边都不相同的 p=v u,这样 p 和 p
14、就构成了一条回路。 （ 2）因为 G 中任意两个结点都位于同一回路中，所以任意结点 u,和任意边 e 的两个端点 v1,v2 都分别在两个回路 C1， C2 中，如果 C1=C2=u v1 v2 u,那么将回路中 v1 v2,用 v1v2=e 替换，就得到新的新的回路，并满足要求。如果 C1 C2， C1=u v1 u,C2=u v2 u,那么构成新的道路 P=u v1 u v2 u,在其中将重复边剔出掉，得到新的回路 C3，其中包含 v1,v2 结点，可以将回路中 v1v2 用 v1v2=e 替换，就得到新的新的回路，并满足要求。 （ 3）对任意两条边 e1,e2 其端点分别为 u1,u2,
15、v1,v2。根据（ 2）存在回路 C1 = u1v1v2 u1,C2=u2 v1v2 u2。那么可以形成新的闭道路 P=u1 v1v2 u2v1v2 u1,在其中将重复边剔出到，得到新的回路 C3，其中包含 e2和 u1,u2 结点，可以将回路中 u1 u2 用 u1u2=e1 替换，就得到新的新的回路，包含 e1,e2,满足要求。 (4)因为任意两条边都在同一回路中，所以不存在割边。假设边 e 是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以， G 中无割边。 2.16 解： (1)deg(v1)=2、 deg(v2)=3 (2)否 (3) 4 (4)略 2.17 解： (1)A= (2) = = = V1 到 V4 长度为 1、 2、 3、 4 的路各有 1、 1、 2、 3 条。 2.18 解：无向图 G: 可达矩阵 P = 有可达矩阵可知改图为强连通图。 2.19 解： (1) 邻接矩阵 A = (2) G 中长度为 3 的通路有 23 条，其中有 7 条为回路。 (3) 图 G 为强连通图 2.20 解：邻接矩阵 A = 关联矩阵 M(G) = v1 v2 v3 v4 v5
