数学建模-图论

有向图：
1, 若vi是ei的始点 aij 1, 若vi是ei的终点 0, 若v 与e 不关联 i i
1, 若vi与v j 关联 aij 无向图： 0, 若vi与v j 不关联
数学建模-图论
二、图的矩阵表示 例3：分别写出右边两图的关联矩阵 解：分别为：
1 0 0 1 1 0 1 1 1 0 0 0 0 0 A 0 1 1 0 1 1 0 0 0 1 1 0 1 1
A
D
C
C A B
A
B
D
对四个陆地 A、B、C、D，若其间有桥，则用一条弧 线连接起来，有两座桥，则连两条不重合的弧线，便得到 一个图，并称代表陆地的四个点为顶点 ，代表桥的弧线 为 边 。 这样一来，能否从一地出发走遍七座桥一次且仅一次 再回到出发点就变成了：能否从这个图上任一顶点出发， 经过每条边一次且仅一次而回到出发顶点。这就是众所周 知的这个图能否“一笔画出”的问题。
1, vi v j E aij 0, vi v j E
例1：写出右图的邻接矩阵： 解：
0 0 A 1 1 1 0 0 0 0 1 0 1 1 0 1 0
数学建模-图论
二、图的矩阵表示
2 有向图的权矩阵A = (aij ) n×n （n为结点数）
数学建模-图论
一、图的基本概念(应用) 用图论思想求解以下各题 例1、一摆渡人欲将一只狼，一头羊，一篮菜从 河西渡过河到河东，由于船小，一次只能带一物 过河，并且，狼与羊，羊与菜不能独处，给出渡 河方法。
数学建模-图论
一、图的基本概念(应用) 解： 用四维0-1向量表示（人，狼，羊，菜）的在西岸 状态，（在西岸则分量取1，否则取0.）
问题: 如果城市不止4个,有n个城市,能否快速给出直接路径
以及需要转机方案. 问题: 过年回家火车路线如何设置，北京公交地铁倒车如何 如何设置 百度地图
15
2018年5月23日
数学建模-图论
一、图的基本概念
如果图的二顶点间有边相连，则称此顶点相邻，每一对顶点 都相邻的图称为完全图，否则称为非完全图，完全图记为 K V 。
若 V (G) X Y , X Y , X Y 0 ，且 X 中 无相邻的顶点对， Y 中亦然，则称图 G 为二分图.
一 二
三 四
图的基本概念
图的矩阵表示 最短路问题及其算法 最小生成树问题
数学建模-图论
一、图的基本概念
假设平面上的 n 个点，把其中的一些点对用曲线或直 线连接起来，不考虑点的位置与连线曲直长短，形成的一 个关系结构称为一个图。 记 G V (G), E (G) , V V (G) 是顶点集， E E (G) 是边集。
支配集--仓库分区
7
• 将该图中所有顶点用不同颜色表示，最少需要几种颜色。
“点着色
• 将该图中所有边用不同颜色表示，最少需要几种颜色。
边着色 关键路径 最大流、最小流
8
问题2(哈密顿环球旅行问题): 十二面体的20个顶点代表世界上20个城市， 能否从某个城市出发在十二面体上依次经过每个 城市恰好一次最后回到出发点？
人在河东： （0,1,0,1） （0,1,0,0） （0,0,1,0） （0,0,0,1） （0,0,0,0）
以十个向量作为顶点，将可能互相转移的状态 连线，则得10个顶点的偶图。 问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？ 方法：从（1,1,1,1）开始，沿关联边到达没有到达 的相邻顶点，到（0,0,0,0）终止，得到有向图即是。
18
2018年5月23日
数学建模-图论
一、图的基本概念
几个基本定理：
1、对图G V，E ，有 d v 2 E .
vV
2、度为奇数的顶点有偶 数个。
3、设G V，E 是有向图， 则 d v d v E .
vV vV
19
2018年5月23日
特别地，若对任意 x X ，则 x 与 Y 中每个顶点 相邻，则称图 G(V , E ) 为完全二分图，记为 K X , Y 。
16 2018年5月23日
数学建模-图论
一、图的基本概念
设 v V (G) ，是边 e E(G) 的端点，则称 v 与 e 相关联， 与顶点 v 关联的边数之和称为该顶点的次数，记为 d (v) 。
数学建模
---图论
前言
• 图论起源于18世纪。第一篇图论论文是瑞士 数学家欧拉于1736 年发表的“哥尼斯堡的七 座桥”。 • 图与网络是运筹学（Operations Research） 中的一个经典和重要的分支，所研究的问题 涉及经济管理、工业工程、交通运输、计算 机科学与信息技术、通讯与网络技术等诸多 领域。 • 传统的物理、化学、生命科学也都越来越广 泛地使用了图论模型方法。
数学建模-图论
一、图的基本概念(应用)
任取v V G , 则有两种情况：
1 v至少与另外3个顶点相邻，这又包含 两种情况： 1、这3点互不相邻，则 G包含3,0图为子图。
2、这3点至少2点相邻，则G包含K 3为子图。
（2）v至多与另外2个顶点相邻(即至少与另外 3个顶 点不相邻)。这又包含两种情况： 1、这3点两两相邻，则 G包含K 3图为子图。
哈密顿圈（环球旅行游戏）
问题3(四色问题): 对任何一张地图进行着色，两个共同边界的 国家染不同的颜色，则只需要四种颜色就够了.
问题4(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育 中心,小至组装一台机床,一架电视机, 都要包括 许多工序.这些工序相互约束,只有在某些工序完 成之后, 一个工序才能开始. 即它们之间存在完 成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多 少时间才能够完成整个工程项目, 影响工程进度 的要害工序是哪几个？
共24=16种状态，
由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不 允许的，
从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是 不允许的，
数学建模-图论
一、图的基本概念(应用) 人在河西： （1,1,1,1） （1,1,1,0） （1,1,0,1） （1,0,1,1） （1,0,1,0）
D
• 能否从这个图上任一顶点出发，经过每条边一次且仅 一次而回到出发顶点。
“
一笔画出”
• 能否从这个图上任一顶点出发，经过每个顶点一次且 仅一次而回到出发顶点。
旅行商问题
• 能否从这个图选择尽量少的点，使得所有的其余点都 和该点集有路径连接。
覆盖问题-系统监控模型
• 能否将图中点集分类，使得每一类点集都没有路径连 接，最少需要分几类。
数学建模-图论
一、图的基本概念(应用) 例2、考虑中国象棋的如下问题： （1）下过奇数盘棋的人数是偶数个。 （2）马有多少种跳法？ （3）马跳出后又跳回起点，证明马跳了偶数步。 （4）红方的马能不能在自己一方的棋盘上不重复 的跳遍每一点，最后跳回起点？
数学建模-图论
一、图的基本概念(应用) 例3、证明：在任意6人的集会上，总有3人互相认 识，或总有3人互相不认识。 解：以顶点表示人，以边表示认识，得6个顶点 的简单图G。 问题：3人互相认识即G包含K3为子图， 3人互相不认识即G包含（3,0）图为子图。
如果各条边都加上方向，则称为有向图，否则称为无向图。 如果有的边有方向，有的边无方向，则称为混合图。
如果任两顶点间最多有一条边，且每条边的两个端点皆 不重合的图，则称为简单图。
13 2018年5月23日
数学建模-图论
一、图的基本概念
图1
14
图2
2018年5月23日
数学建模-图论
一、图的基本概念
一个图会有许多外形不同的图解, 下面两个 图表示同一个图G = (V, E )的图解. 其中 V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}.
0 0 A 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 0
e
e1
e3
d
e2
b
e4
c
e5
a
数学建模-图论
二、图的矩阵表示
4
应用实例
某航空公司在A,B,C,D四城市之间开辟了若干航线 ,如图所示 表示了四城市间的航班图,如果从A到B有航班,则用带箭头的 线连接 A 与B. 问题: 如何直观给出各个城市之间的航班情况 问题: 如果没有直接航班到达,需要转机,有几种转机方案
可以证明:
vV ( G )
d (v) 2 E(G) ，
且由此可知：奇次顶点的总数是偶数，即所有 顶点的次数之和是边数的两倍。
次数为奇数顶点称为奇点，否则称为偶点。
17 2018年5月23日
数学建模-图论
一、图的基本概念 常用d(v)表示图G 中与顶点v关联的边的数目, d(v)称为顶点v的度数. 与顶点v出关联的边的数目称为出度，记作d +(v)， 与顶点v入关联的边的数目称为入度，记作d -(v)。 用N(v)表示图G 中所有与顶点v相邻的顶点的集合. 任意两顶点都相邻的简单图称为完全图. 有n个顶点的完全图记为Kn 。
如果通路中没有相同的顶点, 则称此通路为路径, 简称 路. 始点和终点相同的路称为圈或回路.
数学建模-图论
一、图的基本概念 顶点u与v称为连通的，如果存在u到v通路，任二顶 点都连通的图称为连通图，否则，称为非连通图。极大 连通子图称为连通分图。 连通而无圈的图称为树, 常用T 表示树. 树中最长路的边数称为树的高，度数为1的顶点 称为树叶。其余的顶点称为分枝点。树的边称为树 枝。 设G是有向图，如果G的底图是树，则称G是 有向树，也简称树。
F vi v j , aij 0, , vi v j E i j vi v j E
例2：写出右图的权矩阵： 解：
0 6 8 0 7 A 3 0 2 4 5 0
数学建模-图论
二、图的矩阵表示 3 有向图的关联矩阵A =(aij )n×m （n为结点数m为边数）
从七桥问题说起 ---关于图模型
问题的提出
A
C
B
D • 哥尼斯堡七桥问题 • 七桥问题是发生在18世纪东普鲁土的哥尼斯堡的 一个真实故事。
Hale Waihona Puke Baidu
• 在哥尼斯堡有条普莱格尔河,它有两条支流在城市 中心汇合后流入波罗的海。这条河将城市分割成 四块:A、C两个小岛和B、D两块陆地（如图）。
C
A
B
D
• 为通行方便，在四块陆地之间建了七座桥，每到节、假日 或傍晚，都有许多居民和大学生来此散步。久而久之,人们 发现并热衷于讨论这样一个问题:能否从四块陆地之一出发, 走遍每座桥一次且仅一次然后回到出发地? • 自然有不少人作过实地尝试,但一直未能实现。 • 1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。 欧拉从大家的失败中进行抽象的数学思考,从数学角度成 功地解决了问题。
2、这3点至少2点不相邻，则 G包含3,0为子图。
数学建模-图论
二、图的矩阵表示
邻接矩阵（结点与结点的关系） 关联矩阵（结点与边的关系） 路径矩阵（任意两结点之间是否有路径） 可达性矩阵 直达矩阵 等等……
数学建模-图论
二、图的矩阵表示
1 有向图的邻接矩阵 A = (aij )n×n （n为结点数）
数学建模 -图论 数学建模 -图论
一、图的基本概念 若将图G的每一条边e都对应一个实数F(e), 则称F(e) 为该边的权, 并称图G为赋权图, 记为G = (V, E , F ). 设G = (V, E )是一个图, v0, v1, … , vk∈V, 且 “1≤i≤k, vi－1 vi∈E, 则称v0 v1 … vk是G的一条通路.
问题分析与模型假设：
1. 问题的本质是能否从一地无重复地一次走遍七桥,因 而与所走过的桥的大小、形状、长短、曲直等均无关 ，而只要桥存在，因此不妨将其视为一条弧线
2. 四块陆地可重复经历,至于陆地的大小、形状、质地 等也与问题的本质无关，因而可视四块陆地为四个点 A、B、C、D。
C C A B D B