图论 班 姓名 学号 图论作业 1 一、填空题 1. 非同构的 4 阶和 5 阶树的个数分别为 和 。 2. n 阶 k 正则图 G 的补图的边数为 。 3. 设图 G=(n, m)中各顶点度数均为 3，且 2n=m+3，则 n= ，m= 。 4. 设简单图 G 的邻接矩阵为 A，且 2 A =         3 1 1 2 0 1 2 1 1 1 1 1 3 0 2 2 1 0 2 0 0 1 2 0 2         ， 则图 G 的边数为 。 5. 设 G 是一个完全 l 部图，ni是第 i 部分的顶点数，则它的边数为 。 6. 设 G 是 n 阶简单图，且不含完全子图 K3，则其边数一定不会超过 。 7. 设 n 阶图 G 是具有 k 个分支的森林，则其边数为 。 8. 一棵树有 ni个度数为 i 的结点，i=2,3,…,k，则它有 个度数为 1 的顶点。 9. 完全图 K5的生成树的个数为 。 二、不定项选择题 1．关于图的度序列，下列命题正确的是( ) (A) 同构的两个图的度序列相同； (B) 非负整数序列(d1, d2,…,dn)是图的度序列当且仅当 d1+d2+…+dn是偶数； (C) 如果正整数序列(d1, d2,…,dn)是一棵树的度序列且 n≥2，那么序列中至少有两个 1； (D) 正整数序列(d1, d2,…,dn)是非平凡树的度序列当且仅当 d1+d2+…+dn=2(n-1)； (E) 若图 G 的顶点度数之和大于等于图 H 的顶点度数之和，则图 G 度优于图 H； (F) 如果非负整数序列(d1, d2,…,dn)是简单图的度序列，那么在同构意义下只能确定一个图。 2. 对于序列(7, 5, 4, 3, 3, 2)，下列说法正确的是( ) (A) 可能是简单图的度序列； (B) 可能是非简单图的度序列； (C) 只能是简单图的度序列； (D) 只能是非简单图的度序列； (E) 不是任意图的度序列。 3. 下列说法错误的是( ) (A) 若一个图中存在闭途径，则一定存在圈； (B) 偶图中不存在奇圈； (C) 若图 G 不含三角形，则 G 为偶图； (D) 图的顶点之间的连通关系一定是等价关系； (E) 存在每个顶点的度数互不相同的非平凡简单图。 4. 关于简单图 G 的邻接矩阵 A，下列说法错误的是( ) (A) 矩阵 A 的行和等于该行对应顶点的度数； (B) 矩阵 A 的所有元素之和等于该图边数的 2 倍； (C) 矩阵 A 的所有特征值之和等于该图边数的 2 倍； (D) 矩阵 A 的所有特征值的平方和等于该图边数的 2 倍； 1 / 3 

图论 班 姓名 学号 (E) 矩阵 A2的主对角线上的元素之和等于该图边数的 2 倍； (F) 若 G 是非连通图，则 A 相似于某个准对角矩阵。 5. 图 G=(n, m)一定是树的是( ) (A) 连通图； (B) 无回路但添加一条边后有回路的图； (C) 每对顶点间都有路的图； (D) 连通且 m=n-1； (E) 无圈且 m=n-1。 三、解答题 1. 设无向图 G 有 10 条边，3 度与 4 度顶点各 2 个，其余顶点度数均小于 3，问 G 中至少有 几个顶点？在顶点数最少的情况下，写出 G 的度序列，该度序列是一个图序列吗？ 2. 证明整数序列(6, 3, 4, 2, 2, 5, 2)是简单图的度序列，并构造一个对应的简单图。 3. 设 G 与其补图的边数分别为 m1和 m2，求 G 的阶数。 2 / 3 

图论 班 姓名 学号 4. 设 G 为 n 阶简单图，n>2 且 n 为奇数，G 与其补图中度数为奇数的顶点个数是否相等？ 并给出理由。 5. 证明：任何一个人群中至少有两个人认识的朋友数相同。 6. 证明：若 k 正则二部图具有二分类 V=V1UV2，则|V1|=|V2|。 7. 证明：若图 G 的直径大于 3，则图 G 的补图的直径小于 3。 3 / 3