图的基本概念

图的定义、基本性质和一些记号
设V是非空集合，\(E\subseteq V\times V\). 称\(G=(V,E)\)为图。
一般用\(V(G),E(G)\)分别表示其结点集和边集。\(|V|=n\)称为G的阶。
边\(e=(u,v)\in E\)称结点u和v相邻。

当\(E=V\times V\)时称\(G=K_n\)为n阶无向完全图。
对于\(v\in V\), v作为G中的边的端点次数称为v在G中的度数，记为\(d(v)\). 对于有向图，正度、负度分别定义为v作为始边和终边的次数\(d^+(v), d^-(v)\).
如果图G的所有结点都有相同的度数k，称G为k-正则图。

Prop1. \(\sum\limits_{i=1}^{|V|} d(v_i) = 2|E|\).

对于\(v\in G\), v的邻点集称为v的邻域\(N_G(v)\). 闭邻域\(\overline{N_G(v)}=N_G(v)\cup\{v\}.\) 与v相邻的边\(I_G(v)\)称为v的关联集。
令\(\Delta(G),\delta(G)\)分别表示图G的最大度和最小度。以上定义均可推广到有向图中。

对于\(G'=(V',E'), V'\subseteq V, E'\subset E\), 称\(G'\)为\(G\)的子图。
如果\(V'=V\)， 称\(G'\)为\(G\)的支撑子图（生成子图）。
如果\(E'\)包含了\(V'\)在G中的所有边，称\(G'\)为\(G\)的导出子图，记为\(G'=G[V']\).

给定两个图\(G_1=(V_1,E_1),G_2=(V_2,E_2)\),如果存在双射\(f:V_1\to V_2\)保持边关系，且边的重数相同（若为多重图），则称\(G_1,G_2\)同构，\(G_1\cong G_2\).

图的运算
设\(G=(V,E), E'\subseteq E, V'\subseteq V\). 用\(G-E'\)表示G删去E'所有边得到的图； \(G-V'=G[V-V']\)表示删去V'及其关联边得到的图；\(G\circ V'\)表示G中把V'收缩为一个点得到的图。

设\(G_1,G_2\)为两个不交（即结点集不交）的两个无向图，定义联图\[G_1+G_2 = (V_1\cup V_2, E_1\cup E_2\cup \{(v_1,v_2)|v_i\in V_i\}),\]定义积图\(G_1\times G_2 =\)\[ (V_1\times V_2, \{((u_1,u_2), (v_1,v_2))|u_1=v_1\land (u_2,v_2)\in E_2,\text{或其对偶情况}\}).\]

图的代数表示（数据结构）
设\(n=|V|, m=|E|\).
1. 邻接矩阵\(A=(a_{i,j})_{n\times n}\), 其中\[a_{i,j}=\mathbb I ((v_i,v_j)\in E).\]
2. 权矩阵\(W=(w_{i,j})_{n\times n}\), 其中\(w_{i,j}=g((v_i,v_j))\). 若E中无此边可以补充定义为\(0,\infty\)等.

3. 关联矩阵 \(B=(b_{i,j})_{n\times m}\), \[b_{i,k}\begin{cases} 1, & e_k=(v_i, \_)\\ -1, & e_k=(\_, v_i) \\ 0,& else.\end{cases}\]
4. 边列表，由两个m维向量\(A,B\)组成。对于\(e_k=(v_i,v_j)\), 令\(A(k)=i, B(k)=j\). 对于边权图可以再加一个向量C表示权重。

5. 正向表 由\(n+1\)维向量\(A\)和\(m\)维向量\(B\)组成。
B中依顺序存储每个结点的后继，\(A(i)\)表示结点\(v_i\)的第一个直接后继在B中的存放位置，并约定\(A(n+1) = m+1\). 同样可以补充m维向量C表示权重。

6. 正向邻接表
每个结点的全体外邻点组成一个单链表，结点表示为\([a|b|c]\), 包括外邻接点a，数据b（权值）和下一结点指针c。 n维头指针数组H的分量\(H(i)\)指向\(v_i\)的第一个表结点。

    所属分类：离散数学     发表于2022-05-20