By @JosonLe
at 2017/12/18
废话不多说，直接上。
但不得要说一句，简书Markdown模式真用不惯，文中很多数学公式都显示不出来，不知道在简书中该怎样写，ε=(´ο｀*)))唉
不管了，初次写文望见谅
大体归纳一下
简单图：不存在自己到自己的边，且点与点之间不存在重复边（注：若是有向图，重复边要方向也相同）
-
完全图：
- 无向完全图：任意两个顶点之间都有边相连（仅一个点也是）-------------->结点度数为n-1
- 有向完全图：任意两个点间都有双向边相连(方向相反的两条边)（仅一个点也是）-------------->结点入度出度n-1
- n个节点的完全无向图
$K_{n}$的边数${C_{n}}^{2}$,完全有向图$K_{n}$的边数$2{C_{}n}^{2}$
图的同构(同构映射)：图G和G1之间点和点相映射，对应的边也相映射（通俗说，就是对应的点、边连接关系不变，只是形状变了）
-
度（不谈）
- 无向图中，结点度数之和等于边数的两倍
- 有向图中，入度和 = 出度和 = 边数
- 奇结点（度数为奇数的结点），同理，偶结点。图中奇结点个数必为偶数
零图：结点孤立的图。就一个顶点--->一阶零图，也称平凡图
圈图、轮图
d度正则图：所有结点度数都为d的无向图
-
子图：G=<V,E,
$ \phi $>，$G^{'}=<{V}',{E}',{\phi}'> $,若${V}'\subseteq V,{E}'\subseteq E,{\phi}'\subseteq \phi$,则称${G}'$是G的子图 ($\phi$是点Vi到Vj的边的意思，E是边集合)- 真子图，相比于子图边
${E}'\subseteq E$ - 生成子图，顶点数目相等，
${E}'\subseteq E$,${\phi}'\subseteq \phi$ - 导出子图，去掉某个点和与该点相连的边所生成的子图
- 补图，n阶完全无向图
$K_{n}$的生成子图，记作$\bar{G}$.显然简单无向图都有补图且每个补图都是同构的
- 真子图，相比于子图边
路径：通俗说顶点i到顶点j之间有路，i和j是连通的（单独一个点也是路径，长度为0的基本路径，所以自己可达自己）
简单路径：一条路径中无重复的边
基本路径：一条路径中无重复的顶点（n阶图中基本路径长度小于等于n-1）
回路（环，也称闭路径）：第一个顶点和最后一个顶点相同的路径就是回路，通俗说从顶点i能走回i
基本回路（基本环）：回路中除起始点外，不经过重复点
简单回路（简单环）：回路中不经过重复边
-
连通图：
- 无向图中，任意两个顶点都是连通的，则称G是连通图
- 有向图中，任意vi,vj∈V,vi≠vj
都有从Vi到Vj的路径和从Vj到Vi的路径，则称G是强连通图
3.(有向图)单向连通图：任意两个顶点至少一个可达另一个
4.(有向图)弱连通图：基础图为连通图（“基础图”：有向图去掉边的方向所得的无向图）
图的直径：首先定义两点间距离d，（两点不可达，d为无穷），直径就是Max（
$d<V,{V}'>$）-
连通分量(亦称分支)：
- 无向图中极大连通子图（“极大”，通俗的说多一个点不行少一个也不够，不能再有点是该连通子图还能构成联通图）
- 有向图中极大强连通子图————>（这个是强连通分量，我给他放一起了），还有单向/弱连通子图----->(单向/弱连通分量)
- 前提条件：
- 是子图（非连通图的子图）
- 子图要连通
- 满足“极大”，即极大顶点数
有向图的强连通图一定是回路,否则不可互达.
无向图的连通图不是回路,但是有回路的无向图一定是连通的.-
割点、割边：图G删去点v及相关联的边所得的子图的连通分支数多于原图的连通分支数，则v是G的割点；同理删去边e所得的子图的连通分支数多于原图的，则e是G的割边（桥）。
- 显然，连通图删去一个割点或割边后得到的子图不连通
- 图G中割边e不在任何回路上
矩阵表示、路径矩阵、关联矩阵
-
连通图的生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的 n-1 条边。
- 表明含n个顶点的图，边数小于n-1，则不是连通图；如果它多于n-1条边，则必定构成一个环。但有n-1条边也不一定是生成树
参考链接：图的基础知识
