设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'CV，且E'是E的子集，即E'CE，则称G'是G的子图。子图不是子图11/40
设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'V，且 E'是E的子集，即E'E，则称G'是G的子图。 0 1 3 2 0 1 3 2 0 1 3 2 11/40
在一个图G=(V，E)中，从顶点到顶点i的一条路径是一个顶点序列（iit，iz，…，im，j)，若此图G是无向图，则边(i，i)，（i，iz)，(im-1，im)，（im，j)属于E(G)；若此图是有向图，则<i，i>，<i1,iz>,...,<im-1, im>,<im,j>属于E(G)。路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。（0,1,2）的简单(0,3,2,1）的简单路径长度为3路径长度为212/40
在一个图G=(V，E)中，从顶点i到顶点j的一条路径是一个顶点序列(i， i1，i2，.，im，j)，若此图G是无向图，则边(i，i1)，(i1，i2)，.， (im-1，im)，(im，j)属于E(G)；若此图是有向图，则<i，i1>，<i1， i2>，.，<im-1，im>，<im，j>属于E(G)。 路径长度是指一条路径上经过的边的数目。 若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称 此路径为简单路径。 1 2 3 0 4 1 2 3 0 4 （0,3,2,1）的简单 路径长度为3 （0,1,2）的简单 路径长度为2 12/40
若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。(0,1,3,4,0）的简(0,1,2,4,0）的单回路长度为4简单回路长度为413/40
若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回 路或环。 开始点与结束点相同的简单路径被称为简单回路或简单环。 1 2 3 0 4 1 2 3 0 4 （0,1,3,4,0）的简 单回路长度为4 （0,1,2,4,0）的 简单回路长度为4 13/40
在无向图G中，若从顶点到顶点有路径，则称顶点和顶点是连通的，若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个即本身，而非连通图有多个连通分量。两个连通分量构成14/40
在无向图G中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。 若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。 无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连 通分量只有一个即本身，而非连通图有多个连通分量。 1 2 3 0 4 两个连通分量构成 14/40