图的基本概念

图的基本概念

• 无向图非连通的最极端情况为一个无向完全图加一个单独的顶点，所以此时构成连通图的条件就是无向完全图的边数+1，即n（n-1）/2+1。
• 图的遍历要求每个结点只能被访问一次，但是若图非连通，则从某一顶点出发无法访问到其他全部顶点

• 强连通图的任何顶点到其他所有顶点都有路径，但未必有弧。

• 无向图任意顶点的入度等于出度，但有向图未必满足

• 边最少
  • 对于连通无向图，边最少即构成一棵树的情形
  • 对于强连通有向图，边最少即构成一个有向环的情形
• 如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，那么它就是极大连通子图
• 注意，V是图的顶点数，E是图的边数