●与顶点x相关联的边(x,y)的数目, 称为x的度,记作T(x)或D(x), TD(1)=1 ①(2③3 TD(2)=3 ⑤(4 TD(3)=0 GI ,, ●以顶点x为弧尾的弧<x,y>的数目, 称为x的出度,记作OD(x) A OD(A=1 OD(B)=2 OD(C)=0 以顶点x为弧头的弧<y,x>的数目, G2 称为x的入度,记作ID(x) ID (A)=1 ID (B)=1 ID (C=1 TD(A=OD (A)ID(A)=2 TD(B)=OD(B)+ID (B)=3
● 与顶点 x相关联的边 (x,y)的数目 , 称为 x 的 度，记作TD(x) 或D(x) ， TD(1)=1 TD(2)=3 TD(3)=0 ● 以顶点 x为弧尾的弧 <x,y>的数目 , 称为 x 的出度，记作OD(x) 。 OD(A)=1 OD(B)=2 OD(C)=0 ● 以顶点 x为弧头的弧 <y,x>的数目 , 称为 x 的入度，记作ID(x) 。 ID(A)=1 ID(B)=1 ID(C)=1 TD(A)=OD(A)+ID(A)=2 TD(B)=OD(B)+ID(B)=3 A B C G22 5 4 1 3 G1
对无向图G 若从顶点ⅵ到vj有路径,则称v和ⅴ是连通的 若图G中任意两顶点是连通的,则称G是连通图 2)3(4 G ●若图G是G的一个极大连通子图,则称G是G的一个连通分量。 A FE G1 G2 G3 G有三个连通分量
对无向图G： ● 若从顶点vi到vj有路径,则称vi和vj是连通的。 ● 若图G中任意两顶点是连通的,则称G是连通图。 1 2 3 4 5 6 A F E C B G G D A F E C B G1 D G2 G3 ● 若图G'是G的一个极大连通子图,则称G'是G的一个连通分量。 G G G有三个连通分量
对有向图G ●若在图G中,每对顶点v和vj之间,从ⅵ到vj,且从ⅴj 到ⅵ都存在路径,则称G是强连通图 ●若图G是G的一个极大强连通子图,则称G是G的一个 强连通分量。(强连通图的强连通分量是自身) BC G11 G12 是G1的强连通分量不是G1的强连通分量 B G2 G21 G22 G2有两个强连通分量
对有向图G ● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从vj 到vi都存在路径,则称G是强连通图。 ● 若图G'是G的一个极大强连通子图,则称G'是G的一个 强连通分量。(强连通图的强连通分量是自身) B C G1 A D B C G11 是G1的强连通分量 A D B C G12 不是G1的强连通分量 A D B C G2 A D B C G21 A D G22 G2有两个强连通分量