4--图论--beamer.pdf

图论 韩参变量 开课单位: 某某大学数学与统计学院 手机号码: +1234567654321 电子邮件: 某某大学邮箱 韩参变量 (某某大学) 图论 1 / 32 S7.1: 图的基本概念 Definition 1 一个 图是一个二元组 = ⟨, ⟩, 其 中 是非空结点集, 是连接结点的边 集. 每条边都是无向边的图称为无向图, 每条边都是有 向边的图称为有 向图, 同 时含无向边与有向边的图称为混合图. 若两个结点与同一条边关联, 则称这两个结点是邻接的. 不与任何结点邻接 的结点称为孤立结点. 仅由孤立结点组成的图称为零图. 仅由一个孤立结点 构成的图称为平凡图. 若两条边与同一结点关联, 则称这两条边是邻接的. 关联于同一结点的一条 边称为自回路或环. 韩参变量 (某某大学) 图论 2 / 32 结点的度数 Definition 2 在图 = ⟨, ⟩ 中, 与结点 ∈ 关联的边数, 称作该结点的度数, 记作 deg(). 约定: 每个环在其对应结点上度数增加 2. 最大度: Δ() max{deg() | ∈ }. 最小度: () min{deg() | ∈ }. 在有 向图中, 指向结点的边数称为入度, 逆 向结点的边数称为出度. Theorem 3 (1) 结点度数的总和等于边数的两倍, 即 ∑︀ deg() = 2 | | . ∈ (2) 度数为奇数的结点必定是偶数个. (3) 所有结点的入度之和等于所有结点的出度之和. 韩参变量 (某某大学) 图论 3 / 32 多重图, 简单 图, 完全图, 补图 Definition 4 与同一对结点关联的多条边称为是平行的. 含有平行边的图称为多重图. 不含平行边和环的图称为简单 图. 在简单 图中, 若任意两结点均邻接, 则称该图为完全图. 个结点的无向完 全图记作 . 给定一个 图 , 由 中所有结点和所有能使 成为完全图的添加边组成的 图, 称为 的相对于完全图的补图, 记作 . Theorem 5 个结点的无向完全图 的边数为 (−1) . 2 韩参变量 (某某大学) 图论 4 / 32 子 图, 生成子 图, 补图 Definition 6 ′ ′ ′ ′′ ′′ ′′ 给定三个 图: = ⟨, ⟩, = ⟨ , ⟩, = ⟨ , ⟩. (1) 若 ′ ⊆ , ′ ⊆ , 则称′ 是 的子 图. (2) 若 ′ = , ′ ⊆ , 则称′ 是 的生成子 图. (3) 若′′ = − ′ 且 ′′ 无孤立结点, 则称′′ 是′ 的相对于 的补图. 韩参变量 (某某大学) 图论 5 / 32 图的同构 D