• 主要是讨论从个体特征->整体特征的过程

  • 图的连通性可以反应出图的结构的稳定性

    1. 无向图连通性定义

    image.png

    1.1 无向图可达关系的性质

    image.png
    1.2 可达关系：连通分支
    image.png

    2. 点集和割集

  • 点集和割集主要是为了研究，一些点的存在或者删除后对整个图的连通性影响

image.png

2.1 点割集

image.png
image.png

2.1.1 例

image.png

2.2 边割集

  • 判断边割集的核心就是要保证删除全部的边割集里的边 使得被删除后的图的联通分支数变大，如果没有变大，或者边没有删除完，都不能称为边割集

image.png

3. 连通度

3.1 点连通度和边连通度

image.png

例

image.png

3.2 特殊图的连通度

image.png