顶点的度、入度、出度；顶点，顶点关系的描述；连通图、强连通图；子图、生成子图；连通分量、强连通分量；生成树、生成森林；边的权、带权图/网；几种特殊的图

顶点的度、入度、出度

  • 顶点v的度（无向图）：是指依附于该顶点的边的条数，记为 TD(v)
    无向图的全部顶点的度的和等于边数的两倍
  • 顶点v的度（有向图）：
    • 入度：是以顶点v为终点的有向边的数目，记为ID(v)
    • 出度：是以顶点v为起点的有向边的数目，记为OD(v)
    • 顶点v的度：等于其入度和出度之和，即TD(v)=ID(v)+OD(v)

顶点，顶点关系的描述

  • 路径：顶点vpv_{p}到顶点vqv_{q}之间的一条路径是指顶点序列，
  • 回路：第一个顶点和最后一个顶点相同的路径称为回路或环
  • 简单路径：再路径序列中，顶点不重复出现的路径称为简单路径
  • 路径长度：路径上边的数目
  • 点到点的距离：从顶点出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）
  • 连通：无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
  • 强连通：有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

  1. 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图
    对于n个顶点的无向图G，若G是连通图，则最少有n-1条边，若G是非连通图，则最多可能有Cn−12C^{2}_{n-1}条边
  2. 若图中任何一对顶点都是强连通的，则成此图为强连通图
    对于n个顶点的有向图G，若G是强连通图，则最少有n条边（形成回路）

子图、生成子图

  • 子图：设有两个图G=(V,E)G=(V,E)和G′=(V′,E′)G^{'}=(V^{'},E^{'})，若V′V^{'}是V的子集，且E′E^{'}是E的子集，则称G′G^{'}是G的子图。（就是有节点有边）
  • 生成子图：若有满足V(G′)=V(G)V(G^{'})=V(G)的子图G′G^{'}，则称其为G的生成子图。（取个子图去掉一些边）

连通分量、强连通分量

  • 连通分量：无向图中的极大连通子图称为连通分量（子图必须连通，且包含尽可能多的顶点和边）
  • 强连通分量：有向图中的极大连通子图称为有向图的强连通分量（子图必须强连通，同时保留尽可能多的边）

生成树、生成森林

  • 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。（边尽可能的少，但要保持连通）
  • 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权、带权图/网

  • 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
  • 带权图/网：边上带有权值的图称为带权图，也称为网。
  • 带权路径长度：当图是带权图时，一条路径上所有边的权值之和。称为该路径的带权路径长度。

几种特殊的图

  • 无向完全图：无向图中任意两个顶点之间都存在边
  • 有向完全图：有向图中任意两个顶点之间都存在方向完全相反的两条弧
  • 稀疏图：边数很少的图
  • 稠密图：边数较多的图
  • 树：不存在回路，且连通的无向图
  • 有向树：一个顶点的入度为0，其余顶点的入度均为1 的有向图，称为有向树。