9.路径、路径长度、简单路径、简单回路 设图G=(V,V)中的一个顶点序列{u=V0V,.,Vm=W}中， (W,V)口VR或<V-VOVR,1≤jm,则称从顶点u 到顶点w之间存在一条路径。路径上边或弧的数目称作 路径长度。 简单路径：指序列中顶 如：从A到F长度为3的路径： 点不重复出现的路径。 {A,B,C,F和{A,E,C,F BEBB 简单回路：指序列中第一 个顶点和最后一个顶点相 同，且除此之外序列中顶 点不重复出现的路径
设图G=(V,VR)中的一个顶点序列{ u=vi,0,vi,1, ., vi,m=w}中, (vi,j-1,vi,j) VR 或 < vi,j-1,vi,j> VR , 1≤j≤m, 则称从顶点u 到顶点w 之间存在一条路径。路径上边或弧的数目称作 路径长度。 A B E C F 如:从A到F长度为3的路径： 简单路径:指序列中顶 点不重复出现的路径。 简单回路:指序列中第一 个顶点和最后一个顶点相 同，且除此之外序列中顶 点不重复出现的路径。 9. 路径、路径长度、简单路径、简单回路 ABCFB {A,B,C,F}和 {A,E,C,F} BCFB
10.连通图、连通分量 G1 若无向图中任意两个项 点之间都有路径相通， 则称此图为连通图； 若无向图为非连通图， 则图中各个连通子图 称作此图的连通分量。 G2
若无向图中任意两个顶 点之间都有路径相通， 则称此图为连通图; 若无向图为非连通图， 则图中各个连通子图 称作此图的连通分量。 10. 连通图、连通分量 B A C D F E G1 B A C D G2 F E
11.强连通图、强连通分量 对有向图，若任意两个顶点之间都存在 一条有向路径，则称此有向图为强连通图。 否则，其各个强连通子图称作它的 强连通分量。 :
若任意两个顶点之间都存在 一条有向路径，则称此有向图为强连通图。 A B E C F A B E C F 对有向图， 否则，其各个强连通子图称作它的 强连通分量。 11. 强连通图、强连通分量
12.生成树 假设一个连通图有n个顶点和e条 边，其中n个顶点和n-1条边构成一个 极小连通子图，称该极小连通子图为此连 通图的生成树
假设一个连通图有 n 个顶点和 e 条 边,其中 n 个顶点和 n-1 条边 构成一个 极小连通子图，称该极小连通子图为此连 通图的生成树。 B A C D F E 12. 生成树 B A C D F E B A C D F E B A C D F E
⑦若在一棵生成树任添加一条边，则？。 则必定构成一个环，因为新添加的边必 使得依附于这条边的两个顶点之间有了第二 条路经。 ☑一棵有n个顶点的生成树有且仅有？边 若少于n-1条边，则非连通； 若多于n-1条边，则必有环
Ø若在一棵生成树任添加一条边，则？。 则必定构成一个环，因为新添加的边必 使得依附于这条边的两个顶点之间有了第二 条路经。 Ø一棵有n个顶点的生成树有且仅有？边 若少于n-1条边，则非连通； 若多于n-1条边，则必有环