第1节图的基本概念 支撑子图 o给了一个图G=(V,E),如果G=(V,E),使V=V及F∈E, 则称G是G的一个支撑子图 o设v∈(G),用G-表示从图G中去掉点v及y的关联边后得到 的一个图 o若G如图10-10(a)所示,则G-v3见图10-10(b),图10-10(c)是 图G的一个支撑子图 图10-10 清华大学出版社
第1节 图的基本概念 v 支撑子图 ¢ 给了一个图G=(V，E)，如果G′=(V′ ，E′)，使V=V′及E′∈E ， 则称G′是G的一个支撑子图。 ¢ 设v∈V(G)，用G−v表示从图G中去掉点v及v的关联边后得到 的一个图。 ¢ 若G如图10-10(a)所示，则G − v3见图10-10(b)，图10-10(c)是 图G的一个支撑子图。 图10-10 清华大学出版社 22
第1节图的基本概念 令和有向图有关的概念和术语 o设给定一个有向图,D=(V,A),从D中去掉所有弧上的箭头,就 得到一个无向图,称之为D的基础图,记之为G(D) o给定D中的一条弧a=(u,v),称为a的始点,v为.a的终点,称弧a 是从u指向v的 o设(,44…”)是D中的一个点弧交错序列,如果这个序列 在基础图G(D)中所对应的点边序列是一条链,则称这个点弧交错 序列是D的一条链。类似定义圈和初等链(圈)。 o如果(",a1,"2,a2…,",1")是D中的一条链,并且对=1,2,, k-1,均有a=(,n),称之为从v到的一条路。若路的第一个点 和最后一点相同,则称之为回路。类似定义初等路(回路)。 清华大学出版社
v 和有向图有关的概念和术语 ¢ 设给定一个有向图，D=(V，A)，从D中去掉所有弧上的箭头，就 得到一个无向图，称之为D的基础图，记之为G(D)。 ¢ 给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a 是从u指向v的。 ¢ 设 是D中的一个点弧交错序列，如果这个序列 在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错 序列是D的一条链。类似定义圈和初等链(圈)。 ¢ 如果 是D中的一条链，并且对t=1，2，…， k-1，均有 ，称之为从 的一条路。若路的第一个点 和最后一点相同，则称之为回路。类似定义初等路(回路)。 第1节 图的基本概念 1 1 2 2 k 1 k 1 k i ( ) i i i i i i v ,a ,v ,a ,v ,a ,v 1 1 2 2 k 1 k 1 k i ( ) i i i i i i v ,a ,v ,a ,v ,a ,v t t t+1 i ( , ) i i a v v 1 t i i v 到v 清华大学出版社 23
第1节图的基本概念 今有向图的例子 o图10-8。 (v32(v3,n2),v2,(v2,"),v(v4,5)v32(vy,v3),v3) 是一个回路; (n,(,n,v,y,n,,))是从v到v6的路 (,(,ny),(3,),(y,)是一条链,但不是路。 令对无向图,链与路(圈与回路)两 个概念是一致的 类似于无向图,可定义简单有 向图、多重有向图 图10-8是一个简单有向图。 清华大学出版社
v 有向图的例子 ¢ 图10-8。 是一个回路； 是从v1到v6的路； 是一条链，但不是路。 第1节 图的基本概念 3 2 ( , ( ), , ( ), , ( ), , ( ), ) 3 2 2 4 4 4 5 5 5 3 3 v v ,v v v ,v v v ,v v v ,v v 6 6 ( ( ), ( ), ,( ), ) 1 1 3 3 3 4 4 4 v , v ,v v , v ,v v v ,v v 5 3 6 6 ( ( ) , ( ), , ( , ), ) 1 1 3 3 5 5 v , v ,v ,v v ,v v v v v v 对无向图，链与路(圈与回路)两 个概念是一致的。 v 类似于无向图，可定义简单有 向图、多重有向图。 v 图10-8是一个简单有向图。 清华大学出版社 24
第10章图与网络优化 第1节图的基本概念 第2节树 ■第3节最短路问题 第4节网络最大流问题 第5节最小费用最大流问题 ■第6节中国邮递员问题 清华大学出版社
清华大学出版社 第10章 图与网络优化 n第1节 图的基本概念 n第2节 树 n第3节 最短路问题 n第4节 网络最大流问题 n第5节 最小费用最大流问题 n第6节 中国邮递员问题 25
第2节树 ÷2.1树及其性质 22图的支撑树 23最小支撑树问题 清华大学出版社
第2节 树 v 2.1 树及其性质 v 2.2 图的支撑树 v 2.3 最小支撑树问题 清华大学出版社 26