19335074_黄玟瑜_hw21
需积分: 0 109 浏览量
2022-08-04
15:54:35
上传
评论
收藏 373KB PDF 举报
图论及其应用：第二次作业
注意 请回答任意六题，并将答案在北京时间五月十六日午夜前发送至2160853158@qq.com，邮件
题目中请注明姓名学号
题一 某医院急诊某夜有 169 名病人需要输血，假设每人需要 1 个单位的血量，对 A, B, O, AB
四种血型的需求分别是 39, 38, 42, 50 单位，医院共有 170 单位的储备，对应 A, B, O, AB 分别为
46, 34, 45, 45 单位。
• 请用最大流模型求解最多可以满足多少病人；
• 找出一个容量小于 169 的割，并向精通医学然而并不十分精通图论的医院工作人员用他们可
以理解的方式解释为什么不能满足所有病人。
解：
（1）由于 O 型血能输给其他血型的病人，AB 型病人能接收其他血型的血，同血型可直接供血，
由题意可作出下图：
题目可转化为求从 s 到 t 的最大流，s 到 t 的最大流量等于最小的割 (s, t) 的容量，求得 s 到
t 的最大流如下所示。
1
评论0