关于这篇分享，神犇和大佬们可以点个赞走啦~

进入正题

1.什么是图

• 图是一种数据结构，定义 : $graph = (V，E)$。其中 $V$ 是一个非空有限集合，代表结点，$E$
  代表边的集合。说人话就是，点用边连起来就是图。例如：
  

2.图的分类

• 有向图：图的边有方向，只能按箭头方向从一点到另一点（就像单行道）。例如：
  
• 无向图：图的边没有方向，可以双向通行（和普通道路一样）。例如：
  
• 稠密图：一个边数接近完全图的图。
• 稀疏图：一个边数远远小于完全图的图.

3.图的相关术语

• 度：无向图中与结点相连的边的数目，称为它的度。
• 入度：在有向图中，以这个结点为终点的有向边的数目。
• 出度：在有向图中，以这个结点为起点的有向边的数目。
• 权值：边的”费用”，即从一个点到另一个点所要花费的代价。
• 连通：如果图中两个结点之间存在一条通过若干条边、点到达的通路，则称它们是
  连通的。
• 回路：起点和终点相同的路径，称为回路，也可以叫做“环”。
• 负环：一个所有边的权值和为负数的环称为负环。
• 奇点偶点：无向图中顶点的度若为奇数，则称这个顶点为奇点，若为偶数，则称它为偶点
• 连通分量：
  (1) 非连通无向图中的极大连通子图
  (2) 连通图的连通分量只有一个即本身。设 $G(v,e)$ 是非连通图, $G’(v’,e’)$ 是连通图，如果对于 $v’$ 等于 $v$, $e’$ 包含于 $e$,那么 $G’$ 叫做 $G$ 的极大连通子图。
• 强连通分量：有向图 $G$ 中，如果对于每一对 $V_i,V_j \in V$，从 $V_i$ 到 $V_j$ 和从 $V_j$到 $V_i$ 都
  存在路径，则称 $G$ 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

4.图的定理

1. 无向图中所有顶点的度之和等于边数的两倍，有向图中所有顶点的入度之和等于所有顶点的出度之和。
   2.任意一个无向图一定有偶数个(或0个)奇点。
   3.无向连通图最多 $n \times (n-1)/2$ 条边，最少 $n-1$ 条边。如果有 $n \times (n-1)/2$ 条边,即为无向完
   全图。

完结撒花$QwQ$~