出版时间:2012-7 出版社:华东师范大学出版社 作者:熊斌,郑仲义 编著 页数:101 字数:116000
Tag标签:无
内容概要
1736年.数学家欧拉由解哥尼斯堡七桥问题而创立了图论这门学科.到现在已经二百多年了。图论是离散数学的骨干内容。而离散数学则是计算机科学技术与网络信息科学的理论基础。《图论(第2版)》通过一些有趣的数学问题和数学游戏,向读者比较通俗地介绍了一些图论的基本知识和图论中常用的初等方法,以扩大中学生的知识面,提高分析问题和解决问题的能力。
作者简介
熊斌第46届、49届、51届、52届和53届国际数学奥林匹克中国队领队、主教练,华东师范大学数学系教授,博士生导师,华东师范大学国际数学奥林匹克研究中心主任。多次参与中国数学奥林匹克、全国高中数学联赛、全国初中数学竞赛、西部数学奥林匹克、女子数学奥林匹克、国际城市青少年数学邀请赛等竞赛的命题工作。在国内外发表了100余篇论文,主编和编著的著作150多本。
书籍目录
1 图的定义
2 顶点的度
3 托兰定理
4 树
5 欧拉问题
6 哈密顿问题
7 平面图
8 拉姆赛问题
9 竞赛图
习题解答
章节摘录
版权页: 插图: 当图G是完全图时,每个顶点的度都是99,所以有100个度为99的顶点。 当图G是非完全图时,G中必有两个不相邻的顶点u和v。显然d(u)≤98,d(v)≤98。因此G中度为99的点的个数l≤98。 如果G中除u和v外另有两个顶点x,y不相邻,则“u”,v,x和y中不存在和其他三个顶点都相邻的顶点,与题意矛盾(与G的性质矛盾)。因此G中除“u,v外任意两个顶点相邻。这说明对G中除u,v外的任意点x,均有d(x)≥97。 如果G中除u、v外的任何x都和u,v相邻,则d(x)=99。此时G中度为99的顶点个数为98。 设G中除u、v外有个顶点x和u、v不都相邻,则有G的性质知,G中除u,v,x外的任意顶点y和u、v、x都相邻。因此d(u)≤98,d(v)≤98,d(x)≤98,d(y)=99。所以G中度为99的顶点个数为97。 这表明含100个顶点的简单图G中,如果任意四个顶点中必有一个顶点和其他三个顶点都相邻,那么G中至少有97个度为99的顶点。 回到原问题,即得:该团体中认识其他所有人的成员最少是97个。 注例题中的成员数100改为任意的n,其他条件不变,则结论为该团体至少有n-3人认识其他所有人。
编辑推荐
《数学奥林匹克小丛书•高中卷12:图论(第2版)》由华南师范大学出版社出版。
图书封面
图书标签Tags
无
评论、评分、阅读与下载