切换科目
重点科目
主要科目
次要科目
科数网
首页
刷题
学习
VIP会员
赞助
组卷
集合
教材
VIP
写作
游客,
登录
注册
在线学习
离散数学
第五章 图论
图论模型初步
最后
更新:
2025-01-22 09:30
查看:
101
次
反馈
能力测评
会员8.2元/月
赞助
图论模型初步
我们可以用数学模型来抽象和简化现实世界,将一个现实世界中的问题 A 对应到一个便于思考或有求解方法的数学模型 B 。 图论模型是数学模型的一个分支。在图论模型中,顶点可以代表任何事物,如人,城市等;边表示顶点间的关系;因此图是关系的数学表示。而图论建模就是对一些客观事物进行抽象,化简,并用图来描述事物特征及内在联系的过程。 在前几节中已经给出了几个通过图论模型解决问题的实例。在本节中,将通过一些实例来初步说明如何利用图论模型求解问题。 例 8.6 一个部门有 25 人,对于某个问题,这 25 人存在着各自的看法,那么是否存在这样的情况:在这 25 个人中,每个人恰与另外 5 个人对该问题的看法一致? 利用图论模型求解问题,首先就要明确在建立一个图论模型时,这个图是什么?即什么是顶点?什么是边? 图是关系的数学表示,在本例中,顶点表示人,边表示两个顶点之间"意见一致"的关系,因此在两个"意见一致"的人对应的顶点之间有一条边。所以本例的图论模型由 25 个顶点组成,如果要求"每个人恰与另外 5 个人对该问题的看法一致",则要求每个顶点的度数为 5 。由定理 8.3 可知,这样的图不存在,所以不存在这样的情况:"在这 25 个人中,每个人恰与另外 5 个人对该问题的看法一致"。 例 $8.7 n$ 支篮球队( $n \geqslant 4$ )进行比赛,比赛已经进行了 $n+1$ 场,则存在一个球队,它至少参加过 3 场比赛。 证明:首先,用图论模型表示这一问题:$n$ 个球队用 $n$ 个顶点表示;两个球队之间进行了一场比赛,则在相应的两个顶点之间有一条边相连。这样,原问题就转化为:图 $G$ 有 $n$ 个顶点 $(n \geqslant 4), n+1$ 条边,要求证明在图 $G$ 中存在顶点 $v, d(v) \geqslant 3$ 。 如果在图 $G$ 中不存在这样顶点 $v$ ,即在图 $G$ 中所有的顶点度数都是小于等于 2 ,因为图 $G$ 有 $n$ 个顶点,所以图 $G$ 的所有顶点度数之和小于或等于 $2 n$ ,又因图 $G$ 有 $n+1$ 条边,由定理 8.2 可知,图 $G$ 的所有顶点度数之和为 $2(n+1)$ 。因此导致矛盾,所以命题成立。 例 8.8 今有 $a, b, c, d, e, f,
免费注册看余下 70%
非VIP会员每天5篇文章,开通VIP 无限制查看
《高等数学》难点解析
高数教程
泰勒公式
切线与法线
切平面与法平面
驻点·拐点·极值点·零点
间断点
渐进线
瑕积分
欧拉方程
伯努利方程
Abel 收敛定理
偏导数的几何意义
偏导数的几何意义
梯度
数量场与向量场
多元函数极值
拉格朗日算子
通量与散度
环流量与旋度
格林公式
高斯公式
斯托克斯公式
三大公式比较
傅里叶级数
极坐标微元
点法式方程
变上限定积分
X型计算面积
Y型计算面积
微分的意义
渐近线
间断点
y''+py'+qy=f(x)方程
高斯
黎曼
傅里叶变换(复数)
拉普拉斯变换(复数)
高等数学测评
函数与极限
一元函数微分学
一元函数积分学
微分方程
空间向量与代数
多元微分学
多元积分学
无穷级数
《线性代数》难点解析
线代教程
近世代数对数学的整体思考
线性的意义
矩阵乘法(列视角)
矩阵乘法(行视角)
矩阵左乘
矩阵右乘
逆矩阵求解方程组
阶梯形矩阵的求法
方程组解的判定
四阶行列式的计算
线性变换的意义
线性空间
向量组的等价
线性空间的几何意义
基础解系的求法
施密特正交化
特征值与特征向量的意义
矩阵相似的几何意义
矩阵可对角化的理解
秩的意义(向量版)
秩的意义(方程版)
二次型的意义
线性代数测评
行列式
矩阵
向量空间
《概率论与数理统计》难点解析
概率教程
置信区间与上a分位数
概率中的“取”与“放”
贝叶斯公式
全概率公式
泊松分布
指数分布
伽玛分布
二维密度图的意义
卷积的意义
相关系数的意义
k阶矩是与矩母函数
卡方分布的作用
单正态区间估计理解
假设检验理解
切比雪夫不等式
中心极限定理
概率统计测评
事件与概率
一维随机变量与事件
多维随机变量与事件
随机变量的数字特征
大数定律与中心极限定理
统计量与抽样分布
参数估计
假设检验
上一篇:
最短路
下一篇:
平面图与欧拉公式
本文对您是否有用?
有用
(
0
)
无用
(
0
)
更多
学习首页
数学试卷
同步训练
投稿
会议预约系统
数学公式
关于
Mathhub
赞助我们
科数网是专业专业的数学网站 版权所有
本站部分教程采用AI制作,请读者自行判别内容是否一定准确
如果页面无法显示请联系 18155261033 或 983506039@qq.com