数据结构:图的基本概念

数据结构啊啊啊.图这里陌生的概念好多,在博客上记下来以加深印象

图的顶点与边间关系

对于无向图:

  • 邻接点: 对于无向图 G=(V,{E}), 如果边(v,v’) ϵ E, 则称顶点v和v’互为邻接点,即v和v’相邻接。
  • 依附(关联): 边(v,v’)依附于顶点v和v’, 或者说边(v,v’)与顶点v和v’相关联。
  • 度:顶点v的是和v相关联的边的数目,记为TD(v)
  • 边数与度的关系:边数其实就是各顶点度数和的一半。记作 $e = \cdrac{1}{2}∑_{i=1}^{n}TD(vi)$
    对于有向图:
  • 邻接点:对于有向图 G=(V,{E}), 如果弧<v,v’> ϵ E, 则称顶点v邻接到顶点v’,顶点v’邻接自顶点v。
  • 关联:弧<v,v’>和顶点v,v’相关联。
  • 度: 顶点的度为 TD(v) = ID(v) + OD(v)
    • 入度: 以顶点v为头的弧的数目称为v的入度,记为ID(v);
    • 出度: 以v为尾的弧的数目称为v的出度, 记为OD(v)
  • 边数与度的关系:边数=各顶点出度之和=各顶点入度之和,记作$ e = ∑{i=1}^{n}ID(vi) = ∑{i=1}^{n}OD(vi) $