图的基本知识总结

By @JosonLe
at 2017/12/18

废话不多说，直接上。
但不得要说一句，简书Markdown模式真用不惯，文中很多数学公式都显示不出来，不知道在简书中该怎样写，ε=(´ο｀*)))唉
不管了，初次写文望见谅

大体归纳一下

• 简单图：不存在自己到自己的边，且点与点之间不存在重复边（注：若是有向图，重复边要方向也相同）

• 完全图：

  1. 无向完全图：任意两个顶点之间都有边相连（仅一个点也是）-------------->结点度数为n-1
  2. 有向完全图：任意两个点间都有双向边相连(方向相反的两条边)（仅一个点也是）-------------->结点入度出度n-1
  3. n个节点的完全无向图$K_{n}$的边数${C_{n}}^{2}$,完全有向图$K_{n}$的边数$2{C_{}n}^{2}$

• 图的同构(同构映射)：图G和G1之间点和点相映射，对应的边也相映射（通俗说，就是对应的点、边连接关系不变，只是形状变了）

• 度（不谈）

  1. 无向图中，结点度数之和等于边数的两倍
  2. 有向图中，入度和 = 出度和 = 边数
  3. 奇结点（度数为奇数的结点），同理，偶结点。图中奇结点个数必为偶数

• 零图：结点孤立的图。就一个顶点--->一阶零图，也称平凡图

• 圈图、轮图

• 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是边集合)

  1. 真子图，相比于子图边${E}'\subseteq E$
  2. 生成子图，顶点数目相等，${E}'\subseteq E$,${\phi}'\subseteq \phi$
  3. 导出子图，去掉某个点和与该点相连的边所生成的子图
  4. 补图，n阶完全无向图$K_{n}$的生成子图，记作$\bar{G}$.显然简单无向图都有补图且每个补图都是同构的

• 路径：通俗说顶点i到顶点j之间有路，i和j是连通的（单独一个点也是路径，长度为0的基本路径，所以自己可达自己）

• 简单路径：一条路径中无重复的边

• 基本路径：一条路径中无重复的顶点（n阶图中基本路径长度小于等于n-1）

• 回路（环，也称闭路径）：第一个顶点和最后一个顶点相同的路径就是回路，通俗说从顶点i能走回i

• 基本回路（基本环）：回路中除起始点外，不经过重复点

• 简单回路（简单环）：回路中不经过重复边

• 连通图：

  1. 无向图中，任意两个顶点都是连通的，则称G是连通图
  2. 有向图中，任意vi,vj∈V,vi≠vj
     都有从Vi到Vj的路径和从Vj到Vi的路径，则称G是强连通图
     3.(有向图)单向连通图：任意两个顶点至少一个可达另一个
     4.(有向图)弱连通图：基础图为连通图（“基础图”：有向图去掉边的方向所得的无向图）

• 图的直径：首先定义两点间距离d，（两点不可达，d为无穷），直径就是Max（$d<V,{V}'>$）

• 连通分量(亦称分支)：

  1. 无向图中极大连通子图（“极大”，通俗的说多一个点不行少一个也不够，不能再有点是该连通子图还能构成联通图）
  2. 有向图中极大强连通子图————>（这个是强连通分量，我给他放一起了），还有单向/弱连通子图----->(单向/弱连通分量)
  3. 前提条件：
     • 是子图（非连通图的子图）
     • 子图要连通
     • 满足“极大”，即极大顶点数

• 有向图的强连通图一定是回路,否则不可互达.
  无向图的连通图不是回路,但是有回路的无向图一定是连通的.

• 割点、割边：图G删去点v及相关联的边所得的子图的连通分支数多于原图的连通分支数，则v是G的割点；同理删去边e所得的子图的连通分支数多于原图的，则e是G的割边（桥）。

  1. 显然，连通图删去一个割点或割边后得到的子图不连通
  2. 图G中割边e不在任何回路上

• 矩阵表示、路径矩阵、关联矩阵

• 连通图的生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的 n-1 条边。

  1. 表明含n个顶点的图，边数小于n-1，则不是连通图；如果它多于n-1条边，则必定构成一个环。但有n-1条边也不一定是生成树

参考链接：图的基础知识