图的基本概念及表示

图的基本概念

逻辑结构二元组B=(K,R),任意一对结点间都允许一个关系存在

  • 分类:无向图、有向图、带权图、稠密图、完全图、连通图等
  • 最一般的数据结构

表示:G=(V, E),有向完全图 $n * (n - 1)$ 条边,无向完全图 $n * (n - 1) / 2$ 条边

带权的连通图称为网络

图G有$n$个顶点,$e$条边,顶点$v_{i}$的度数为$TD(v_{i})$,则有$$e = \frac{1}{2} \sum_{i = 0}^{n - 1}TD(v_{i})$$

环:回路,无向图平行边不构成环,有向图两条边可构成环

- 阅读剩余部分 -