此讲适合参加全国联赛二试的同学

介绍图论和我们学习的一般的知识点比如函数一样,首先要介绍一些定义,只是图论里的定义相对较多,这里给出部分在竞赛中常用到的:

MT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHP

就像学函数的时候,学了定义和相关概念后我们要学一些性质,比如单调性等等。这里也给出几个图论的竞赛中常见的相关定理:

MT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHP

从这个定理马上可以得出:

MT【90】图论基础知识及相关例题-LMLPHP

注解[1]:平面图必须满足上面边和顶点的关系,在顶点给定时边的数目不能太多。但不是说满足上面式子的就一定是平面图。比如$K_{3,3}$是非平面图,但$n=6,m=9$满足上面的式子.

MT【90】图论基础知识及相关例题-LMLPHP

注解[2]:$K_5$是非平面的.

证明:$n=5,m=10$不满足$m\le3n-6$

事实上:1930年Kuratowski 证明了以下定理:一个图是可平面的,当且仅当它不含$K_5$或者$K_{3,3}$构型的子图.

但问题是找这两种子图也不是那么容易.

MT【90】图论基础知识及相关例题-LMLPHPMT【90】图论基础知识及相关例题-LMLPHP

一般的有以下著名定理:

MT【90】图论基础知识及相关例题-LMLPHP

05-11 15:41