离散数学——图论总结归纳

图论

图的基本概念

图的集合表示

图的表示 \(G(V,E)\) ，其中 \(V\) 为顶点集， \(E\) 为边集，都为有限集.边集可以使有向边集，也可以是无向边集.

\(V(G)\)，\(E(G)\) 表示图 \(G\) 的顶点集和边集.

有序边的表示方法为 \(e_i\) 或者 \(<v_i,v_j>\) ，无序边的表示方法为 \(e_i\) 或 \((v_i,v_j)\).

其他一些基本概念

• 阶：顶点数，有 \(n\) 个顶点即为 \(n\) 阶图.
• 零图：一条边也没有的图.\(n\) 阶零图记为 \(N_n\).一阶零图称为平凡图
• 空图：在运算中产生 \(V\) 为空的情况，记为 \(\varnothing\).
• 基图：有向图变无向图称它的基图
• 环：
  • 无向图中，\(e_k=(v_i,v_j)\) ，称 \(e_k\) 与 \(v_i\)（或 \(v_j\) ）关联；若 \(v_i=v_j\) 则关联次数为 \(2\) ，否则为 \(1\). 不关联则为 \(0\).
  • 有向图中，有始终点之分.
  • 在两种图中，有 \(v_i=v_j\) 则称 \(e_k\) 为环.
• 相邻：点有边连接，边有点连接，称这两个点（边）相邻.
• 简单图：既不含平行边，也不含环的图，称为简单图. 含平行边的为多重图.
  • 在无向图，平行边只需要同连接两个顶点；在有向图中，平行边需要方向相同.
  • 平行边的条数称为重数.

    graph LR
    subgraph 不是平行边
    direction LR
    a((v1))
    b((v2))
    a-->b
    b-->a
    end
    subgraph 是平行边
    direction LR
    c((v1))
    d((v2))
    c-->d
    c-->d
    end
    不是平行边 <---> 是平行边
    

• 度：记 \(G\) 为无向图， \(D\) 为有向图. 则 \(v\) 作为端点的次数为度数，记为 \(d_G(v)\). 有向图中分出度和入度，分别记为 \(d_D^+(v)\) 和 \(d_D^-(v)\). （出为 \(+\) ，入为 \(-\) ，正好与电磁学中的通量相反）
  • 最大度：\(\Delta (G)\) ，\(\Delta (D)\)
  • 最小度：\(\delta (G)\) ，\(\delta (D)\)
  • 最大/小出度：\(\Delta ^+ (D)\)，\(\delta ^+ (D)\)
  • 最大/小入度：\(\Delta ^- (D)\)，\(\delta ^- (D)\)
• 悬挂顶点：度数为 \(1\)，与之关联的边为悬挂边.
• 奇度顶点/偶度顶点：无需解释.
• 握手定理
• 同构（\(\cong\)）
• 彼得松图
• 完全图：\(G\) 为 \(n\) 阶无向简单图，每个顶点都与其余 \(n-1\) 个顶点相连，则 \(G\) 为 \(n\) 阶（无向）完全图，记为 \(K_n\)；若为有向图，则为 \(n\) 阶有向完全图.
• \(n\) 阶竞赛图：\(n\) 阶有向简单图 \(D\) 的基图为 \(n\)阶无向完全图 \(K_n\) ，则称 \(D\) 为 \(n\) 阶竞赛图.
• \(k-\)正则图：\(G\) 为 \(n\) 阶无向简单图，那么 \(\forall v \in V(G), d(v)=k\) .
• 子图、母图、真子图、生成子图：对应子集、原集、真子集、点集相等的子集.