满足 V' = V,则称 H 为 G 的 生成子图/支撑子图 (spanning subgraph)。
显然,G 是自身的子图,支撑子图,导出子图;
无边图 是 G 的支撑子图。原图 G 和无边图都是 G 的平凡子图。
如果一张无向图 G 的某个生成子图 F 为 k- 正则图,则称 F 为 G 的一个 k- 因子 (k-factor)。
如果有向图 G = (V, E) 的导出子图
满足
,有
,则称 H 为 G 的一个 闭合子图 (closed subgraph)。
连通
无 向 图 对 于 一 张 无 向 图 , 对 于 , 若 存 在 一 条 途 径 使 得 , 则 称 和 是 连 通 的 。
由 定 义 , 任 意 一 个 顶 点 和 自 身 连 通 , 任 意 一 条 边 的 两 个 端 点 连 通 。
若 无 向 图 , 满 足 其 中 任 意 两 个 顶 点 均 连 通 , 则 称 是 连 通 图 , 的 这 一 性 质 称 作 连 通 性 。
若 是 的 一 个 连 通 子 图 , 且 不 存 在 满 足 且 为 连 通 图 ,
则 是 的 一 个 连 通 块 连 通 分 量 ( 极 大 连 通 子 图 ) 。
有 向 图 对 于 一 张 有 向 图 , 对 于 , 若 存 在 一 条 途 径 使 得 , 则 称 可 达 。
由 定 义 , 任 意 一 个 顶 点 可 达 自 身 , 任 意 一 条 边 的 起 点 可 达 终 点 。 ( 无 向 图 中 的 连 通 也 可 以 视 作 双 向 可 达 。 )
若 一 张 有 向 图 的 节 点 两 两 互 相 可 达 , 则 称 这 张 图 是 强 连 通 的 。
若 一 张 有 向 图 的 边 替 换 为 无 向 边 后 可 以 得 到 一 张 连 通 图 , 则 称 原 来 这 张 有 向 图 是 弱 连 通 的 。
与 连 通 分 量 类 似 , 也 有 弱 连 通 分 量 ( 极 大 弱 连 通 子 图 ) 和
强 连 通 分 量 ( 极 大 强 连 通 子 图 ) 。
图的稀疏
稀疏图/稠密图
若一张图的边数远小于其点数的平方,那么它是一张 稀疏图 (sparse graph)。
若一张图的边数接近其点数的平方,那么它是一张 稠密图 (dense graph)。
这两个概念并没有严格的定义,一般用于讨论 时间复杂度 为 O(|V|^2) 的算法与 O(|E|) 的算法的效率
差异(在稠密图上这两种算法效率相当,而在稀疏图上 O(|E|) 的算法效率明显更高)。