图论

作者简介

奥数小丛书·高中卷12（第二版 图论），ISBN：9787561791714，作者：熊斌，郑仲义 编著

书籍目录

1 图的定义
2 顶点的度
3 托兰定理
4 树
5 欧拉问题
6 哈密顿问题
7 平面图
8 拉姆赛问题
9 竞赛图
习题解答

编辑推荐

《数学奥林匹克小丛书•高中卷12:图论(第2版)》由华南师范大学出版社出版。

内容概要

熊斌第46届、49届、51届、52届和53届国际数学奥林匹克中国队领队、主教练，华东师范大学数学系教授，博士生导师，华东师范大学国际数学奥林匹克研究中心主任。多次参与中国数学奥林匹克、全国高中数学联赛、全国初中数学竞赛、西部数学奥林匹克、女子数学奥林匹克、国际城市青少年数学邀请赛等竞赛的命题工作。在国内外发表了100余篇论文，主编和编著的著作150多本。

章节摘录

版权页：   插图：   当图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人认识其他所有人。

图书封面

---

 图论下载

---