图的概念¶
简介¶
图论是数学的一个分支，图是由若干个点和边所组成的集合。点代表事物，而边代表事物之间的关系。
概念¶
图的构成¶
图是一个二元组 \(G=(V,E)\)，\(V\) 是一个非空集合，表示点，\(E\) 表示边。图分为有向图和无向图，其实就是边有没有方向的区别。边上是可以有权值的，有权值的图成为有权图。
度¶
- 在有向图中，一个点的前驱结点的数量就是这个结点的入度 \(d^-(v)\)，后继结点的数量就是这个结点的出度，记作 \(d^+(v)\)，这个结点的度就是入度和出度的和，记作 \(d(v)\) \((d(v)=d^+(v)+d^-(v))\)；
- 在无向图中，一个结点的邻点数量就是这个结点的度，记作 \(d(v)\)。
对于一个有向图：
\(\sum_{v\in G}d^+(v)=\sum_{v\in G}d^-(v)=|E|\)
对于一个结点，不同度数的情况也不一样：
| 度数 | 名称 | 英文名称 |
|---|---|---|
| \(d(v)=0\) | 孤立点 | isolated vertex |
| \(d(v)=1\) | 叶子结点 | leaf vertex |
| \(2\mid d(v)\) | 偶点 | even vertex |
| \(2\nmid d(v)\) | 奇点 | odd vertex |
| \(d(v)=\mid V\mid -1\) | 支配点 | universal vertex |
一个图当中的所有结点的度的最大值记作 \(\Delta(G)\)，所有结点的度的最小值记作 \(\delta(G)\)。说人话就是 \(\Delta(G)=\max\limits_{v\in G}d(v)\)，\(\delta(G)=\min\limits_{v\in G}d(v)\)。
简单图¶
- 自环：如果有一条边 \((u,v)\)，其中 \(u=v\)，那么 \((u,v)\) 就是一个自环；
- 重边：如果有两条边完全相等，就称作重边；
- 简单图：如果一个图里面没有自环和重边，这个图就被称作为简单图。