习题与解答(图论).pdf

作作业业题题与与解解答答 第十四章第十四章6 6 1616 2525 2929 4444 4545 5050 6 6 1 1 设设 n n 阶图阶图 G G 中有中有 m m 条条边边 证证明明 2 Gm nG 2 n 2 n 阶阶非非连连通通的的简简单单图图的的边边数数最最多多可可为为多多少少 最最少少呢呢 证明 证明 1 1 由由 i Gd vG 根根据据握握手手定定理理有有 1 n i i nGd vnG 得得到到 2 m GG n 2 n 2 n 阶非连通的简单图至少有阶非连通的简单图至少有 2 2 个个连连通通分分支支 边边数数最最多多的的情情 况况是是由由 K Kn 1 n 1和一个孤立点构成 它的边数为和一个孤立点构成 它的边数为 n 1 n 2 2 n 1 n 2 2 边数最少的非连通图 当然是边数最少的非连通图 当然是 n n 阶零图 边数阶零图 边数 m 0 m 0 由由 n n 个个 孤孤立立点点构构成成的的图图 1616 画画出出无无向向完完全全图图 K K4 4的的所所有有非非同同构构的的子子图图 指指出出哪哪些些是是生生成成子子图图 哪哪些些是是自自补补图图 解解 下下面面给给出出了了 K K4 4的的 1818 个个非非同同构构的的子子图图 其其中中有有 1111 个个生生成成子子图图 8 18 8 18 其中连通的有其中连通的有 6 6 个个 11 12 13 14 16 17 11 12 13 14 16 17 2525 画出 画出 5 5 阶阶 3 3 条条边边的的所所有有非非同同构构的的无无向向简简单单图图 解解 3 3 条边产生条边产生 6 6 度 分配给度 分配给 5 5 个个顶顶点点 按按简简单单图图度度数数的的要要求求 有有下下 面面 4 4 种种分分配配方方案案 1 1 1 1 1 2 2 0 1 1 2 2 1 1 1 1 1 2 2 0 1 1 2 2 3 0 1 1 1 3 4 0 0 2 2 2 3 0 1 1 1 3 4 0 0 2 2 2 在在同同构构意意义义下下 每每种种方方案案对对应应一一个个简简单单图图 4 4 个个非非同同构构的的图图如如下下 v1 v2 v4 v3 2929 设 设 G G 是是 n n 阶阶 n 1n 1 条边的无向图 证明条边的无向图 证明 G G 中存在顶点中存在顶点 v v 使得 使得 d v d v 3 3 证明证明 用用反反证证法法 假假若若不不然然 v v V G V G 均有均有 d v d v 2 2 则则由由握握手手定定理理 可得可得 2 n 1 2m 2 n 1 2m d v d v 2n 2n 其中其中 m m 为为边边数数 显显然然矛矛盾盾 所所以以结结论论成成立立 44 有向图 有向图 D D 如如图图所所示示 求求 1 D 1 D 中中 V V1 1到到 V V4 4长度为长度为 1 2 3 41 2 3 4 的的通通路路各各为为几几条条 2 D 2 D 中中 V V1 1到到 V V1 1长度为长度为 1 2 3 41 2 3 4 的的回回路路各各为为几几条条 3 D 3 D 中长度为中长度为 4 4 的的通通路路有有多多少少条条 其其中中长长为为 4 4 的的回回路路多多少少条条 4 D 4 D 中长度小于等于中长度小于等于 4 4 的的通通路路有有多多少少条条 其其中中有有多多少少条条为为回回路路 5 5 写出写出 D D 的的可可达达矩矩阵阵 解 解 只要求出只要求出 D D 的邻接矩阵的的邻接矩阵的 4 4 次次幂幂即即可可 A A 0100 1001 0100 0021 A A 2 2 1001 0121 1001 0221 v1 v2 v4 v3 v5 A A 3 3 0121 1222 0121 2223 A A 4 4 1222 2344 1222 2465 1 D 1 D 中中 V V1 1到到 V V4 4长度为长度为 1 2 3 41 2 3 4 的通路分别为的通路分别为 0 0 0 0 2 2 2 2 2 D 2 D 中中 V V1 1到到 V V1 1长度为长度为 1 2 3 41 2 3 4 的回路分别为的回路分别为 1 1 1 1 3 3 5 5 3 D 3 D 中长度为中长度为 4 4 的通路有的通路有 4444 条 其中长为条 其中长为 4 4 的回路的回路 1111 条条 4 D 4 D 中长度小于等于中长度小于等于 4 4 的通路共的通路共 8888 条条 即即 A AA A 2 2 A A 3 3 A A 4 4 中中元元素素之之和和 其中有其中有 22 22 即即 A AA A 2 2 A A 3 3 A A 4 4 中中所所有有对对角角元元素素之之和和 条条是是回回路路 5 5 因为因为 D D 中中存存在在经经过过所所有有顶顶点点的的回回路路 是是强强连连通通图图 所所以以可可达达矩矩阵阵 为为 4 4 阶元素全是阶元素全是 1 1 的的方方阵阵 4545 有向图 有向图 D D 如如图图所所示示 求求 1 v 1 v2 2到到 v v5 5长度为长度为 1 2 3 41 2 3 4 的的通通路路数数 2 v 2 v5 5到到 v v5 5长度为长度为 1 2 3 41 2 3 4 的的回回路路数数 3 D 3 D 中长度为中长度为 4 4 的通路数的通路数 含回路含回路 4 D 4 D 中中长长度度小小于于或或等等于于为为 4 4 的的回回路路数数 5 5 写出写出 D D 的的可可达达矩矩阵阵 解解 只要求出只要求出 D D 的邻接矩阵的的邻接矩阵的 4 4 次次幂幂即即可可 A A 00001 10100 00001 10100 01010 A A 2 2 01010 00002 01010 00002 20200 A A 3 3 20200 02020 20200 02020 00004 A A 4 4 00004 40400 00004 40400 04040 1 v 1 v2 2到到 v v5 5长度为长度为 1 2 3 41 2 3 4 的的通通路路数数分分别别为为 a a25 25 1 1 0 a 0 a25 25 2 2 2 2 条条 a a25 25 3 3 0 0 条条 a a25 25 4 4 0 0 条条 2 v 2 v5 5到到 v v5 5长度为长度为 1 2 3 41 2 3 4 的的回回路路数数分分别别为为 a a55 55 1 1 0 a 0 a55 55 2 2 0 0 条条 a a55 55 3 3 4 4 条条 a a55 55 4 4 0 0 条条 3 D 3 D 中长度为中长度为 4 4 的通路数的通路数 含回路含回路 即即 A A 4 4 中元素之和中元素之和 为为 3232 条条 4 D 4 D 中长度小于或等于为中长度小于或等于为 4 4 的回路数为的回路数为 即为即为 A AA A 2 2 A A 3 3 A A 4 4 中中对对角角 元素之和元素之和 12 12 条条 5 D 5 D 是是强强连连通通的的 所所以以可可达达矩矩阵阵为为元元素素全全为为 1 1 的的 5 5 阶阶方方阵阵 5050 设 设 G G 是是 6 6 阶阶无无向向简简单单图图 证证明明 G G 或或它它的的补补图图G中存在中存在 3 3 个个顶顶点点彼彼此此 相相邻邻 证明证明 取取一一个个顶顶点点 v v1 1 由由鸽鸽巢巢原原理理 v v1 1至少关联至少关联 3 3 条条 G G 中中的的边边 或或至至少少 关联关联 3 3 条条G中中的的边边 不不妨妨设设 v v1 1至少关联至少关联 3 3 条条 G G 中中的的边边 设设这这 3 3 条条边边的的 另另一一个个端端点点分分别别为为 v v2 2 v v3 3 v v4 4 如图如图 a a 所所示示 再再对对 v v2 2 v v3 3 v v4 4之之间间的的邻邻 接接关关系系进进行行讨讨论论 1 1 若若 v v2 2 v v3 3 v v3 3 v v4 4 v v2 2 v v4 4 中有一条是中有一条是 G G 的边 则在的边 则在 G G 中有中有 3 3 个顶点彼此相邻 如图个顶点彼此相邻 如图 b c d b c d 所所示示 2 2