图

图的基本概念

图由结点集合 $V$ ，边集合 $E$ ，映射关系 $\varphi$ 构成，其中 $\varphi:E\rightarrow V\times V/\{V,V\}$ 为由边到结点序偶/两元素集合的函数
当 $\varphi$ 映射到序偶时，称为有向图，反之为无向图
每条边关联的两个点相互点邻接，同一结点上的各条边相互边邻接
若 $e$ 关联的两点是同一结点，称为自回路/环
若 $\varphi(e_1)=\varphi(e_2)$ ，称这两条边互为平行边，在有向图中需注意方向
图的分类(侧重点不同的领域定义可能有所不同)：
- 简单图：既没有自回路也没有平行边
- 多重边图：没有自回路，有平行边
- 伪图：有自回路和平行边
图的同构：含双射函数 $f:V\rightarrow V',g:E\rightarrow E'$ ，新的映射关系 $\varphi'$ ，满足 $\varphi(e)=\{v_1,v_2\}\rightarrow\varphi'(g(e))=\{f(v_1),f(v_2)\}$
结点的度数及相关结论：
- 所有结点度数之和 $d(G)$ 等于两倍的边数
- 一定含偶数个奇度节点
$d$ $d$ 度正则图：所有结点度数为 $d$ $d$ 度，若结点数为 $d+1$ $d + 1$ ，则称其为** $d+1$ $d + 1$ 阶完全无向图**，记为 $k_{d+1}$ $k_{d + 1}$
- $k_n$ 为同阶图中边数最多的图，且 $\begin{align}|E|=\frac{n(n-1)}2=C_n^2\end{align}$
子图的定义：
- 若子图的三个构成部分都包含于母图，称为子图
- 在子图基础上，若边、映射关系真包含于母图，称为真子图
- 在子图基础上，若结点集合和母图一致，称为生成子图，即对母图只删除边(或不删除)
- 导出子图：分为由边导出和由结点导出
路径、回路：
- 路径由若干结点及连接它们的边组成，若起点和终点重合，称其为回路
- 若一条路径/回路中边互不相同，称为简单路径/回路
- 若一条路径结点互不相同/回路除起点外结点互不相同，称为基本路径/回路(圈)
- 若简单回路包含图中所有边，称为欧拉回路；若基本回路包含图中所有点，称为哈密尔顿回路
- 基本路径一定是简单路径，反之不成立；基本回路也不一定是简单回路
- $n$ 阶图中，基本路径长度小于等于 $n-1$
连通性：
- 若两结点间有路径，则称它们可达，称最短路径为测地线
- 定义图的直径为最长路径的长度
- 无向图：若任意两结点可达，称 $G$ 是连通的
- 有向图：
  - 若其对应的无向图(也叫基础图)连通，称为弱连通
  - 若任意两结点有单向路径，称为单向连通
  - 若任意两结点互相可达，称为强连通
- 无向图连通分支：由可达关系(是一个等价类)划分出的等价类导出的子图为连通分支
- 每个连通分支都是一个连通子图
- 若通过删去边/点能使一个连通分支变为两个或以上，称其为割边/割点
- $e是割边\Leftrightarrow e不在任何简单回路上$
邻接矩阵：注意结点没有自回路，结点和自身不可达
邻接矩阵的转置：表示其逆图，所有边反向
邻接矩阵的幂 $A^n$ ： $a_{ij}$ 表示由 $i$ 到 $j$ 的 $n$ 度路径长度
可达性矩阵 $P$ ：是布尔矩阵，表示可达性
$AA^T$ ： $a_{ij}$ 表示以 $i/j$ 为起点，共同终于某些结点的边的个数
$A^TA$ ： $a_{ij}$ 表示以某些结点为起点，终于 $i/j$ 的边的个数

图#

图的基本概念#

图

图的基本概念