定义

完全图(简单完全图)

完全无向图：边数为𝐧𝐧−𝟏𝟐
完全有向图：边数为 𝐧(𝐧−𝟏)

子图、生成子图

G的子图：所有的顶点和边都属于图G的图

G的生成子图：含有G的所有顶点的子图

连通，连通图，连通分量
【无向图】

v和w连通：无向图中,v到w的路径存在【而不是要求有直接的边】

连通图：图中任意两个顶点都是连通的

连通分量：无向图中的极大连通子图

极大连通子图：连通图只有一个极大连通子图，就是它本身。

强连通图，强连通分量

【有向图】

v和w强连通：有向图中,从v到w和从w到v都有路径，而非弧

强连通图：图中任何一对顶点都是强联通的

强连通分量：有向图中的极大连通子图

生成树，生成森林

生成树：包含图中全部顶点的一个极小连通图

极小连通图：要能连通图的所有顶点而又不产生回路的任何子图

生成森林：非连通图中,连通分量的生成树构成了非连通图的生成森林

顶点的度，入度，出度

顶点的度Degree：图中与该顶点相关联边的数目

入度：指向该顶点的边的数目

出度：从该顶点出去的边的数目

顶点的度 = 出度 + 入度

对于具有n个顶点, e条边的有向图, 出度和=入度和 = e

对于具有n个顶点, e条边的无向图, 顶点度的和（出度+入度）= 2e

路径，路径长度和回路

路径Path：在一个图中，路径是从顶点u到顶点v所经过的顶点序列

路径长度：该路径上边的数目

回路：第一个顶点和最后一个顶点相同的路径

简单路径，简单回路

简单路径：顶点不重复出现的路径

简单回路：除第一个和最后一个顶点，其余顶点不重复出现的回路

距离

从u到v的距离：从u到v的最短路径

有向树

一个顶点的入度为0，其余顶点的入度均为1的有向图