钱培星
【摘要】 图论作为一门数学分支历史悠久,从哥尼斯堡城的七桥问题至今,发展迅速,也受到数学竞赛的青睐。本文从2016年数学联赛的第三题谈起,介绍了图论的相关概念及一般的解题方法,最后再给出该题的较为简便的解法。
【关键词】图论问题 数学竞赛 解题方法
【中图分类号】G633.6 【文献标识码】A 【文章编号】2095-3089(2017)07-0123-02
圖论作为一个重要的数学分支,几千年前,我国的河图、洛书就已经涉及到一些简单有趣的图论问题。18世纪,哥尼斯堡七桥问题使得图论作为一门真正的学科进入学者们的视野。而近二十年来,由于计算机科学、编码理论、规划论、数字通讯、实验设计等学科的迅猛发展,提出了一系列的需要离散数学解决的理论和实际问题,使得图论的研究更为活跃。由于图论蕴含的数学思想丰富,图形简洁美观,证明巧妙,方法千变万化,非常灵活,因而备受数学竞赛的青睐。今年的高中数学联赛加试第三道题就是一道以图论为背景的题:
给定空间中10个点,其中任意四点不在一个平面上,将某些点之间用线段相连,若得到的图形中没有三角形也没有空间四边形,试确定所连线段数目的最大值。
在解决这道图论问题前,我们先来介绍一下图论的一些定义和概念:
一、图论相关的基本定义和基本概念
图由一个点集合V和一个连接某些点对的线段的集合E构成的图形称为图。记作G(V,E).其中,V中的点称为顶点,E中的线段(不一定是直线段)称为边。通常|V|和|E|表示顶点个数和边的数量。……