偶图模型
凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。
(1) 仓库与销售间
M：点代表仓库或销售点，连线代表仓库与销售店间的关联
(2) 上课安排问题
Q：学校有6位教师将开设6门课程。六位教师的代号是Xi（i=1,2,3,4,5,6)，六门课程代号是Yi （i=1,2,3,4,5,6)。已知，教师X1能够胜任课程Y2和Y3；教师X2能够胜任课程Y4和Y5；教师X3能够胜任课程Y2；教师X4能够胜任课程Y6和Y3；教师Y5能够胜任课程Y1和Y6；教师X6能够胜任课程Y5和Y6。
M：点表示教师或者课程，连线表示当且仅当该教师能胜任该课程
2.2 最短路模型
凡涉及到最小状态转换问题，均可转化为最短路模型。点表示允许的状态，连线表示状态的转换（可逆与不可逆分别对应于无向图、有向图）。
(1) 最短航线
M：点表示城市，连线表示当且仅当两城市有直达航线，并在该线上注明两城市的距离，即权值
A：问题转化为求两点间的最短路径
(2) 状态转换
Q：某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。求最少的操作次数能均分酒。
M：设x1,x2,x3分别表示8,5,3升酒壶中的酒量，则
点表示组合(x1,x2,x3) ,连线表示当且仅当可通过倒酒的方式相互变换
A：问题转化为在该图中求点(8,0,0)到点(4,4,0)的一条最短路
(3) 狼羊菜渡河
Q：在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河？
M：但是以下组合不能允许出现：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6种。岸上只能允许出现10种组合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。
点表示可允许的组合，连线当且仅当两种情况可用载人(或加一物)的渡船相互转变。
A：问题转化为求由顶点“人狼羊菜”到顶点“空”的一条最短路。
2.3 最小生成树模型
道路铺设
Q：道路铺设，使得任意两个地方均可达，并且费用最小
M：点表示工厂(假设是工厂)，任意两点连线，并标出铺设需要的费用
A：问题转化为求该图的最小生成树
2.4 欧拉图模型
通俗地讲，G是欧拉图当且仅当G存在经过每条边恰好一次，并且回到起始点的迹。
(1) 哥尼斯堡七桥问题
Q：能否从一点出发，走遍7座桥，且通过每座桥恰好一次，最后仍回到起始地点
M：点表示陆地，连线表示桥
A：问题转化为G是否存在E图
(2) 中国邮递员问题
Q：邮递员必须走过他投递范围内的每一条街道至少一次，选择一条尽可能短的路线
M：点表示路口，连线表示当且仅当两路口有直达街道
A：若G是E图，通过Fleury算法构造Euler环游，即为所求。否则，按一定规则添加重复边，再用Fleury算法构造Euler环游。
2.5 哈密尔顿圈模型
(1) 旅行售货员问题——TSP
一售货员要到若干城市去售货，每座城市只经历一次，问如何安排行走路线，使其行走的总路程最短。
例子：
Q：一电脑代理商要从她所在城市出发，乘飞机去六个城市，然后回到出发点，如果要求每个城市只经历一次，能否办到？给出行走方案。
M：点表示城市，连线表示两城市有直达航线
A：该图是否存在H圈
(2) 圆桌会议座位安排
Q：若干人围圆周开会，每个人会不同的语言，如何安排座位，使得每个人能够和他身边的交流
M：点表示人，连线表示当且仅当两个人能交流，即至少会同一种语言。(可能你一下子想到的偶图模型，的确该问题可以抽象成偶图模型，但很难转化为图论问题)
A：给出该图的一个H圈
2.6 匹配模型
(1) 旅游座位安排
Q：有一个旅行团要组织一批人去旅游，其中一些人是朋友他们要乘坐公共汽车去，而车上的位子是成对的。因此为了让大家旅途更愉快，旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。
M：点表示旅行团的人，连线表示当且仅当两人是朋友
A：求该图的最大匹配
(2) 研究生找工作
Q：学生能找到理想工作吗？
M：点表示研究生或者工作，连线表示当且仅当学生申请了该工作
A：问题转化为求饱和每个顶点的一个匹配，即完美匹配
(3) 最优分派问题
M：点表示工作或者人员，构造完全偶图，边的权值表示该工人做此份工作的效率
A：问题转化为求该图的最优匹配
2.7 平面图模型
平面模型可以这样理解，交通网络，使得不交叉，且无需修高架桥、隧道（这里的隧道显然跟山洞不同）
(1) 电路板设计问题
Q: 连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。
M；点表示电路元器件，连线表示元器件间的连接
A；该图是否可平面
(2) 景区空调管道的设计
M：点表示景区，连线表示当且仅当两景点间要铺设空调管道
A：能否把上图画在平面上，使得边不会相互交叉？
(3) 3间房子和3种设施问题
Q：要求把3种公用设施(煤气，水和电)分别用煤气管道、水管和电线连接到3间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？
M：点表示公用设施或者房子，连线表示该类公用设施连接到该房子
A：抽象出来的图是否可平面嵌入
2.8 着色模型
点着色问题对应于顶点集合的一种划分方式，对应于分类问题。边着色对应于边集合的一种划分方式，也对应于分类问题。区分点着色模型和边着色模型，主要在于抽象出来的模型，是相邻的顶点还是相邻的边不能着同一种颜色。
(1) 点着色模型
① 考试时间安排
Q：使得学生们不会有相互冲突的考试，最小安排数
M：点表示待考的课程，连线表示至少有一个学生同时选择这两门课
A：问题转化为求该图的点色数(把互不冲突的课程、考试安排在同一个时间段完成)
② 课程安排问题
Q: 学生选择课程中，使得学生选课不会发生冲突，如何制订一张课时数尽可能小少的课表
M：点表示课程，连线表示当且仅当有某个学生同时选了这两门课程
A：问题转化为求该图的点色数
③ 交通灯的相位设置问题
Q：为了(最终)让所有的车辆都能够安全通过路口，对于交通灯来说，所需要的相位的最小数是多少
M：点表示车道，连线当且仅当两个车道上的车不能同时安全地进入路口
A：问题转化为求该图的点色数
(2)边着色模型
① 排课表问题
Q：设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。
M：令X=｛x1,x2,…,xm｝, Y=｛y1,y2,…,yn｝,xi与yj间连pij条边，得偶图G=(X, Y)。
A：问题转化为求该图的边着色数
(2) 比赛安排问题
Q：最少天完成比赛
M：点表示参赛人，连线当且仅当两人有比赛
A:问题转化为求一种最优边着色，即用最少色数进行正常边着色
2.9 覆盖模型
覆盖模型，对应于控制问题，通俗地讲点覆盖对应于用最少的点来控制所有边(即任一边至少有一个顶点在点独立集中)，边覆盖对应于用最少的边控制所有的点。均对应于控制问题。
(1) 哨站设计
Q：城市设置哨岗，使得哨兵能监管所有街道的最少哨岗数
M：点表示交叉口，连线表示存在直达街道
A：问题转化为求该图的点覆盖
2.10 强连通性定向图模型
(1) 城市交通网设计问题
Q：一座城市为某种需要，要把所有街道改为单行道，使得人们在任意两个位置都可以相互到达。如何设计单行道方向
M：顶点表示街道交叉口，连线当且仅当存在直达街道
A：问题等价于在模型图中给出其强连通定向
(2) 竞赛图
M：循环比赛的结果可以用所谓的“竞赛图”来表示。u队战胜了v队，则由点u向v画一条有向边。显然，“竞赛图”是完全图的一种定向图。
温馨提示：答案为网友推荐，仅供参考