图之易混概念


  1. 简单图
    • 不存在重复边
    • 不存在顶点到自身的边

  2. 多重图
    • 允许某两个结点之间的边数多于一条
    • 允许顶点通过同一条边和自己关联

  3. 简单路径
    在路径序列中,顶点不重复出现的路径。

  4. 简单回路
    除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路。

  5. 完全图 or 简单完全图
    • 无向图中,任意两个顶点之间都存在边,所以总边数 \( \frac{n(n-1)}{2} \)
    • 有向图中,任意两个顶点之间都存在方向相反的两条弧,所以总边数 \( n(n-1) \)

  6. 连通 and 连通图
    无向图中,若顶点 v 到顶点 w 有路径存在,则称 v 和 w 是连通的。若该无向图中的任意两顶点都是连通的,则称该图为连通图。

  7. 极大连通子图 and 连通分量
    非连通无向图 的极大连通子图称为连通分量。极大要求该连通子图包含其所有的边。极小连通子图是既要保持图连通又要使得边数最少的子图。

  8. 强连通 and 强连通图
    有向图中,若顶点 v 到顶点 w 和从顶点 w 到顶点 v 都有路径存在,则称这两个顶点是强连通的。若该有向图中的任意两顶点都是强连通的,则称该图为强连通图。

  9. 强连通分量 and 极大强连通子图
    非强连通有向图 的极大强连通子图称为强连通分量。

  10. 生成树
    一个无向连通图的生成树是它的 极小连通子图,若图中含有 n 个顶点,则其生成树由 (n-1) 条边构成。若是有向图,则可能得到它的若干有向树组成的生成森林。
    最小生成树 就是一个带权图的总权值最小的生成树。
------本文结束感谢您的阅读 ------
0%