图（上）

图的概念

图G由顶点集合V(G)和边集合E(G)构成

说明： 对于n个顶点的图，对每个顶点连续编号，即顶点的编号为 0 ~ n-1。通过编号唯一确定一个顶点。

图的基本运算：

• 图的初始化
• 销毁图
• 从顶点$v$v出发深度优先遍历
• 从顶点$v$v出发广度优先遍历

图的基本术语

端点和邻接点

• 无向图：若存在一条边$(i,j)$(i,j)->顶点$i$i和顶点$j$j为端点，它们互为邻接点。
• 有向图：若存在一条边$<i,j>$<i,j>->顶点$i$i为起始端点（简称起点），顶点$j$j为终止端点（简称终点），它们互为邻接点。

顶点的度、入度和出度

• 无向图：
  以顶点$i$i为端点的边数称为该顶点的度。
  

• 有向图：
  以顶点$i$i为终点的入边的数目，称为该顶点的入度。
  以顶点$i$i为始点的出边的数目，称为该顶点的出度。
  一个顶点的入度与出度和为该顶点的度。
  

若一个图中有$n$n个顶点和$e$e条边，每个顶点的度为$d_{i}(0\leq{i}\leq{n-1})$di​(0≤i≤n−1),则有：
$e=\frac{1}{2}\sum_{i=0}^{n-1}d_{i}$e=21​i=0∑n−1​di​

完全图

• 完全无向图：每两个顶点之间都存在着一条边，称为完全无向图，包含$n(n-1)/2$n(n−1)/2S条边。
  
• 完全有向图：每个顶点之间都存在着方向相反的两条边，称为完全有向图，包含$n(n-1)$n(n−1)条边。
  

稠密图、稀疏图

当一个图接近完全图时，则称为稠密图。
相反，当一个图含有较少的边数（即当$e<<n(n-1)$e<<n(n−1)）时，则称为稀疏图。

子图

设有两个图$G=(V, E)$G=(V,E)和$G'=(V', E')$G′=(V′,E′)，若$V'$V′是$V$V的子集，且$E'$E′是$E$E的子集，则称$G'$G′是$G$G的子图。

路径和路径长度

  在一个图$G=(V, E)$G=(V,E)中，从顶点$i$i到顶点$j$j的一条路径$(i, i_1, i_2, …, i_m, j)$(i,i1​,i2​,…,im​,j)。其中所有的$(i_x, i_y)\in E(G)$(ix​,iy​)∈E(G)，或者$(i_x,i_j) \in E(G)$(ix​,ij​)∈E(G)
  路径长度是指一条路径上经过的边的数目。
  若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。

回路或环

  若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。

连通、连通图和连通分量

  无向图：若从顶点i到顶点j有路径，则称顶点i和j是连通的。
  若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。
  无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身而非连通图有多个连通分量。

强连通图和强连通分量

  有向图：若从顶点i到顶点j有路径，则称从顶点i到j是连通的。
  若图G中的任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在路径，则称图G是强连通图。

  有向图G中极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身。非强连通图有多个强连通分量。