第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