图论数学模型.pptVIP

图论数学模型第1页，共13页，星期日，2025年，2月5日2.3建立图模型

解决实际问题的趣例第2页，共13页，星期日，2025年，2月5日例1节目排序问题一场文艺演出共有8个节目,全体演员中有10人须参加两个以上的节目演出,情况如表，表中的√号所示,如演员1要参加三个节目A、B和H.若节目主办单位希望首尾两个节目为A和H,或为H和A,并且希望每个演员不连续参加两个节目的演出,试为主办单位安排一个节目顺序表.第3页，共13页，星期日，2025年，2月5日第4页，共13页，星期日，2025年，2月5日分析如演员1要参加三个节目A、B和H。若节目主办单位希望首尾两个节目为A和H。或为H和A，并且希望每个演员不连续参加两个节目的演出，试为主办单位安排一个节目顺序表。所谓开头为节目A（或H），结尾为H（或A），可以认定是一个图的出发点和结束点，由此考虑，以8个节目为顶点构建图模型。由于每个演员不连续参加两个节目的演出,意味着对八个顶点联线时要注意相邻顶点的演员关系.于是决定,若两个节目无同一名演员参加,则可连一条边,表示这两个节目可以紧排,否则不连边,便构成一个图模型（图2—19）.第5页，共13页，星期日，2025年，2月5日解：第6页，共13页，星期日，2025年，2月5日例2药品存储问题有八种化学药品A、B、C、D、P、R、S和T要放进贮藏室保管,出于安全原因,下列各组药品不能贮在同一室内:A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D，试为这八种药品设计一个使用房间数最少的贮藏方案。第7页，共13页，星期日，2025年，2月5日解：TCP;ABS;RD第8页，共13页，星期日，2025年，2月5日例3工程流程图（第五届北京高中数学知识应用竞赛题）机床的大修有如下的工作项目：拆卸③，清洗④，电器检修④，部件检查①，零件加工④，零件修理⑤，床身和工作台研合②，部件组装（不含电器）②，变速器组装①，试车③.1.画出工序的流程图，即用图表示出各项工作的衔接关系.????2.假定大修期间没有耽误任何时间，并把开始拆卸时刻记为0，试问：大修完成的时刻最早是多少？????3.在不影响最短时间完工的条件下，每个工作项目最早和最迟开工时间各是多少？第9页，共13页，星期日，2025年，2月5日关于工序流程图画法的说明（1）“拆卸”，“清洗”等这些具体工作称为工序，用实箭线“→”来表示。工序名称写在箭线上方，完成这项工序的时间写在箭线下面，箭线的方向代表了工序时间的流向.????（2）工序之间交接处表示的圆圈称为事项或结点，用以标志前面工序的结束和允许后面工序的开始，是工序完成或开始的瞬间符号，具有承上启下、把工序衔接起来的作用.????（3）若A工序必须在B工序完成之后才有条件进行，则称A是B的紧后工序，或称B是A的紧前工序.另外，同一对结点间不能表示两个及其以上个工序，如图2－21（左图）的画法是不允许的，为此引进了虚工序概念而将此表示式画成图2－21（右图）的形式.第10页，共13页，星期日，2025年，2月5日