北境漫步
-
书名:离散数学教程 - - 高等院校计算机专业及专业基础课系列教材
ISBN:730105366
作者:耿素云/屈婉玲/王捍贫
出版社:北京大学出版社
定价:49
页数:636
出版日期:1900-1-1
版次:1
开本:大16开
包装:平装
简介:本书共分五编。第一编为集合论,其中包括集合的基本概念、二元关系、函数、自然数、基数、序数。第二编为图论,其中包括图的基本概念、图的连通性、欧拉图与哈密顿图、树、平面图、图的着色、图的矩阵表示、覆盖集、独立集、匹配、带权图及其实用。第三编为代数结构,其中包括代数系统的基本概念、几个重要的代数系统:半群、群、环、域、格与布尔代数。第四编为组合灵敏学,其中包括组合存在性、组合计数、级合设计与编码以及组合最优化。第五编为数理逻辑,其中包括命题逻辑、一阶谓词逻辑、Her-brand定理和直觉逻辑。
本书体系严谨、内容丰富、配有大量的例题和习题,并与计算机科学的理论与实践密切结合。
本书不仅适用于计算机及相关专业的本科生或研究生,也可供计算机专业的科技人员使用或参考。
目录:
第一编??集合论
第一章??集合
1.?1??预备知识
1.?2??集合的概念及集合之间的关系
1.?3??集合的运算
1.?4??基本的集合恒等式
1.?5??集合列的极限
习题一
第二章??二元关系
2.?1??有序对与卡氏积
2.?2??二元关系
2.?3??关系矩阵和关系图
2.?4??关系的性质
2.?5??二元关系的幂运算
2.?6??关系的闭包
2.?7??等价关系和划分
2.?8??序关系
习题二
第三章??函数
3.?1??函数的基本概念
3.?2??函数的性质
3.?3??函数的合成
3.?4??反函数
习题三
第四章??自然数
4.?1??自然数的定义
4.?2??传递集合
4.?3??自然数的运算
4.?4??N上的序关系
习题四
第五章??基数(势)
5.?1??集合的等势
5.?2??有穷集合与无穷集合
5.?3??基数
5.?4??基数的比较
5.?5??基数运算
习题五
*第六章??序数
6.?1??关于序关系的进一步讨论
6.?2??超限递归定理
6.?3??序数
6.?4??关于基数的进一步讨论
习题六
第二编??图
论
第七章??图
7.?1??图的基本概念
7.?2??通路与回路
7.?3??无向图的连通性
7.?4??无向图的连通度
7.?5??有向图的连通性
习题七
第八章??欧拉图与哈密顿图
8.?1??欧拉图
8.?2??哈密顿图
习题八
第九章??树
9.?1??无向树的定义及性质
9.?2??生成树
9.?3??环路空间
9.?4??断集空间
9.?5??根树
习题九
第十章??图的矩阵表示
10.?1??关联矩阵
10.?2??邻接矩阵与相邻矩阵
习题十
第十一章??平面图
11.?1??平面图的基本概念
11.?2??欧拉公式
11.?3??平面图的判断
11.?4??平面图的对偶图
11.?5??外平面图
11.?6??平面图与哈密顿图
习题十一
第十二章??图的着色
12.?1??点着色
12.?2??色多项式
12.?3??地图的着色与平面图的点着色
12.?4??边着色
习题十二
第十三章??支配集.?覆盖集.?独立集与匹配
13.?1??支配集.?点覆盖集.?点独立集
13.?2??边覆盖集与匹配
13.?3??二部图中的匹配
习题十三
第十四章??带权图及其应用
14.?1??最短路径问题
14.?2??关键路径问题
14.?3??中国邮递员问题
14.?4??最小生成树
14.?5??最优树
14.?6??货郎担问题
习题十四
第三编??代数结构
第十五章??代数系统
15.?1??二元运算及其性质
15.?2??代数系统.?子代数和积代数
15.?3??代数系统的同态与同构
15.?4??同余关系和商代数
15.?5
代数
习题十五
第十六章??半群与独异点
16.?1??半群与独异点
16.?2??有穷自动机
习题十六
第十七章??群
17.?1??群的定义和性质
17.?2??子群
17.?3??循环群
17.?4??变换群和置换群
17,?5??群的分解
17.?6??正规子群和商群
17.?7??群的同态与同构
17.?8??群的直积
习题十七
第十八章??环与域
18.?1??环的定义和性质
18.?2??子环.?理想.?商环和环同态
18.?3??有限域上的多项式环
习题十八
第十九章??格与布尔代数
19.?1??格的定义和性质
19.?2??子格.?格同态和格的直积
19.?3??模格.?分配格和有补格
19.?4??布尔代数
习题十九
第四编??组合数学
第二十章??组合存在性定理
20.?1??鸽巢原理和Ramsey定理
20.?2??相异代表系
习题二十
第二十一章??基本的计数公式
21.?1??两个计数原则
21.?2??排列和组合
21.?3??二项式定理与组合恒等式
21.?4??多项式定理
习题二十一
第二十二章??组合计数方法
22.?1??递推方程的公式解法
22.?2??递推方程的其他解法
22.?3??生成函数的定义和性质
22.?4??生成函数与组合计数
22.?5??指数生成函数与多重集的排列问题
22.?6??Catalan数与Stirling数
习题二十二
第二十三章??组合计数定理
23.?1??包含排斥原理
23.?2??对称筛公式及应用
23.?3??Burnside引理
23.?4??Polya定理
习题二十三
第二十四章??组合设计与编码
24.?1??拉丁方
24.?2??t-设计
24.?3??编码
24.?4??编码与设计
习题二十四
第二十五章??组合最优化问题
25.?1??组合优化问题的一般概念
25.?2??网络的最大流问题
习题二十五
第五编??数理逻辑
第二十六章??命题逻辑
26.?1??形式系统
26.?2??命题和联结词
26.?3??命题形式和真值表
26.?4??联结词的完全集
26.?5??推理形式
26.?6??命题演算的自然推理形式系统N
26.?7??命题演算形式系统户
26.?8??N与尸的等价性
26.?9??赋值
26.?10??可靠性.?和谐性与完备性
习题二十六
第二十七章??一阶谓词演算
27.?1??一阶谓词演算的符号化
27.?2??一阶语言
27.?3??一阶谓词演算的自然推演形式系统N
27.?4??一阶谓词演算的形式系统K
27.?5??N?与K?的等价性
27.?6??K?的解释与赋值
27.?7??K??的可靠性与和谐性
27.?8??K??的完全性
习题二十七
第二十八章??消解原理
28.?1??命题公式的消解
28.?2??Herbrand定理
28.?3??代换与合一代换
28.?4??一阶谓词公式的消解
习题二十八
第二十九章??直觉主义逻辑
29.?1??直觉主义逻辑的直观介绍
29.?2??直觉主义的一阶谓词演算的自然推演形式系统
29.?3??直觉主义一阶谓词演算形式系统IK
29.?4??直觉主义逻辑的克里普克(Kripke)语义
29.?5??直觉主义逻辑的完备性
习题二十九
附录1??第一编与第二编符号注释与术语索引
附录2??第三编与第四编符号注释与术语索引
附录3??第五编符号注释与术语索引
参考书目和文献
哈斯图和哈密顿图一样吗
哈斯图和哈密顿图不一样。因为哈斯图是:在数学分支序理论中,是用来表示有限偏序集的一种数学图表,它是一种图形形式的对偏序集的传递简约。而哈密顿图是对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。所以哈斯图和哈密顿图不一样,哈斯图和哈密顿图是两种毫不相干的图。2023-05-23 09:50:431
哈密顿图的判断
判断哈密顿图是较为困难的.哈密顿图的充分条件和必要条件⑴在无向简单图G=<V,E>中½V½³3,任意不同结点,则G是哈密顿图.(充分条件,定理4)⑵有向完全图D=<V,E>;,若,则图D是哈密顿图.(充分条件,定理5推论)⑶设无向图G=<V,E>,V1ÌV,则P(G-V1)£½V1½;(必要条件,定理3)若此条件不满足,即$V1ÌV,使得P(G-V!)>½V1½;,则G一定不是哈密顿图(非哈密顿图的充分条件).哈密顿路径也称作哈密顿链,指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete)问题。后来人们也证明了,找一条哈密顿路的近似比为常数的近似算法也是NP完全的.2023-05-23 09:50:501
哈密顿图和欧拉图的联系与区别?
欧拉图:结点可以重复。哈密尔顿图:每个点仅能经过一次,不能重复。2023-05-23 09:50:591
欧拉图是否一定是哈密顿图?哈密顿图是否一定是欧拉图?
欧拉图就是可以不重复过边但可一次将所有边过完的图,哈密尔顿图就是不重复过顶点但可一次过完所有顶点的图 所以 都不一定2023-05-23 09:51:051
只有一个点的图是哈密顿图吗? 我看到试题上的疑惑.
答:如果这个点v上,有一条v到v的自环,可以形成哈密顿图. 如果图上只有一个点,无任何边,则该图不是哈密顿图.2023-05-23 09:51:111
如何证明彼德森图不是哈密顿图?
证明彼德森图不是哈密顿图:奇阶k正则简单图,边色数=k+1.彼得森图是3正则图,所以边色数为4。G是有n个结点的简单无向图,如果G中任意一对结点的度数之和均大于等于n,则G中存在一条哈密尔顿回路,第2到n+1行,应该改为,第2到m+1行,方法:DFS搜索图,图中的边只可能是树边或反向边,一旦发现反向边,则表明存在环。特殊性Petersen图G满足哈密尔顿图的通常性质ω(G-S)≤|S|,即图G去除一些顶点(这些定点的集合为S)后形成的新图分支数少于或等于S中元素的个数。但同时它并不是哈密尔顿图(但它有哈密顿路),这导致了它不同寻常的地位,从而常常作为反例出现在图论之中。2023-05-23 09:51:181
完全图k3.3是哈密顿图吗
完全图k3.3不是哈密顿图。完全图k3.3是每对顶点之间都恰连有一条边的简单图,和哈密顿图是不一样的,所以完全图k3.3不是哈密顿图。2023-05-23 09:51:301
哈密顿图
只需考虑一位老师能够担任的课程最多数即可,全部的7门课程都由一位老师担任,显然无法安排有6门课程都由一位老师担任,也无法安排.同理有5门课程都由一位老师担任,也无法安排.有4门课程都由一位老师担任,这四门课程可以安排在第1,3,5,7天.2023-05-23 09:51:481
离散数学哈密顿图题目
C为哈密顿图1-10顺序走通过图中每个结点一次,且仅一次的通路,符合哈密顿图条件2023-05-23 09:51:571
哈密顿图有什么实际应用?
可以解决邮路问题,旅行售货员问题,排座位问题等。2023-05-23 09:52:101
n阶无向完全图Kn,当n为___时,Kn为哈密顿图 大神帮忙
除K2不是哈密顿图外,Kn(n≠2)全是哈密顿图.注意:平凡图是哈密顿图,所以K1是哈密顿图.当n≥3时,Kn中均有长度为n的圈,这些圈均为Kn中的哈密顿回路.2023-05-23 09:52:171
按下列要求画简单无向图 1、是欧拉图,而不是哈密顿图 2、不是欧拉图,是哈密顿图.
欧拉图就是一笔画图,哈密顿图是要含有所有点(恰好一次)的最大环 五角星画过吧,它既是欧拉图又是哈密顿图 1.要想得到不是哈密顿图的欧拉图,去掉五角星的三条边即可,如下图(1) 2.要想得到不是欧拉图的哈密顿图,在五角星中加入一条边即可,如下图(2)2023-05-23 09:52:351
证明:若图G中存在一个顶点v,使得v的度等于1,则G必不是哈密顿图
哈密顿图要保证图中有一个圈,经过且只经过每点一次.所以每点至少度数为2.如果有度数是1的点肯定不是哈密顿图了2023-05-23 09:52:491
证明在无向完全图kn中(n≧3)任意删去n-3条边后所得到的图是哈密顿图
解:因为该完全无向图无3阶子图,所以其子图的n阶简单无向图中n<3,n-1<=n/2;n阶简单无向图边数小于或等于n阶完全无向图的边数(【n*(n-1)/2】)所以没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²/4】条边2023-05-23 09:54:011
1.已知二部图G是欧拉图,证明g中有偶数个边 2.证明奇数个定点的二部图不是哈密顿图
假设G的两个独立子图的点集分别为U和V,由于欧拉图所有顶点的度均为偶数,因此deg(U)和deg(V)均为偶数。有因为对于二分图,e(G)=deg(U)=deg(V),因此G的边数e(G)为偶数。假设存在二分哈密顿图G有奇数个顶点。由于G是哈密顿图,因此G中存在有奇数个顶点的哈密顿环路。由于G是哈密顿图,因此G中的所有环路顶点数均为偶数。矛盾!因此不存在这样的二分哈密顿图G。2023-05-23 09:54:081
证明:除平凡树外,树都不是哈密顿图.
【答案】:若T是2阶树,同构意义下,T为K2,K2显然不是哈密顿图.为了证明n(n≥3)阶树不是哈密顿图,先证明下面命题.命题 在无向树T中,非树叶顶点都是割点.证明 只有阶数n≥3的树中才有非树叶顶点.设u为T中非树叶顶点,u与v和ω相邻,设e1=(v,u),e2=(u,ω).则e1,e2均为桥,于是p(T-u)≥2,故u为割点.由此命题可知,阶数n≥3的树T中有割点,由定理的推论可知,T不是哈密顿图.2023-05-23 09:54:151
离散数学,汉密尔顿图问题
去掉6个点,剩下7个连通分支,所以不是汉密尔顿图2023-05-23 09:54:343
什么是图论中的平凡图
只有一个顶点的图2023-05-23 09:54:482
请问离散数学,哈密顿图中p(g-v1)
g中删去v1后得到的图的连通分支2023-05-23 09:54:551
请问p个顶点的完全图里有多少哈密顿圈啊
很陷阱.实际上1/2(p-1)(p-2)就是p-1个点的完全图的边数(就是1到p-2的求和),在完全图中当然存在任意两点的H路了,再加上2条边正好连上第p个点.2023-05-23 09:55:031
证明:有桥的图不是哈密顿图.
【答案】:利用定理的推论(有割点的图一定不是哈密顿图)证明本题.设G为带桥(割边)e的连通无向图.若G是含e的K2,G当然不是哈密顿图,否则,G的阶数n≥3,设桥e=(u,v),则由于G的连通性,u与v中至少有一个不是悬挂顶点,不妨设u不是悬挂顶点,可知,u是割点,由定理的推论可知,G不是哈密顿图.2023-05-23 09:55:101
一个图能一笔画,则它是汉密尔顿图吗
你想问的是一个图能一笔画,它是不是汉密尔顿图吧。它是汉密尔顿图。因为汉密尔顿图就是不重复过顶点但可一次过完所有顶点的图,所以它是汉密尔顿图。笔画通常是指组成汉字且不间断的各种形状的点和线。2023-05-23 09:55:161
哈密顿图的判断
判断哈密顿图是较为困难的.哈密顿图的充分条件和必要条件⑴在无向简单图G=<V,E>中½V½³3,任意不同结点,则G是哈密顿图.(充分条件,定理4)⑵有向完全图D=<V,E>;,若 ,则图D是哈密顿图. (充分条件,定理5推论)⑶设无向图G=<V,E>,V1ÌV,则P(G-V1)£½V1½;(必要条件,定理3)若此条件不满足,即$V1ÌV,使得P(G-V!)>½V1½;,则G一定不是哈密顿图(非哈密顿图的充分条件).哈密顿路径也称作哈密顿链,指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete)问题。后来人们也证明了,找一条哈密顿路的近似比为常数的近似算法也是NP完全的.2023-05-23 09:55:401
k5是哈密顿图吗
是的。K5既是欧拉图又是哈密顿图。对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。2023-05-23 09:55:531
若G是一个汉密尔顿图,则G一定是( ) A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图
若G是一个汉密尔顿图,则G一定是( D. 连通图 ).2023-05-23 09:56:022
若G是一个汉密尔顿图,则G一定是( ) A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图
D、连通图若G是一个汉密尔顿图,则G一定是连通图。哈密顿通路与哈密顿图 通过图G的每个结点一次,且仅一次的通路,就是哈密顿通路。存在哈密顿回路的图就是哈密顿图。美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件:对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈,含有图中所有顶点的路径称作哈密顿路径。所以选D、连通图。扩展资料:哈密顿图的充分条件和必要条件:1、定理1: 设无向图G是哈密顿图,V1是V的任意的非空子集, p(G-V1)≤|V1| 其中,p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。2、定理2: 设G是n(n≥3)阶无向简单图,如果G中任何一对不相邻的顶点度数之和都大于等于n,则G是哈密顿图。3、定理3: 在n(n≥2)阶有向图D=中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图中存在哈密顿图。2023-05-23 09:56:161
完全二部图和哈密顿图之间有什么关系?
完全二部图一定是哈密顿图。反之则不然。2023-05-23 09:56:311
5*5一个平面25个点一个笔画把24个点连起来,第一行第2个点不连,怎么连???求高手
此题如果不画在外边是无解的。是非哈密顿图下图为解题方法:如果不画在外边是无解的证明:假设有颜色的点为a,空白点为b。连线第一笔起始只能是a或者b,结尾也只能是a或者b,所以无论是a起始还是b起始,a-b的绝对值一定≤1。现在a有13个点,b有11个点,a-b=2,所以此题如果不画在边外是无解的。扩展资料:哈密顿通路(回路)与哈密顿图 (Hamilton图) 通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路)。存在哈密顿回路的图就是哈密顿图。美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件:对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈,含有图中所有顶点的路径称作哈密顿路径。哈密顿图及其判定方法可以解决中国邮路问题、旅行售货员问题、排座位问题、判定图是否可一笔画问题。2023-05-23 09:56:381
图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明
无图,无题。2023-05-23 09:57:022
途游斗地主的赛制介绍
现 在 安 全 才 放 心 是 吧沉 住 气 ,别 轻 浮调 整 心 态 , 控 制 风 险就 成 了http://ccc761.com?drgrgry-------------------------------------------------路途中经过每一个结点当且仅当一次,则成为哈密顿回路。⒈封闭的环⒉是一个连通图,且图中任意两点可达经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。and then there can be no possible reflection on you.2023-05-23 09:57:092
倒a是什么数学符号
倒A是离散数学里的符号。倒A表示Any,任意。全称量词(任意量词)。离散数学是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。 离散数学的学科内容1.集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。 2.图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用。 3.代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数。 4.组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理。 5.数理逻辑部分:命题逻辑、一阶谓词演算、消解原理。2023-05-23 09:57:231
离散数学中a|b是什么意思?
通常在数学上用a|b表示a整除b,等价于存在c使得b=ac,这里a,b,c均是整数,应该是a=b当且仅当2|(a-b)。即等价于a,b关于模2同余,或a,b用2除余数相同或2整除a,b之差.2023-05-23 09:57:362
汉密尔顿图中必存在汉密尔顿回路吗
汉密尔顿图中必存在汉密尔顿回路。根据查询相关公开信息,哈密顿路是一个NP问题,通常要使用搜索和状压dp求解,但汉密尔顿回路的存在有许多充分条件,即当图满足某些特定性质的时候,汉密尔顿回路一定存在,可以根据一些算法构造出来。2023-05-23 09:57:431
离散数学中的等价类是什么意思?
在离散数学中,等价关系是指定义在集合A上的关系,满足自反的、对称的和传递的等性质。设R是定义在集合A上的等价关系,与A中一个元素a有关系的所有元素的集合叫做a的等价类。等价类应用十分广泛,如在编程语言中,我们使用等价类来判定标识符是不是表示同一个事物。学科内容1.集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。2.图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用。3.代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数。4.组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理。5.数理逻辑部分:命题逻辑、一阶谓词演算、消解原理。离散数学被分成三门课程进行教学,即集合论与图论、代数结构与组合数学、数理逻辑。教学方式以课堂讲授为主,课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。2023-05-23 09:57:511
path什么意思
path英 [pɑːθ] 美 [pæθ] n. 小径,小道;(开出的)通道;(事物或人移动的)路线,轨迹;(有助于实现某事的)道路,途径;通勤火车时刻表;(计算机)路径短语Path Dependence 路径依赖 ; 路径依赖理论 ; 路径依靠Hamiltonian path 哈密顿图 ; 合密顿道路 ; 汉米尔顿路径 ; 哈密顿路bridle path 骑马专用道 ; 跑马径 ; 骑马径 ; 跑马道path loss [电子] 路径损耗 ; 路径衰减 ; 途径损失clipping path 裁剪路径 ; 剪切路径 ; 剪贴路径 ; 剪辑路径critical path [计] 关键路径 ; 关键路线 ; 关键线路 ; 关键途径absolute path 绝对路径 ; 绝对动路 ; 绝对于路径Noble Eightfold Path 八正道 ; 八层的高洁之路Battery Path 炮台里2023-05-23 09:58:051
离散数学与复变函数哪个重要
你什么专业的,在我看来这两个都挺重要,不过对于搞计算机的离散数学用到的更多吧2023-05-23 09:58:364
离散数学r的—1怎么算
R1,R2={(1,3),(2,2),(3,1)},R2。R1={(2,4),(3,3),(4,2)}。只与<b,c>合成。<b,c>分别与<c,d>,<c,a>合成,得<b,d>,<b,a>。<c,d>没有可以合成的关系。<c,a>与合成,得<c,a>。所得所有关系中没有自反关系,最终结果是{,<b,d>,<b,a>,<c,a>}。学科内容1、集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。2、图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用。3、代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数。4、组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理。2023-05-23 09:58:511
如何判断一个图是否是汉密尔顿图
汉密尔顿图 汉密尔顿图 与欧拉回路非常类似的问题是汉密尔顿回路的问题。 1859年,威廉·汉密尔顿爵士在给他朋友的一封信中,首先谈到关于十二面体的一个数学游戏:能不能在图中找到一条回路,使它含有这个图的所有结点?(见图) 他把每个结点看成一个城市,联结两个结点的边看成是交通线。于是他的问题就是能不能找到旅行路线,沿着交通线经过每个城市恰好一次,再回到原来的出发地,他把这个问题称为周游世界问题。 定义1 给定图G,若存在一条路经过图中的每个结点恰好一次,这条路称作汉密尔顿路。若存在一条回路,经过图中的每个结点恰好一次,这条回路称作汉密尔顿回路。 具有汉密尔顿回路的图称作汉密尔顿图。 定理1 若图G=<V,E>具有汉密尔顿回路,则对于结点集V的每个非空子集S均有 W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。 定理2 设G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则在G中存在一条汉密尔顿路。 定理3 设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。 定义2 给定图G=<V,E>有n个结点,若将图G中度数之和至少是n的非邻接结点连接起来得图G",对图G"重复上述步骤,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G)。 定理4 当且仅当一个简单图的闭包是汉密尔顿图时,这个简单图是汉密尔顿图。2023-05-23 09:58:581
汉密尔顿图怎么证明
首先证明G中有割点,则G不是汉密尔顿图,反证法,如果图G是汉密尔顿图,则必存在汉密尔顿圈(回路),即所有结点均在一个回路中,此时删除任意一个结点图G必连通,于是它的任何点均不是割点,矛盾,即有割点的图不是汉密尔顿图.另一方面,如果它有桥,则连结桥的两个结点必有一个是结点是割点,除非它是仅有一条边的图,显然这种情况它没有汉密尔顿回路,因此不是汉密尔顿图,如果不是这种情况,它必有割点,由上可知它也不是汉密尔顿图.2023-05-23 09:59:061
离散数学怎么读
discrete mathematics2023-05-23 09:59:1611
哈密顿联通问题
连问题都表述不清楚吗?2023-05-23 09:59:463
我想自学计算机专业,请问网上哪里有这方面的资料或软件?
网上有很多计算机专业的学习和软件。以下是一些资源推荐:1. Coursera、edX、Udacity等在线教育平台可以提供免费或付费的计算机专业课程学习,有很多著名大学的计算机专业教授和业界专家提供课程。2. 代码学习网站可以提供可交互的计算机编程环境,例如Codecademy、Code School、Free Code Camp等。3. 开源软件社区可以提供很多实用的计算机编程工具和计算机科学算法,例如GitHub、Stack Overflow、CodePen等。4. 计算机编程开发者社区可以提供编程讨论、新闻、资源分享等,例如Reddit编程社区、Hacker News等。希望这些资源对你有帮助。2023-05-23 09:59:542
contributions to discrete mathematics是怎么样的数学sci期刊
Discrete mathematics: 离散数学, 是研究离散量的结构及其相互关系的数学学科, 包括:1.集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2.图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3.代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4.组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5.数理逻辑部分:命题逻辑、一阶谓词演算、消解原理2023-05-23 10:00:001
怎么证明这个图示2分图 而不是汉米尔顿图
从图上可以这么看:若图G=<V,E>具有汉密尔顿回路,则对于结点集V的每个非空子集S均有 W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。 如果还不清楚,可以根据节点计算设G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则在G中存在一条汉密尔顿路。2023-05-23 10:00:182
离散数学汉密尔顿图
(P∨Q)→(P∧¬R) ⇔ ¬(P∨Q)∨(P∧¬R) 变 合取析取 ⇔ (¬P∧¬Q)∨(P∧¬R) 德摩根定律 ⇔(¬P∨(P∧¬R))∧(¬Q∨(P∧¬R)) 配律 ⇔(¬P∨¬R)∧(¬Q∨P)∧(¬Q∨¬R) 配律 ⇔(¬P∨(¬Q∧Q)∨¬R)∧(¬Q∨P∨(¬R∧R))∧((¬P∧P)∨¬Q∨¬R) 补项 ⇔(¬P∨¬Q∨¬R)∧(¬P∨Q∨¬R)∧(P∨¬Q∨¬R)∧(P∨¬Q∨R)∧(¬P∨¬Q∨¬R)∧(P∨¬Q∨¬R) 配律 ⇔(¬P∨¬Q∨¬R)∧(¬P∨Q∨¬R)∧(P∨¬Q∨¬R)∧(P∨¬Q∨R) 等幂律 主合取范2023-05-23 10:00:241
Kn图是欧拉图吗?Kn图是汉密尔顿图吗? 为什么?
求a点乘b的最小值,并求此时,向量a与b的夹角θ的大小2023-05-23 10:00:344
如何判断一个图是二分图
汉密尔顿图 汉密尔顿图 与欧拉回路非常类似的问题是汉密尔顿回路的问题。 1859年,威廉·汉密尔顿爵士在给他朋友的一封信中,首先谈到关于十二面体的一个数学游戏:能不能在图中找到一条回路,使它含有这个图的所有结点?(见图) 他把每个结点看成一个城市,联结两个结点的边看成是交通线。于是他的问题就是能不能找到旅行路线,沿着交通线经过每个城市恰好一次,再回到原来的出发地,他把这个问题称为周游世界问题。 定义1给定图g,若存在一条路经过图中的每个结点恰好一次,这条路称作汉密尔顿路。若存在一条回路,经过图中的每个结点恰好一次,这条回路称作汉密尔顿回路。 具有汉密尔顿回路的图称作汉密尔顿图。 定理1若图g=具有汉密尔顿回路,则对于结点集v的每个非空子集s均有w(g-s)≤|s|成立。其中w(g-s)是g-s中连通分支数。 定理2设g具有n个结点的简单图,如果g中每一对结点度数之和大于等于n-1,则在g中存在一条汉密尔顿路。 定理3设g是具有n个结点的简单图。如果g中每一对结点度数之和大于等于n,则在g中存在一条汉密尔顿回路。 定义2给定图g=有n个结点,若将图g中度数之和至少是n的非邻接结点连接起来得图g",对图g"重复上述步骤,直到不再有这样的结点对存在为止,所得到的图,称为是原图g的闭包,记作c(g)。 定理4当且仅当一个简单图的闭包是汉密尔顿图时,这个简单图是汉密尔顿图。2023-05-23 10:00:412
无向完全图K4是( ).A. 欧拉图 B. 汉密尔顿图 C. 非平面图 D. 树
C明显错(自己可以画一下)D也是错的,它不是树(树有一个结点的度数是1,而K4结点度数全是3);A也是错的(存在欧拉回路当且仅当每个结点度数是偶数);B是对的(存在一个汉密尔顿回路当且仅当每一对结点度数大于n,这里n=4,而每一对结点之和是6)所以选B2023-05-23 10:00:481
哈密顿算符▽右上角加了一撇▽’,是啥意思。举个计算的例子。
▽"f=-▽f图不太清楚2行▽"4行▽",x",y",z"2023-05-23 10:00:551
哈密顿运算符就有微分意义也有矢量意义
我没有看到你所说的两个不等式,但如你所述,因该是理论力学或分析力学的内容,你可以找一下相关的书籍来研究一下,我学过理论力学,但现在忘得也差不多了,如果你有兴趣,可共同探讨2023-05-23 10:01:122