《湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学.pdf》由会员分享，可在线阅读，更多相关《湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学.pdf（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、习 题 六 1.设 G 是 一 个 无 回 路 的 图，求 证：若 G 中 任 意 两 个 顶 点 间 有 惟 一 的 通 路，则 G 是 树.证 明：由 假 设 知，G 是 一 个 无 回 路 的 连 通 图，故 G 是 树。2.证 明：非 平 凡 树 的 最 长 通 路 的 起 点 和 终 点 均 为 悬 挂 点.分 析：利 用 最 长 通 路 的 性 质 可 证。证 明：设 尸 是 树 T 中 的 极 长 通 路。若 P 的 起 点 v满 足 d(v)l,则 P 不 是 T 中 极 长 的 通 路。对 终 点 M也 可 同 理 讨 论。故 结 论 成 立。3.证 明：恰 有 两 个 悬
2、挂 点 的 树 是 一 条 通 路.分 析：因 为 树 是 连 通 没 有 回 路 的，所 以 树 中 至 少 存 在 一 条 通 路 P。因 此 只 需 证 明 恰 有 两 个 悬 挂 点 的 树 中 的 所 有 的 点 都 在 这 条 通 路 P 中 即 可。证 明：设,v是 树 T 中 的 两 个 悬 挂 点，即 d()=d(v)=l。因 T 是 树，所 以 存 在(“,v)-通 路 P-uw-wkv,k 0,显 然，d(wi)2 o 若 d(叫)2,则 由 T 恰 有 两 个 悬 挂 点 的 假 设，可 知 T 中 有 回 路；若 T 中 还 有 顶 点 x不 在 尸 中，则 存 在(
3、,x)-通 路，显 然 与 x 不 邻 接,且 4(x)2 2。于 是，可 推 得 T 中 有 回 路，矛 盾。故 结 论 成 立。4.设 G 是 树，A(G)J l,求 证：G 中 至 少 有 个 悬 挂 点.分 析：由 于 A(G)2 Z,所 以 G 中 至 少 存 在 一 个 顶 点 v 的 度 2 k,于 是 至 少 有 k 个 顶 点 与 邻 接，又 G是 树，所 以 G中 没 有 回 路，因 此 与 v邻 接 的 点 往 外 延 伸 出 去 的 分 支 中，每 个 分 支 的 最 后 一 个 顶 点 必 定 是 一 个 悬 挂 点，因 此 G 中 至 少 有 k个 悬 挂 点。证
4、明：设 e V(G),且 d(“)2 机 2 攵。于 是，存 在 匕，%e V(G),使“匕 w E(G),i=1,，机。若 匕 不 是 悬 挂 点，则 有 匕 e V(G),使。如 此 下 去，有 甲 G V(G),满 足 匕 j,且 d(匕)=1,i=l,，*故 G 中 至 少 有 人 个 悬 挂 点。5.设 G(p,q)是 一 个 图，求 证：若 q N p,则 G 中 必 含 回 路.分 析：利 用 树 是 没 有 回 路 且 连 通 的 图，且 树 中 的 顶 点 数 和 边 数 的 关 系 可 证。证 明：设 G(p,q)有&个 分 支:GM=G(P,q),G M k G K p*
5、/)。显 然，p=Pi+q=0+外。若 G 无 回 路，则 每 个 G,.(,/)均 是 树，i=l,，攵。于 是 q,=Pj-1,/=1,k。从 而 q=p-k p,k N 1,即 q p 此 为 矛 盾，故 G 必 含 回 路。6.设 G(p,q)是 有 A 个 连 通 分 支 的 图，求 证：G 是 森 林 当 且 仅 当?=p-h证 明：见 题 5的 证 明。7.画 出 K 4的 所 有 16棵 生 成 树.解，K 4的 所 有 16棵 生 成 树 如 下 图 所 示。8.设 G（p,q）是 连 通 图，求 证：?/?-1.分 析：树 应 该 是 具 有 p 个 顶 点 中 边 数 最
6、 少 的 连 通 图，而 树 中 的 边 数 q=p-l可 证。证 明：设 G 是 连 通 图。若 G 无 回 路，则 G 是 树，于 是 q=p-l。若 G 有 回 路，则 删 去 G 中 女 0 条 边 使 之 保 持 连 通 且 无 回 路。于 是 q k=p l,即 4=1+p 1。9.递 推 计 算 K2.3的 生 成 树 数 目.+10.通 过 考 虑 树 中 的 最 长 通 路，直 接 验 证 有 标 记 的 5 个 顶 点 的 树 的 总 数 为 125.分 析：设 树 中 5 个 顶 点 的 标 记 分 别 为 1,2,3,4,5。而 5 个 顶 点 的 树 的 最 长 通
7、路 只 能 是 4、3、2,如 下(1)(2)(3)所 示。(1)Q_ Q_Q_Q_Q 最 长 通 路 长 度 为 4；(2)Q _ Q _Q _Q 最 长 通 路 长 度 为 3：(3)最 长 通 路 长 度 为 2。对 于(1),把 每 个 顶 点 看 作 是 一 个 空,不 同 的 顶 点 序 列 对 应 不 同 的 树,但 由 于 对 称 性 12345和 54321所 形 成 的 树 应 该 是 同 一棵 树，因 此 这 种 情 况 下 所 有 有 标 记 的 树 的 数 目 为：5!/2=60个；对 于(2),把 上 面 四 个 顶 点 分 别 看 作 个 空，在 构 造 树 的
8、时 候 可 以 先 构 造 这 四 个 顶 点，剩 下 的 一 个 顶 点 只 能 放 在 下 面，选 择 上 面 四 个 顶 点 的 数 目 应 为 可 以 从 所 有 有 标 记 的 树 的 数 目 为*4!,但 同 样 由 对 称 性，如 1234这 样 的 排 列 和 顶 点 5 构 成 的 树 与 1235这 样 的 排 列 和 4 构 成 的 数 是 一 样 的。因 此 这 种 情 况 下 所 有 有 标 记 的 树 的 数 目 为：。；*4!/2=60个；对 于(3),只 要 确 定 了 中 间 度 为 4 的 顶 点，这 棵 树 就 构 造 完 了，所 有 这 种 情 况 下
9、有 标 记 的 树 的 数目 为：C；=5 个；解：有 标 记 的 5 个 顶 点 的 树 的 总 数 为：60+60+5=125个。11.用 丁()表 示 个 顶 点 的 有 标 记 树 的 个 数，求 证：2(一 M()=WM 一 攵 方 G T(一 女 口=1由 此 得 恒 等 式“一 1 T(一 k/i C：=2(一 1)户 k=分 析：每 个 n 阶 树 可 由 下 面 的 方 法 构 造 出 来：先 从 这 n 个 顶 点 中 任 取 k 个 顶 点 构 造 出 一 个 k 阶 树,对 剩 下 的 n-k个 顶 点 构 造 出 一 个 n-k阶 树，再 将 这 两 个 树 合 并
10、成 一 个 树，显 然 这 样 得 到 的 树 是 一 个 n 阶 的 树。又 由 定 理 6.2.4有 i个 顶 点 的 无 标 记 的 生 成 树 共 有 产 个，可 得 下 面 的 证 明。证 明：任 取 k 个 顶 点 的 一 棵 k 阶 树 与(n-k)个 顶 点 构 成 的 n-k阶 树 之 间 连 接 两 点 就 是 一 棵 n 阶 树,这 里 有 k(n-k)种 连 接。并 注 意 到 一 来 一 往 每 条 边 用 了 两 次,因 此，k(n-k)T(k)T(n-k)Cnk=2T(n)。/I-1上 式 两 边 对 k 从 1 到 n-1 求 和,得 2(一 1)T()=2 乂
11、 k)T(k)T(-k)C。再 将 T(n)=泌-2,k=lT(k)=kk-2,T(n-k)=(n-k)n-k-2,代 入 上 式 便 可 得 恒 等 式：n-1 卜 5-1(产 七：=2(-1)”？k=12.如 何 用 Kruskal算 法 求 赋 权 连 通 图 的 权 最 大 的 生 成 树(称 为 最 大 树)？证 明：将 Kruskal算 法 中 的“小”改 成“大”即 可 得 到“最 大 树”。13.设 G 是 一 个 赋 权 连 通 图，V(G)=1,2,-,H,/?2.求 证：按 下 列 步 骤(Prim算 法)可 以 得 出 G 的 一 个 最 优 树.(z)置 U:=1,T
12、:=0；(ii)选 取 满 足 条 件 i e U,j e V(G)U 且 C(i,J)最 小 的(i,j)；(nz)T:Tji,j,U：=U j j；(iv)若 U*V(G)则 转(ii),否 则 停 止，T 中 的 边 就 是 最 优 树 的 边.解：设 T*是 按 Prim算 法 得 出 的 图。由 Prim算 法 的 初 值 及 终 止 条 件，可 知 T*连 通，且 T*为 G 的 生 成 子 图。又 由(ii)知 T*无 回 路。故 T*是 生 成 树。(2)设 T(G)=TIT是 G 的 生 成 树，T H T*,仿 定 理 631的 证 明，可 证 结 论 成 立。14.按 题
13、 13的 Prim算 法，求 出 图 6.9 的 最 优 树.解：最 优 树 如 下。(权 为 20)习 题 七 1.对 图 7.7中 的 两 个 图，各 作 出 两 个 顶 点 割。图 7.7解：对 图 7.7增 加 加 节 点 标 记 如 下 图 所 示，则 的 两 个 顶 点 割 为：Vll=a,b；V12=c,d(b)的 两 个 顶 点 割 为：V21=u,v；V12=yy2.求 图 7.7中 两 个 图 的 K(G)和/l(G).解:如 上 两 个 图，有 k(G l)=入(G l)=2,k(G 2)=l,入(G2)=23.试 作 出 一 个 连 通 图 G,使 之 满 足：K(G)
14、=/1(G)=3(G)解：做 连 通 图 G 如 下，于 是 有：Z(G)=G)=S(G)4.求 证，若 G(p,q)是 6-边 连 通 的,则”即/2.证 明：设 G 是 k边 连 通 的，由 定 义 有 人(G)M k.又 由 定 理 7.1.2知 入(G)W 努 此 有 k至 入(G)=1/，/即 kS 2 y,从 而 q”/。5.求 证,若 G 是 除 简 单 图，且 b(G)N p-2,则 K(G)=b(G).分 析：由 G 是 简 单 图，且 b(G)N p-2,可 知 G 中 的 6(G)只 能 等 于 p-1或 p-2；如 6(G)=p-l,则 G 是 一 个 完 全 图，根
15、据 书 中 规 定，有 k(G)=p-l=6(G)；如 6(G)=p-2，则 从 G 中 任 取 V(G)的 子 集 V I,其 中 V ll=3,贝 UV(G)-V1的 点 导 出 子 图 是 连 通 的，否 则 在 V I中 存 在 一 个 顶 点 v,与 其 他 两 个 顶 点 都 不 连 通。则 在 G 中，顶 点 v 最 多 与 G 中 其 他 p-3个 顶 点 邻 接，所 以 d(v)W p-3,与 6(G)=p-2矛 盾。这 说 明 了 在 G 中，去 掉 任 意 p-3个 顶 点 后 G还 是 连 通 的，按 照 点 连 通 度 的 定 义 有 k(G)k-3,又 根 据 定
16、义 7.1.1,K(G K b(G),有 k(G)=k-2o证 明：因 为 G 是 简 单 图，所 以 d(v)Wp一 l,veV(G),已 知 6(G)叁 p-2(i)若 3(G)=p-l,则 G=Kp(完 全 图)，故 k(G)=p-l=6(G)。(i i)若 8(G)=p-2,则 GWKp,设 u,v不 邻 接，但 对 任 意 的 w W V(G),有 uw,vw CE(G).于 是，对 任 意 的 V lq V(G),IVll=p-3,G-V1 必 连 通.因 此 必 有 k(G)Mp-2=6(G),但 k(G)叁 6(G)。故 k(G)=8(G)。6.找 出 一 个。阶 简 单 图，
17、使 3(G)=p 3,但 K(G)*G).解：如 图 G,p=5(G)=2=p 3,K(G)=l b(G)。G7.设 G 为 3-正 则 简 单 图,求 证 K(G)=X(G).分 析：G 是 一 个 3 正 则 简 单 图，所 以 6(G)=3,根 据 定 理 7.1.1有 K(GK/1(GKMG),所 以 K(G)只 能 等 于 0,1,2,3 这 四 种 情 况。下 面 的 证 明 中 分 别 讨 论 了 这 四 种 情 况 卜 K(G)和 刈 G)的 关 系。证 明：(1)若 K(G)=0,则 G 不 连 通，所 以 A(G)=K(G).(2)设 K(G)=1,且 u 是 G 中 的
18、一-个 割 点，G-u不 连 通，由 于 d(u)=3,从 而 至 少 存 在 一 个 分 支 仅 一 边 与 u 相 连，显 然 这 边 是 G 的 割 边，故 X(G)=1,所 以 入(G)=K(G)(3)设 K(G)=2,且 vl,v2 为 G 的 一 个 顶 点 割.Gl=G-vl连 通，则 v2是 G 1 的 割 点 且 v2在 G 1 中 的 度 小 于 等 于 3,类 似 于(2)知 在 G 1 中 存 在 一 割 边 e2(关 联 v2)使 得 Gl-e2不 连 通.另 一 方 面 由 于 A(G)=K(G)=2故 G c 2 连 通.由 于 Glv2=(G-e2)-vl,故
19、vl是 G-e2的 割 点，且 vl在 G-e2中 的 度 小 于 等 于 3,于 是 类 似 于 知，在 G-e2中 存 在 一 割 边 el,即(G-e2)-el=G-el,e2)不 连 通,故 人(G)=2.所 以 X(G)=K(G).(4)设 k(G)=3,于 是,有 3=k(G)W G)W 6(G)=3,知 K(G)=2(G)=38.证 明：一 个 图 G 是 2-边 连 通 的 当 且 仅 当 G 的 任 意 两 个 顶 点 由 至 少 两 条 边 不 重 的 通 路 所 连 通.分 析：这 个 题 的 证 明 关 键 是 理 解 2-边 连 通 的 定 义。证 明：(必 要 性)
20、因 为 G 是 2-边 连 通 的，所 以 G 没 有 割 边。设 u,v 是 G 中 任 意 两 个 顶 点,由 G 的 连 通 性 知 u,v 之 间 存 在 一 条 路 径 P1,若 还 存 在 从 u 到 v 的 与 P1边 不 重 的 路 径 P2,设 C=P1UP2,则 C 中 含 u,v的 回 路，若 从 u 到 v 的 任 意 另 外 路 径 和 P1都 有 一 条(或 几 条)公 共 边，也 就 是 存 在 边 e 在 从 u 到 v 的 任 何 路 径 中，则 从 G 中 删 除 e,G 就 不 连 通 了，于 是 e 成 了 G 中 一 割 边，矛 盾。(充 分 性)假
21、设 G 不 是 一 个 2-边 连 通 的，则 G 中 有 割 边，设 e=(u,v)为 G 中 一 割 边，由 已 知 条 件 可 知，u 与 v 处 于 同 一 简 单 回 路 C 中，于 是 e 处 在 C 中，因 而 从 G 中 删 除 e 后 G 仍 然 连 通，这 与 G 中 无 割 边 矛 盾。9.举 例 说 明：若 在 2-连 通 图 G 中，P 是 一 条 通 路，则 G 不 一 定 包 含 一 条 与 P 内 部 不 相 交 的(,。)一 通 路 Q。G解 如 右 图 G,易 知 G 是 2连 通 的,若 取 P 为 uvlv2v,则 G 中 不 存 在 Q 了。10.证
22、明：若 G 中 无 长 度 为 偶 数 的 回 路，则 G 的 每 个 块 或 者 是 2,或 者 是 长 度 为 奇 数 的 回 路.分 析：块 是 G 的 一 个 连 通 的 极 大 不 可 分 子 图，按 照 不 可 分 图 的 定 义，有 G 的 每 个 块 应 该 是 没 有 割 点 的。因 此，如 果 能 证 明 G 的 某 个 块 如 果 既 不 是 K?,也 不 是 长 度 为 奇 数 的 回 路，再 由 已 知 条 件 G 中 无 长 度 为 偶 数 的 回 路，则 可 得 出 G 的 这 个 块 肯 定 存 在 割 点，则 可 导 出 矛 盾。本 题 使 用 反 证 法。证
23、 明：设 K 是 G 的 一 个 块，若 k 既 不 是 K 2也 不 是 奇 回 路，则 k 至 少 有 三 个 顶 点，且 存 在 割 边 e=uv,于 是 u,v中 必 有 一 个 是 割 点，此 与 k 是 块 相 矛 盾。11.证 明：不 是 块 的 连 通 图 G 至 少 有 两 个 块，其 中 每 个 块 恰 含 一 个 割 点.分 析：一 个 图 不 是 块，按 照 块 的 定 义，这 个 图 肯 定 含 有 割 点 v,对 图 分 块 的 时 候 也 应 该 以 割 点 为 标 准 进 行，而 且 分 得 的 块 中 必 定 含 这 个 割 点，否 则 所 得 到 的 子 图
24、 一 定 不 是 极 大 不 可 分 子 图，从 而 不 会 是 一 个 块。证 明：由 块 的 定 义 知，若 图 G 不 是 块 且 连 通，则 G 有 割 点，依 次 在 有 割 点 的 地 方 将 G 分 解 成 块，一 个 割 点 可 分 成 两 块，每 个 块 中 含 G 中 的 一 个 割 点。如 下 图 G。易 知 u,v是 割 点，G 可 分 成 四 个 块 K I-K 4。其 中 每 个 块 恰 含 一 个 割 点。1 2.证 明：图 G 中 块 的 数 目 等 于（G）+1）其 中，M。）表 示 包 含 0 的 块 的 数 目.ueV（G）分 析：一 个 图 G 的 非
25、割 点 只 能 分 布 在 G 的 一 个 块 中，即 乂。）=1（当 v 是 G 的 非 割 点 时），且 每 个 块 至 少 包 含 一 个 割 点。因 此 卜 面 就 从 G 的 割 点 入 手 进 行 证 明。证 明 中 使 用 了 归 纳 法。证 明：先 考 虑 G 是 连 通 的 情 况(1)结 论 ueV(G)成 立。假 设 G 中 的 割 点 数 nWk(k20)时:结 论 成 立。Xj n=k+l的 情 况，任 取 G 的 一 个 割 点 a,可 将 G 分 解 为 连 通 子 图 G,使 得 a在 Gj中 不 是 割 点，a又 是 G 的 公 共 点。这 样，每 一 个 G
26、,有 且 仅 有 一 个 块 含 有 a,若 这 些 G 共 有 r个，则 b(a)=r,又 显 然 Gi的 块 也 是 G 的 块，且 Gi的 割 点 数 力 W k。故 由 归 纳 法 假 设 Gi的 块 的 块 数 为 1+Z 0,厂)，这 里 历 是 G 中 含 v 的 块 的 块 数，注 意 到 G 中 异 于 a 的 v,oeV(Gi)b(v)=&(v),而 a 在 每 一 个 Gi中 均 为 非 割 点，故)(a)(i=l,2,/)。于 是 Gj的 块 数 为 1+Z(b()-l)(i=l,2,/)UV(Gi)va将 所 有 G 的 块 全 部 加 起 来，则 得 到 G 的 块
27、 数 为：r+Z3(o)T)=r+Z(M)l)=l+(r-l)+(&(t?)-l)=l+(贴 1)i=l L eV(G)t w V(G)DWV(G)ueV(G)va va va由 归 纳 法 可 知，当 G 连 通 时，结 论 成 立。当 G 不 连 通 时，对 每 个 连 通 分 支 上 述 结 论 显 然 成 立。因 此 有 图 G 中 块 的 数 目 等 于 0(G)+Z(W o)T)veV(G)13.给 出 一 个 求 图 的 块 的 好 算 法。分 析：设 G 是 一 个 具 有 p 个 顶 点，q 条 边，w 个 连 通 分 支 的 图。求 图 G 的 块 可 先 求 图 G 的
28、任 一 生 成 森 林 F,且 对 每 一 边 e g F,求 F+e中 的 唯 一 回 路，设 这 些 回 路 Cl,C 2,，Cq俨、,都 已 求 得，(这 些 都 有 好 算 法)。在 此 基 础 上，我 们 注 意 到，两 个 回 路(或 一 个 回 路 与 一 个 块)若 有 多 于 1个 公 共 点，则 它 们 属 于 同 一 块。此 外，由 割 边 的 定 义 知，G 的 任 一 割 边 不 含 于 任 何 回 路 中，且 它 们 都 是 G 的 块。基 于 这 些 道 理，可 得 如 下 求 图 G 的 块 的 好 算 法。解：求 图 的 块 的 算 法：(1)令 s=l,t=
29、L n=q-p+w(2)若 n0,输 入 Cl,C2,Cn；否 则，转 第 4 步。(3)若 IV(Cs)cV(C,+,)l l,令 Cs=C s D C,且 对 i=s+t,，n-1,令C,=c,.+1,n=n-l,转 第 4 步；否 则，t=t+l,转 第 5 步。(4)若 sn,令 t=l,转 第 3 步；否 则，算 法 停 止(这 时 Cl,C2,，g 与 E(G)-C1,C2,，&中 的 每 一 边 都 是 G 的 块)(5)若 s+t n 转 第 3步；否 则，s=s+l,转 第 4 步。本 算 法 除 了 求 回 路 有 已 知 的 好 算 法 外，计 算 量 主 要 在 第 3
30、 步，比 较 C,与 的 顶 点 寻 找 它 们 的 公 共 点 的 运 算 中，这 些 运 算 不 超 出 p2*(q-p+w)次，故 是 好 算 法。14.证 明：”2用,0是+1)-连 通 的。分 析：只 要 证 明“2川 邛 不 存 在 少 于*+1个 顶 点 的 顶 点 割 集。设 V是 一 个 IVk2r+l的 任 一 顶 点 子 集，可 分 W k 2r和 I Vl=2r两 种 情 形 证 明。证 明：(1)当 IVk 2r时，根 据 定 理 7.3.1的 证 明，V不 是“2”的 顶 点 割 集，当 然 更 不 是 在 上 加 些 边 的 的 顶 点 割 集。(2)当 1=2
31、厂 时，设 H 是“2,+3的 顶 点 割 集，i，/属 于“2%V 的 不 同 分 支。考 察 顶 点 集 合 和 T j,j+,.,i-1,i 这 里 加 法 取 模 若 S 或 T 中 有 一 个 含 V，的 顶 点 少 于 r个,则 在“2川 w-V中 存 在 从 到 j 的 路。与 V为 顶 点 割 集 矛 盾。若 S 和 T 中 都 有 V，的 r个 顶 点，则：若 S 或 T 中，有 一 个(不 妨 说 S)中 V,的 r个 顶 点 不 是 相 继 连 成 段，则 S-H 中 存 在 从 i到)的 路。与 V为 顶 点 割 集 矛 盾。若 S 与 T 中，V的 7 个 顶 点 都
32、 是 相 继 连 成 一 段 的。若 S 与 T 中 至 少 有 一 个 没 有 被 分 成 两 段，则 立 即 与 V，为 顶 点 割 集 矛 盾；若 S-V，被 分 成 两 段：含 i的 记 加，含/的 记 S2，且 T-H 也 被 分 为 两 段：含 i的 记 小 含/的 记 小 这 样，被 分 为 两 段：含 i的 S|U(和 含/的 S 2 U T 2。这 两 段 都 是 连 通 的，且 含，段 的 中 间 点（或 最 靠 近 中 间 的 点），0与 含，段 的 类 似 点 Jo满 足：/0+-（为 偶 数）io+三n+一 l（为 奇 数）故 io与 A 有 边 相 连，在”2川,-
33、V 中 有 路。，o,Jo”，/），与 V为 顶 点 割 集 矛 盾。综 上 所 述，“2川，是（2厂+1）连 通 的。15.证 明：/c（Hm n）=A（Hmil）=m.分 析：根 据 定 理 7.3.1,图“是 m-连 通 图，因 此 有 K（/,）=m又 根 据 的 构 造，可 知 8（H Q=m,再 由 定 理 7.1.1可 证。证 明：由 定 理 7.3.1知：K（H 必）=m已 知：k W 入=5而 b（Hmi）=机.因 此:m=k A 8=m.故 4（/,）=m,16.试 画 出“4 8、“5 8 和”,9分 析：根 据 书 上 第 54页 构 造“凡 的 方 法 可 构 造 出
34、“4.8、”5.8和“5.9。（i）4.8：r=2,p=8,对 任 意 ij e V（/74 8）,I i-j|Wr 或 者”心 r,其 中,p=O,j=7,6i=8,j=7,6则 4 s 如 下 图：i=i(mod p),j 三 j(mod/?).“4,8 图(ii)“58图：r=2,p=8,则 在 兄 8中 添 加 连 接 顶 点 i 与 i+p/2(modp)的 边，其 中 1近 0 2,.15;2-*6;3 f 7;4 f o.则“5.8 图 如 下(iii)so 图:匚 2,在 出.9图 上 添 加 连 接 顶 点 0 与(p-1)/2和(p+1)/2的 边，以 及 顶 点 i 与
35、i+(p+1)/2(modp)的 边，其 中 1W i(p-1)/2.z=0,j=8,7 f=9,/=8,7.,.0-4;0 f 5;则”5.9图 如 下:i=l,j-8j=1 0,/=81-6;2 f 7;3-8.“5.9 图习 题 8i、图 中 8.10中 哪 些 是 E 图？哪 些 是 半 E 图？分 析：根 据 欧 拉 定 理 及 其 推 论，E 图 是 不 含 任 何 奇 点 的 图，半 E 图 是 最 多 含 两 个 奇 点 的 图。解：（a）半 E 图。（b）E 图。（c）非 半 E 图 和 E 图 2、试 作 出 一 个 E 图 G（p,q）,使 得 p 与 q 均 为 奇 数
36、。能 否 作 出 一 个 E 图 G（p,q）,使 得 p 为 偶 数，而 q为 奇 数？如 果 是 p 为 奇 数，q 为 偶 数 呢?解：以 下 E 图 中，p 与 q 的 奇 偶 如 卜 表 P qG1奇 数 奇 数 G2 偶 数 奇 数 G3 奇 数 偶 数 3、求 证：若 G 是 E 图，则 G 的 每 个 块 也 是 E 图。分 析：一 个 图 如 果 含 有 E 回 路，则 该 图 是 E 图；另 一 方 面 一 个 块 是 G 中 不 含 割 点 的 极 大 连 通 不 可 分 子 图，且 非 割 点 不 可 能 属 于 两 个 或 两 个 以 上 的 块。这 样 沿 G 中
37、的 一 条 E 回 路 遍 历 G 的 所 有 边 时，从 一 个 块 到 达 另 一 个 块 时，只 能 经 过 割 点 才 能 实 现。证 明：设 B 是 G 的 块，任 取 G 中 一 条 E 回 路 C,由 B 中 的 某 一 点 v 出 发，沿 C 前 进，C 只 有 经 过 G 的 割 点 才 能 离 开 B,也 就 是 说 只 有 经 过 同 一 个 割 点 才 能 回 到 B 中，注 意 到 这 个 事 实 后，我 们 将 C 中 属 于 B 外 的 一 个 个 闭 笔 回 路 除 去，最 后 回 到 v 时，我 们 得 到 的 就 是 B 上 的 一 个 E 回 路，所 以
38、B 也 是 E 图。4、求 证：若 G 无 奇 点，则 G 中 存 在 边 互 不 重 的 回 路 G.,使 得 E(G)=E(C,)U E(C2)U.-U(C J分 析：G 中 无 奇 点，则 除 了 孤 立 点 后 其 他 所 有 点 的 度 至 少 为 2,而 孤 立 点 不 与 任 何 边 关 联，因 此 在 分 析 由 边 构 成 的 回 路 时 可 以 不 加 考 虑；而 如 果 个 图 所 有 的 顶 点 的 度 至 少 为 2,则 由 第 五 章 习 题 18知 该 图 必 含 回 路。证 明：将 G 中 孤 立 点 去 掉 以 后 得 到 图 G 1,显 然 G I 也 是
39、一 个 无 奇 点 的 E 图，且 6(G1)N2。由 第 五 章 习 题 18知，G 1 必 含 有 回 路 C1；在 图 G1-C1中 去 掉 孤 立 点，得 图 G 2,显 然 G 2 仍 然 是 一 个 无 奇 点 的 图，且 b(G2)N2,于 是 G 2 中 也 必 含 回 路 C2,如 此 直 至 I G m 中 有 回 路 Cm,且 Gm-Cm全 为 孤 立 点 为 止，于 是 有：(G)=(C,)u(C2)5 U E(C,)5、求 证：若 G 有 2k0个 奇 点，则 G 中 存 在 k 个 边 互 不 重 的 链 Qk,使 得：(G)=E(e,)uE(e2)u-uE(e,)
40、分 析：一 个 图 的 E 回 路 去 掉 一 条 边 以 后，将 得 到 一 条 E 链。证 明：设 匕 匕，匕，匕+1，匕 人 为 G 中 的 奇 数 度 顶 点，k l在 Vi和 Vi+k之 间 用 新 边 ei连 接，i=l,2.k,所 得 之 图 记 为 G*,易 知 G*的 每 个 顶 点 均 为 偶 数，从 而 G*存 在 E 闭 链 C*。现 从 C*中 删 去 ei(i=l,2.k),则 C*被 分 解 成 k 条 不 相 交 的 链 Qi(i=l,2.k),显 然 有：E(G)=)u E(Q2)U-U E(2,)6、证 明：如 果(1)G 不 是 2连 通 图，或 者(2)
41、G 是 二 分 图 vX,Y,且 X#Y,则 G 不 是 H 图。分 析：G 不 是 2连 通 图，说 明 K G)，于 是 K(G)=1或 K(G)=0,如 果 K(G)=O,则 说 明 G不 连 通，如 G 不 连 通，显 然 G 不 是 H 图，如 K(G)=1则 G 中 存 在 孤 立 点，因 此 有 3(G-V)2,由 定 理 821G不 是 H 图。若 G 是 二 分 图 6,Y,则 X 或 Y 中 的 任 意 两 个 顶 点 不 邻 接，因 此 G-X剩 下 的 是 Y 中 的 点，这 些 点 都 是 孤 立 点；同 样 G-Y剩 下 的 是 X 中 的 点，这 些 点 也 是
42、孤 立 点；即 有。(G-X)=M,以 G Y)=IXI,如 果*彳 丫，则 有。(G X)=IYI IXI或 0(G Y)=IXIIH成 立。无 论 哪 个 结 论 成 立，根 据 定 理 8.2.1都 有 G 不 是 H 图。证 明：若(1)成 立 则 G 不 连 通 或 者 是 G 有 割 点 u,若 G 不 连 通，则 G 不 是 H 图，若 G 有 割 点 u,WS=u,于 是 3(G-u)S因 此 G 不 是 H 图.若(2)成 立,不 妨 设 凶|x|=|s|即：co(G-5)|S|.因 此 G 不 是 H 图.7、证 明：若 G 是 半 H 图 则 对 于 V(G)的 每 一
43、个 真 子 集 S,有：(G S)W|S|+1.分 析：图 G 的 权 与 它 的 生 成 子 图 5 勺 连 通 分 支 数 满 足：&(G)W以 G)因 为 一 个 图 的 生 成 子 图 是 在 该 图 的 基 础 上 去 掉 若 干 边 得 到 的，显 然 去 掉 边 以 后 只 能 使 该 图 的 连 通 分 支 增 加。对 于 图 G 的 一 条 H 通 路 C,满 足 任 取 S u V,。(。S)W|S|+L证 明:设 C 是 G 的 一 条 H 通 路，任 取 S u V,易 知 6?(C_5)|S|+1.而 C-S 是 G-S 的 生 成 子 图.故。(G S)(C S)(
44、|S|+1.故 0(G-S)W|S|+1.8、试 述 H 图 与 E 图 之 间 的 关 系。分 析：H 图 是 指 存 在 一 条 从 某 个 点 出 发 经 过 其 他 顶 点 有 且 仅 有 一 次 的 回 路：而 E 图 是 指 从 某 点 出 发 通 过 图 中 所 有 的 边 一 次 且 仅 有 一 次 的 回 路。从 定 义 可 看 出，这 两 者 之 间 没 有 充 分 或 必 要 的 关 系。解：考 虑 如 下 四 个 图：易 知 G 1 是 E 图，但 非 H 图;G 2 是 H 图，但 非 E 图;G 3 既 非 E 图，又 非 H 图；G 4 既 是 E 图，也 是 H
45、 图。9、作 一 个 图，它 的 闭 包 不 是 完 全 图 分 析：一 个 p 阶 图 的 闭 包 是 指 对 G 中 满 足 d(u)+d(v)与 p 的 顶 点 u,v,若 uveE(G),则 将 边 uv加 到 G 中，得 到 G+uv,如 此 反 复 加 边，直 到 满 足 d(u)+d(v)与 p 的 所 有 顶 点 均 邻 接。由 闭 包 的 定 义，如 果 一 个 图 本 身 不 存 在 任 何 一 对 顶 点 u,v,满 足 d(u)+i(v)p,则 它 的 闭 包 就 是 其 自 身。显 然 可 找 到 满 足 这 种 条 件 的 非 完 全 图。解：如 右 图 G,G=G
46、,但 G 不 是 完 全 图。G10、若 G 的 任 何 两 个 顶 点 均 由 一 条 H 通 路 连 接 着，则 称 G 是 H 连 通 的。证 明：若 G是“连 通 的，且 p N 4,则 q N；(3p+l).(2)对 于 卢 4,构 造 一 个 具 有 q=1(3 p+l)的 H 连 通 图 G。分 析：根 据 定 理 5.3.1有 2 q=(匕)，因 此 q=d(匕)/2/=1 i=lP而 g d(匕)2 p*b(G),所 以 q 2 p*6(G)/2,因 此 如 果 能 判 断 6(G)3,则 有/=1q p*3(G)/2 3 P/2；(3 p+l);下 面 的 证 明 关 键
47、是 判 断 6(G)2 3。证 明：(1)任 取 wGV(G),由 于 G 是 连 通 的,所 以 d(w)21。若 d(w)=l,则 与 w 邻 接 的 顶 点 u 与 w之 间 不 可 能 有 一 条 H 通 路 连 接 它 们，否 则 因 为 p 2 4,所 以 G中 除 了 u 与 w 外 还 有 其 他 顶 点，因 此，如 果 u 与 w 之 间 有 一 条 H 通 路 的 话，这 条 H 通 路 与 u 与 W的 连 线 就 构 成 了 一 个 回 路，这 样 与 d(w)=l矛 盾，所 以 d(w)Wl；同 样 的 道 理，若 d(w)=2,则 与 w 邻 接 的 顶 点 u 与
48、 v之 间 不 存 在 H 通 路。因 此 3(G)2 3。从 而 2q=Ed(u)23p,即：2q23p,也 即 q 2 3p/2(i)若 P 为 奇 数，于 是|(3 p+l);(i i)若 p 为 偶 数，则 3P为 偶 数，于 是 勺？(3 p+l)；综 合 以 上 各 种 情 况，有：q g(3 p+l)；(2)(i)当 尸 偶 数 时,q=3 p/2,满 足 条 件 的 图 如 下 图(a);(i i)当 尸 奇 数 时，q=g(3 p+l)满 足 条 件 的 图 如 下 图(b);图(a)图(b)11、证 明：若 G 是 一 个 具 有 p=2 8 的 连 通 简 单 图，则 G
49、 有 一 条 长 度 至 少 是 2 5 的 通 路。分 析：使 用 反 证 法，假 设 G 中 没 有 一 条 长 度 大 于 或 等 于 2 3 的 通 路。先 找 到 图 G 的 一 条 最 长 通 路 P,设 其 长 度 为 m,由 假 设 m2 3。再 在 P 的 基 础 上 构 造 一 条 长 度 为 m+1的 回 路 C,显 然 C 中 包 含 的 顶 点 数 小 2 6,山 于 p叁 2 6,所 以 图 G 至 少 还 有 一 个 顶 点 v 不 在 该 圈 中，又 由 于 G 是 连 通 的，所 以 v 到 C 上 有 一 条 通 路 P:于 是 P+C的 长 度 等 于 通
50、 路 P 的 长 度 的 通 路 构 成 了 一 条 比 P 更 长 的 通 路，这 与 P 是 G 的 一 条 最 长 通 路 矛 盾。从 而 本 题 可 得 到 证 明。证 明：(用 反 证 法)设=匕 匕 吗?的 最 长 通 路 淇 长 度 为 m,假 设 mo由 定 义 知：v,+iUT,因 此，|SUT归 根 SUT|=|S+|T|-|5nT|J+J-|snT|=2-|snr|.|snT|o,即 snrw。设 匕 e S n r 丰,从 而 有 G中 的 长 为 m+1的 回 路 C：vv2 v,vI+1vm v(.+1v).因 p+1 4 2 b,所 以，C外 至 少 还 有 一