图的相关定义

无向图定义

• 无向边： 若顶点到顶点到之间没有方向，则称这条边为无向边(Edge),用无序偶对（）表示
• 无向图： 若图中任意两个顶点之间的边都是无向边，则称该图为无向图。
• 无向完全图： 无向图中，如果任意两个顶点之间都存在边，则称为图的无向完全图。

有向图定义

• 有向边： 若顶点到顶点之间有方向，则称这条边为向边(Edge),用有序偶对 表示。
• 有向图： 若图中任意两个顶点之间的边都是有向边，则称该图为有向图。
• 有向完全图： 有向图中，如果任意两个顶点之间都存在方向互为相反的边，则称为图的有向完全图。

顶点和边的关系

• 度数： 当两个顶点通过一条边相连时，称两个顶点是相邻的，并称这条边依附于这两个顶点。某个顶点的度数即为依附于它的边的总数。
• 子图： 由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。
• 路径： 由各个边依次连接的一系列顶点。
• 简单路径： 一条没有重复的路径。
• 环路径： 一条至少含有一条边且起点和终点相同的路径。
• 简单环路径： 一条（除起点和终点必须相同之外）不含有重复顶点和边的环。
  :::tip
  路径的长度是路径上的边数。
  :::
  在大多数情况下，路径指的是简单路径，而环指的是简单环。当两个顶点之间存在一条连接双方的路径时，我们称为一个顶点到另外一个顶点是连通的。

连通图

• 连通图： 如果对于图中任意两个顶点，都有路径连通，则这幅图为连通图。
• 极大连通子图： 具有极大顶点数的连通子图。
• 无向图中的连通分量： 无向图中的极大连通子图称为连通分量。连通分量要满足一下条件：
  • 要是子图
  • 子图要连通
  • 连通子图含有极大顶点数
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边
• 有向图中的强连通分量： 有向图中的极大连通子图称为强连通分量。连通分量要满足一下条件：
  • 要是子图
  • 子图要连通
  • 连通子图含有极大顶点数
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边

连通图的生成树

连通图的生成树是一个极小的连通子图，它含有图中全部的 n 个顶点，但只有足以构成一棵树的n-1条边。所以在无向图中连通图且有n个顶点n-1条边叫生成树，在有向图中，一个顶点入度为0，其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。