图G由顶点集V和边集E组成,记为G=(V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)的集合
|V| 表示图G中顶点的个数,也称图G的阶;|E| 表示图G中的边的条数
由于子图的定义只是说明子集,没有说明真子集,所以相等的图也是子图
由于图的边集可以为空,所以无边子图也是符合定义的子图
根据图的定义,边是代表顶点之间的关系,所以边必须有两个端点,上面的图片中有一条边只有一个端点,完全不符合图的定义所以不是图,所以更不能称之为子图
连通和强连通定义如下
连通图和强连通图的定义如下
N个顶点的连通图和强连通图最少有多少条边?
连通分量(极大连通子图)与强连通分量(极大强连通子图)
无向图连通分量(极大连通子图)
有向图强连通分量(极大强连通子图)
如果原图是一个连通图或强连通图,那该图的连通分量或强连通分量都是与原图一样的,如果原图并不是一个连通图或强连通图,那该图的连通分量或强连通分量会是有多个的