已知有六台机床x1,x2,…,x6,六个零件y1,y2,…,y6。机床x1可加工零件y1;x2可加工零件y1,y2,x3可加工零件y1,y2,y3;x4可加工零件y2;x6可加工零件y2、y3、y4;x6可加工零件y2、y5、y6。现在要求制定一个加工方案,使一台机床只加工一个零件,一个零件只在一台机床上加工,要求尽可能多地安排零件的加工。试把这个问题化为求网络最大流的问题,求出能满足上述条件的加工方案。
第4题
设G=(V,E)是一个简单图,令δ(G)=min{d(v)}(称δ(G)为G的最小次)。证明:(1)若δ(G)≥2,则G必有圈;(2)若δ(G)≥2,则G必有包含至少δ(G)+1条边的圈。
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!