浅析图论教学

翟明清

(滁州学院数学系,安徽滁州 239000)

浅析图论教学

翟明清

(滁州学院数学系,安徽滁州 239000)

图论是《离散数学》课程的重要组成部分,也是数学专业高年级的选修课程.本文介绍了从事图论教学和研究的一些心得,探讨了如何在该课程的教学过程中激发学生的学习兴趣和培养学生的发现问题及解决问题能力,从而为学生今后作毕业论文或者进一步从事科学研究打下基础.

离散数学;图论;教学

1 引 言

图论是离散数学和组合数学的重要分支.它以图为研究对象,这种图由若干给定的点及连接两点的边所构成,通常用来描述某些事物之间的某种特定关系,以点代表事物,以连接两点的边表示两个事物间具有这种关系.

图论起源于著名的柯尼斯堡七桥问题.当时哥尼斯堡城的居民有郊游的习惯,在城郊的普雷格尔河中有两个小岛,有七座桥将两个小岛和两边河岸连接起来,问一个人能否从其中某一块陆地出发不重复地走遍七座小桥,再回到起点?然而无数次的尝试都没有成功.瑞士数学家欧拉在1736年证明了这个问题没有解,他用抽象分析法将这个问题转化为一个图论问题：即把每一块陆地看成一点,每一座桥看成一条边,从而得到一个图.欧拉关于该问题的研究《依据几何位置的解题方法》也被公认为图论领域的第一篇论文.此后,一些著名的图论问题,如四色猜想,哈密顿问题,Rem sey数问题,图的重构问题等陆续被提出,它们推动了图论理论研究的日益完善和深入.上世纪中期,随着计算机科学的飞速发展,图论成为数学中发展最快的分支之一.图论从它诞生开始就显示了它的应用价值.如今,图论在计算机理论科学,运筹学,系统科学,化学,生物学等很多学科领域都有着重要的应用.

图论有别于一些数学基础课程,它与实际问题密切联系,强调数学应用能力的培养,它解决问题的方法没有连续性和固定套路,非常灵活,往往一个问题一种解法.这些特征促使教师在教学中要避免填鸭式的讲授,而应在讲解知识的过程中激发学生的学习兴趣和创造性思维能力.那么如何在教学中达到这种理想的目的呢?我认为关键词就是“兴趣”和“问题”.因为最好的学习动机是兴趣,最好的学习方式是带着问题学习.下面将围绕它们谈一谈图论教学中的体会.文中涉及到的一些概念和术语如无详细说明,可参见[1-3].

2 设计好第一次课

很多同学经过一、二年级的数学基础课和专业课学习之后,很容易对数学产生这样的印象：枯燥,难懂,脱离实际.甚至认为如果以后不当教师或从事科研,数学学得再好也没什么用.这些想法容易伤害学习积极性,是非常要不得的,图论课为我们改变学生的这些想法提供了一个契机.为此,第一次课要出奇制胜,要让学生从第一次课开始就产生这样的想法：原来数学课程也可以这么轻松有趣,这么贴近现实生活.为了达到此目的,我们不妨从一个童年时期的智力题或故事开始.

例1传说楚汉时期的著名将领韩信不光是一个军事家还是一个数学天才.一次行军途中,他看到路边两位老农在争吵,上前了解原因,原来是为了分油不均而相持不下.他们手中有一个装满了油(容量10斤)的油篓,以及一个容量7斤的空油罐和一个容量3斤的空油葫芦,但是3个容器上都没有刻度,也没有测量工具.韩信略一思考,丢下一句话便匆匆上路,两位老农稍稍一愣,方然领悟.原来韩信说的是“葫芦归罐罐归篓”.“葫芦归罐罐归篓”的意思是：一次次的将油从油篓中倒向油葫芦,油葫芦装满就向油罐里倒,油罐装满就向油篓里倒,如此反复,若干次后,就可以将油均分为两份.韩信给出了该问题的一种可行解,那么还有没有其他办法呢?韩信的办法是不是最优的呢?

例2猎人带着一担白菜,一只羊和一条狼要过河.但是只有一条小船,只有猎人会划船并且他一次至多只能带白菜,羊,狼三者之一过河.如果让狼和羊在一起,而猎人不在旁边的话,狼就会把羊吃掉.如果让羊和白菜在一起,而猎人不在旁边的话,羊就会把白菜吃掉.问如何让他们都平安过河?

类似上述的问题有很多,方法往往也不止一种,摸索一下,我们也不难找到某种可行的办法.但要找出所有的可行解以及最优解,就需要建立图的模型.以例1为例,我们可以将油所在的状态用一些有序3元组表示,其中第一、二、三个分量分别表示当前时刻篓、罐、葫芦中油的储量.如初始状态为〈10,0,0〉,其他可能状态为〈7,3,0〉,〈7,0,3〉,〈1,6,3〉,〈3,7,0〉,〈3,4,3〉,〈5,5,0〉,〈5,4,1〉,〈5,3,2〉,〈2,5,3〉等等.然后将这些有序3元组看成顶点,从一个顶点A到另一个顶点B连一条有向边当且仅当A所代表的状态可以一次到达B所代表的状态,这样得到一个有向图.图中从顶点〈10,0,0〉到顶点〈5,5,0〉的所有有向路构成了所有的可行解.而最短有向路则为最优解.

这样的问题生动而有趣,同时能反映图论的“神奇”——实际问题可以转化为图的模型求解.

3 激发学生的学习兴趣

图论的每一章节往往以某个概念为中心展开,介绍与之相关的其他概念,定理,公式或算法等等.这个概念就是这一章节的关键词,要激发学生的学习兴趣,就必须事先告诉大家这个概念的实际背景,研究它有什么用.为此,在给出这个概念之前,我们同样可以从日常生活中的一个小问题入手.例如,在引入平面图定义之前,可给出下述问题.

例3有3个野人住在一个原始森林里的3个不同地方,他们每天都要到另外3个不同的地方获取果实,水和柴火.然而由于山路崎岖狭窄,当他们在路上相遇时,经常发生争吵甚至打架.为了他们能够长期和谐相处,能否为他们设计路线,使得他们永远也不在途中相遇?

这个问题抽象成图模型就是完全二部图K3,3是否存在一种平面画法,使得任意两条边不交叉?这个问题是无解的.同学们自然要问为什么——找不到并不能说明没有啊.接着告诉大家这个“为什么”的答案就在这一章节的内容中并随即引入平面图的概念：一个图称为平面图,如果它可以画在平面上使得任意两条边不交叉.

在引入色数,控制数,匹配数,哈密顿图等中心概念之前,我们也不难找到一些实际问题与之对应.这些日常生活中的小问题,有时比高谈阔论更有用,它能让同学们立即产生兴趣并对所要研究的概念印象深刻.

4 如何发现问题

前文已经强调了问题在学习中的重要性.然而,要提高学生对学习的主动积极性,就必须让学生自己想出一些问题并试着解决它.授人以鱼不如授人以渔.给学生一个好问题,不如教会学生如何发现问题.一位数学家也曾经说过,发现问题有时比解决问题更为重要.如何在图论教学过程中培养学生的发现问题能力呢?在讲解一个图的概念,模型及其相关性质时,我们应该经常提醒学生发散自己的思维,去建立一个新的概念,模型并研究其性质.当然,这种发散不是漫无边际的发散,通常是基于原有概念(模型)的推广或者迁移.

以图的着色概念为例,图G的一个k-着色是指用{1,2,…,k}中的元素对图G的所有顶点标号,使得任意两个相邻顶点标号不同.图G的色数是指能使图G存在一个k-着色的最小整数k.色数模型的实际应用有很多,比如,电台的频率分配问题.一些城市的广播电台需要分配频率,为了尽可能避免相互干扰而又不占用过大的频宽,可以让邻近的城市使用不同频率,而相距甚远的城市则不做要求.在学习了色数的概念和性质后,可以启发同学们:频率分配问题抽象成色数模型有些简单化,很多情况下并不能满足避免干扰的要求,为了更好的降低干扰,我们该怎么办?

可将该问题留作课后作业,鼓励大家提出改进模型的办法.并提醒大家注意两个原则:合理性和可行性.合理性就是建立的模型要尽可能好的达到我们的目的,可行性就是模型不能太复杂,要便于求解.二者很多情况下是矛盾的,需要在它们之间寻求平衡.事实上,上述问题就是一个典型的模型推广问题.我们可以定义一种k-L(p,q)着色:用{1,2,…,k}中的元素对图G的所有顶点标号,使得任意两个相邻顶点(距离为1的顶点)标号之差不小于p,任意两个较为接近的顶点(如距离为2的顶点)标号之差不小于q,这里p≥q为非负整数.显然,普通着色就是L(p,q)着色的一个特例,即L(1,0)着色.

又如,在平面图内容中,欧拉公式,极大平面图的性质等都是重要知识点.可以启发同学们:既然完全图K5和完全二部图K3,3都不能嵌入平面,它们能否嵌入环面呢,如何嵌入呢?更一般地,环面图的欧拉公式应该是什么样的?极大环面图又有那些性质以及如何证明呢?这些问题都是典型的模型迁移问题——从平面图到环面图.

5 如何解决问题

尽管如前文所说,图论解题的具体方法是灵活的,离散的,我们还是可以在教学过程中有意识的训练学生的宏观证明思想.通常来说,证明图论命题有以下五种基本思想:归纳法思想,反证(归谬)法思想,极图思想,图变换思想,构造或算法思想.有时它们需要结合使用.

归纳法适用于以下情形:所研究的图对某种性质具有遗传性,即它可以退化为更小的图而保持该性质.例如树删去一个悬挂点仍为树;完全图删去任一个点仍为完全图.反证法适用于:不符合命题结论的图比符合命题条件的图具有更为明确的结构特征或性质.此时考虑不符合命题结论的图,则容易推出矛盾.极图思想是指在图中找一个具有某种特征的极大(小)子图,利用其极大(小)性来证明结论或推出矛盾.

例4证明每颗非平凡有限树至少两个叶子.

证 这个命题可以对顶点数做归纳来证明.下面用更简单的极图思想证明.设P是树中的一条最长路,u和v是其两个端点.既然P是最长的,u和v均不能有P之外的邻居.又因为树中不能有圈,从而u,v均只有一个邻居,即u,v为叶子.

图变换思想是指将所面对的图模型转换为一个新的图模型,利用新模型的特征或已有性质来证明结论.图论中著名的最大流最小割定理就可以图变换后利用Menger定理来证明.证明一些图论问题是N P完全的,通常也是将一已知的N P完全问题在多项式时间内图变换为该问题.

例5 设图G中每个顶点均为奇度点,则经过G的每条边的哈密顿圈(即经过所有顶点恰好一次的圈)均有偶数个.

证 先引入一定义:设P=u1u2…un为图中的一条哈密顿路(即经过所有顶点恰好一次的路),ui (i≠n-1)为un的邻居,则称哈密顿路Q=u1u2…ui un un-1…ui+1为P诱导的哈密顿路.显然,P诱导的哈密顿路的数目是un的邻居数减去1,且Q也诱导P.

任取边uv,若无哈密顿圈经过uv,命题成立.否则,设P1,P2,…,Pt为图G-uv中从u出发的所有哈密顿路,其中P1,P2,…,Ps(s≤t)为从u到v的所有哈密顿路,只需证明s为偶数即可.为此,定义一个新的图H:以P1,P2,…,Pt为顶点,Pi与Pj在H中邻接当且仅当在G-uv中Pi诱导Pj.则每个点Pi(1≤i≤s)在H中有奇数个邻居,每个点Pj(s+1≤j≤t)有偶数个邻居.由握手定理,H中所有点的邻居数之和为偶数,从而s为偶数.

构造或算法思想适用于证明某种结构或方案的存在性,尤其是确定图的一些结构参数的值或界时经常使用.例如,考虑控制数,色数等问题时,直接构造或由算法产生一个我们需要的控制集,着色方案等等.

例6图G的一个2-稳定集是指G的一个顶点子集使得其中任两个点之间距离大于2.图G的一个控制集是指G的一个顶点子集使得G的任何其他点都有邻居在其中.G的2-稳定数α(G)是指G的最大2-稳定集的基数,G的控制数γ(G)是指G的最小控制集的基数.证明对任一颗树T, α(T)=γ(T).

证首先证明对任何图G,α(G)≤γ(G).设S是一最大2-稳定集,则S外每个点在S中至多一个邻居,从而S就需要|S|个顶点才能控制,故γ(G)≥|S|.

下面证明对任一颗树T,α(T)=γ(T).为此,设计一算法产生一个2-稳定集S和一个控制集D使得|S|≥|D|(对于树这个算法是简单的,这里略去了).于是

这意味着α(T)=γ(T).

[1] Bondy J A,Murty U SR.Graph theo ry w ith applications[M].No rth-Holland：Elsevier,1976.

[2] Chartrand G,Oellermann O R.App lied and algorithmic graph theory[M].New Yo rk：McGraw-Hill,1993.

[3] West D B.Introduction to graph theo ry[M].New Jersey：Prentice Hall,2001.

Brief Talk about Graph Theory Teaching

Zhai Ming-qing
(Department of Mathematics,Chuzhou University,Chuzhou 239000,China)

Graph theo ry is an important component of Discrete Mathematics and an op tional course for higher grade studentsmajo ring in Mathematics,too.Some experience in teaching and studying p ractice is introduced in this paper. And it is exp lo red that how to invite the students’interest in studying Mathematics and train the abilities finding p roblem and solving p roblem.Thus this can make a good base for the students doing paper,studing and researching fo r the further.

discretemathematics;graph theo ry;teaching

G642.1

C

1672-1454(2011)05-0203-04

2009-01-06