第 七 章 图 一 、 选 择 题 1． 图 中 有 关 路 径 的 定 义 是 （ ）。【 北 方 交 通 大 学 2001 一 、 24 （ 2 分 ）】 A． 由 顶 点 和 相 邻 顶 点 序 偶 构 成 的 边 所 形 成 的 序 列 B． 由 不 同 顶 点 所 形 成 的 序 列 C． 由 不 同 边 所 形 成 的 序 列 D． 上 述 定 义 都 不 是 2． 设 无 向 图 的 顶 点 个 数 为 n， 则 该 图 最 多 有 （ ） 条 边 。 A． n-1 B． n(n-1)/2 C． n(n+1)/2 D． 0 E． n2 【 清 华 大 学 1998 一 、 5 （ 2 分 ）】【 西 安 电 子 科 技 大 1998 一 、 6 （ 2 分 ）】 【 北 京 航 空 航 天 大 学 1999 一 、 7 （ 2 分 ）】 3． 一 个 n 个 顶 点 的 连 通 无 向 图 ， 其 边 的 个 数 至 少 为 （ ） 。 【 浙 江 大 学 1999 四 、 4 (4分 )】 A． n-1 B． n C． n+1 D． nlogn； 4． 要 连 通 具 有 n 个 顶 点 的 有 向 图 ， 至 少 需 要 （ ） 条 边 。【 北 京 航 空 航 天 大 学 2000 一 、6(2 分 ）】 A． n-l B． n C． n+l D． 2n 5． n 个 结 点 的 完 全 有 向 图 含 有 边 的 数 目 （ ）。【 中 山 大 学 1998 二 、 9 （ 2 分 ）】 A． n*n Ｂ ． n（ n＋ １ ） C． n／ 2 D． n*（ n－ l） 6． 一 个 有 n 个 结 点 的 图 ， 最 少 有 （ ） 个 连 通 分 量 ， 最 多 有 （ ） 个 连 通 分 量 。 A． 0 B． 1 C． n-1 D． n 【 北 京 邮 电 大 学 2000 二 、 5 （ 20/8 分 ）】 7． 在 一 个 无 向 图 中 ， 所 有 顶 点 的 度 数 之 和 等 于 所 有 边 数 （ ） 倍 ， 在 一 个 有 向 图 中 ， 所有 顶 点 的 入 度 之 和 等 于 所 有 顶 点 出 度 之 和 的 （ ） 倍 。【 哈 尔 滨 工 业 大 学 2001 二 、 3 （ 2分 ）】 A． 1/2 B． 2 C． 1 D． 4 8． 用 有 向 无 环 图 描 述 表 达 式 (A+B)*（（ A+B） /A）， 至 少 需 要 顶 点 的 数 目 为 ( )。【 中 山 大 学1999...
