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

图论

图的基本概念

图的集合表示

图的表示 $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$ .
• 子图、母图、真子图、生成子图：对应子集、原集、真子集、点集相等的子集.