§6.1.1图的概念 7.路径(通路)(续) 对无向图,若有边序列 (x2Xx),(x12X2),…,(x212Xn) 且n≥l,则称x与xn之间有路径(通路),该路径可用 上列边序列表示,亦可用下列结点序列表示 )(d
11 §6.1.1 图的概念 7．路径（通路）（续） • 对无向图，若有边序列 (x0 ,x1 )，(x1 ,x2 )，…，(xn-1 ,xn ) 且n≥1，则称x0与xn之间有路径（通路），该路径可用 上列边序列表示，亦可用下列结点序列表示 (x0 , x1 , … ,xn ) a b c d
§6.1.1图的概念 7.路径(通路)(续) 路径中边的数目称为路径长 若x。-x,则称相应的路径为回路/环路。 若在路径(xx1,…xn)中,除x与xn外,任意其它结 点均不相同,则称该路径为简单路径。起点与终点重合 的简单路径称为简单回路。 4 12
12 §6.1.1 图的概念 7．路径（通路）（续） • 路径中边的数目称为路径长。 • 若x0=xn，则称相应的路径为回路/环路。 • 若在路径(x0 , x1 , … ,xn )中，除x0与xn外，任意其它结 点均不相同，则称该路径为简单路径。起点与终点重合 的简单路径称为简单回路。 a b c d 1 2 5 4 3
§6.1.1图的概念 8.子图/生成图 若某图G的结点集合与边集合分别是另一图的G的结 点集合和边集合的子集,则称G为G的子图。 设有两个图G与G,若它们的结点集合相同,但G的 边集合是G的边集合的子集,则称G是G的生成图 显然,生成图一定是子图,但反之未必。 4 13
13 §6.1.1 图的概念 8．子图/生成图 • 若某图G'的结点集合与边集合分别是另一图的G的结 点集合和边集合的子集，则称G'为G的子图。 • 设有两个图G与G'，若它们的结点集合相同，但G'的 边集合是G的边集合的子集，则称G'是G的生成图。 • 显然，生成图一定是子图，但反之未必。 a b c d 1 2 5 4 3
§6.1.1图的概念 9.连通 若图中任意两结点间均有通路(x到y与y到x),则称 该图是(强)连通的 若图中某子图是连通的,则称该子图为一个连通分量 若G的某子图G是连通的,并且,若有G的另一子图 G”包含图G,则G必不连通,则称G’是极大连通分量
14 §6.1.1 图的概念 9．连通 • 若图中任意两结点间均有通路（x到y与y到x），则称 该图是（强）连通的。 • 若图中某子图是连通的，则称该子图为一个连通分量。 • 若G的某子图G'是连通的，并且，若有G的另一子图 G''包含图G'，则G''必不连通, 则称G'是极大连通分量。 a b c d 1 2 5 4 3
§6.1.1图的概念 9.连通(续) 对于有向图,若任意两结点间至少有单向通路,但有 些结点无双向通路,则称该图为弱连图。 类似地,也有弱连通分量的概念 4 15
15 §6.1.1 图的概念 9．连通（续） • 对于有向图，若任意两结点间至少有单向通路，但有 些结点无双向通路，则称该图为弱连图。 • 类似地，也有弱连通分量的概念。 1 2 5 4 3