第1节图的基本概念 令例3某单位储存八种化学药品,其中某些药品是不能存 放在同一个库房里的。用点n,n2,n2,,n,V,,别代表这 八种药品,若药品v和药品v是不能存放在同一个库房的, 则在v和之间联一条线 从这个图中可以看到,至少要有四个库房,因为v1,v2,v3,3 必须存放在不同的库房里 事实上,四个库房就足够了。例如{v},{2,V,v(y,n3},{,n 各 存放在一个库房里(这一类寻求库房的最少个数问题,属于图论中 的所谓染色问题,一般情况下是尚未解决的)。 药品存放图 清华大学出版社
第1节 图的基本概念 v 例3 某单位储存八种化学药品，其中某些药品是不能存 放在同一个库房里的。用点 分别代表这 八种药品，若药品vi和药品vj是不能存放在同一个库房的， 则在vi和vj之间联一条线。 ¢ 从这个图中可以看到，至少要有四个库房，因为 必须存放在不同的库房里。 ¢ 事实上，四个库房就足够了。例如 各 存放在一个库房里(这一类寻求库房的最少个数问题，属于图论中 的所谓染色问题，一般情况下是尚未解决的)。 6 7 8 , 1 2 3 4 5 v ,v ,v ,v ,v v ,v ,v 1 2 5 8 v ,v ,v ,v 7 6 8 { },{ },{ },{ } 1 2 4 3 5 v v ,v ,v v ,v v ,v 药品存放图 清华大学出版社 7
第1节图的基本概念 图:由点及点与点的连线构成,反映了实际生活中某些对 象之间的某些特定关系 o点:代表研究的对象; o连线:表示两个对象之间特定的关系。 图:是反映对象之间关系的一种抽象 o一般情况下,图中点的相对位置如何,点与点之间连线的长短曲 直,对反映对象之间的关系并不重要。 口如例2,也可以用图10-5所示的图去反映五个球队的比赛情况,与图 10-3没有本质区别。 比赛情况图 清华大学出版105
第1节 图的基本概念 v 图：由点及点与点的连线构成，反映了实际生活中某些对 象之间的某些特定关系 ¢ 点：代表研究的对象； ¢ 连线：表示两个对象之间特定的关系。 v 图：是反映对象之间关系的一种抽象 ¢ 一般情况下，图中点的相对位置如何，点与点之间连线的长短曲 直，对反映对象之间的关系并不重要。 o 如例2，也可以用图10-5所示的图去反映五个球队的比赛情况，与图 10-3没有本质区别。 比赛情况图 清华大学出版社图10-5 8
第1节图的基本概念 冷关系的对称性和非对称性: o几个例子中涉及到的对象之间的“关系”具有“对称性”,就是说, 如果甲与乙有这种关系,那么同时乙与甲也有这种关系。 o实际生活中,有许多关系不具有这种对称性。 口如例2,如果人们关心的是五个球队比赛的胜负情况,那么从图10-3中就 看不出来了。为了反映这一类关系,可以用一条带箭头的连线表示 口例如,如果球队v胜了球队v2,可以从v引一条带箭头的连线到v2 口类似胜负这种非对称性的关系,在生产和生活中是常见的,如交通运输 中的“单行线”,部门之间的领导与被领导的关系,一项工程中各工序 之间的先后关系等。 比赛胜负图 清华大学出版社
第1节 图的基本概念 v 关系的对称性和非对称性： ¢ 几个例子中涉及到的对象之间的“关系”具有“对称性” ，就是说， 如果甲与乙有这种关系，那么同时乙与甲也有这种关系。 ¢ 实际生活中，有许多关系不具有这种对称性。 o 如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图10-3中就 看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。 o 例如，如果球队v1胜了球队v2，可以从v1引一条带箭头的连线到v2 o 类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输 中的“单行线” ，部门之间的领导与被领导的关系，一项工程中各工序 之间的先后关系等。 比赛胜负图 清华大学出版社 9
第1节图的基本概念 今图的概念 o图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形 o两点之间不带箭头的连线称为边,带箭头的连线称为弧。 o如果一个图G由点及边所构成,则称之为无向图(也简称为图),记 为G=1E),式中V,E分别是G的点集合和边集合。一条连结点v,"∈V 的边记为[",](或[V,V) o如果一个图D由点及弧所构成,则称为有向图,记为D=(V,A),式中V, A分别表示D的点集合和弧集合。一条方向是从v指向v的弧,记为 清华大学出版社
第1节 图的基本概念 v 图的概念 ¢ 图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。 ¢ 两点之间不带箭头的连线称为边，带箭头的连线称为弧。 ¢ 如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记 为 ，式中V，E分别是G的点集合和边集合。一条连结点 的边记为［ ］(或［ ］)。 ¢ 如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V， A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为 ( )。 G =(V,E) i j v ,v j i v ,v i j v ,v i j v ,v V 清华大学出版社 10
第1节图的基本概念 无向图的例子 V={v1,"2ny,} E=er, e,, e3, e4, es,e6, e7 其中 e=v,"2],e2=v,v2」,e3=v2,V3],e;=[v3,小, e=[v,]e。=[v,n]e=[v,] 无向图 e3 图10-7 清华大学出版社
第1节 图的基本概念 v 无向图的例子 其中 V=v1 ,v2 ,v3 ,v4 E e1 ,e2 ,e3 ,e4 ,e5 ,e6 ,e7 1 1 2 2 1 2 3 2 3 4 3 4 5 1 4 6 1 3 7 4 4 e = v ,v , e = v ,v , e = v ,v , e = v ,v , e = v ,v , , e = v ,v , e v ,v 无向图 图10-7 清华大学出版社 11