GeoGebra脚本程序在开放教育图论教学中的应用

汪 吉

(武汉市广播电视大学 汉阳区分校，湖北 武汉 430050)

一、引言

离散数学是开放教育计算机本科层次的一门专业基础课。图论作为离散数学的重要内容之一,其研究对象是由点和线组成的拓扑图形,通过这些图形能方便地模拟现实中各种关系系统。图论在数据结构、程序设计、操作系统、计算机网络等学科中有着十分重要的作用。但在实际教学中,由于其理论抽象、方法灵活、算法复杂,许多学生对这一部分掌握得不太理想。因此,本文针对开放教育的特点,就如何提高图论的教学效果做了一些探索。

二、图论教学中引入GeoGebra软件的必要性

GeoGebra是由美国数学家MarkusHohenwarter设计的结合代数、几何、微积分于一体的动态数学软件,它以点、线、向量、函数为基本操作对象,同时支持可编程操作。软件能将计算和编程的结果以直观、动态的图形展现出来,并可导出为GIF动图或网页,十分便于网上学习和资源共享,是适合开放教育图论教学的有力工具。

(一)利用GeoGebra增强图论教学的直观性

图论以图为研究对象,教学中涉及大量图形的绘制,如完全图、正则图、欧拉图、汉密尔顿图等,绘图往往占据了大量的教学时间。利用GeoGebra可以方便地绘制各种标准图形,还能加以交互性演示,如对图中的边或结点进行移动或着色等,有助于学生对概念的理解。图论以算法为研究重点,教学中涉及各种算法的讲解,如求最短路径的Dijkstra算法、求欧拉回路的Fleury算法、求最小生成树的Kruskal算法等。这些算法在表述上大都抽象且形式化,而开放教育学生数学基础薄弱,理解起来比较困难。利用GeoGebra可以将算法的执行过程分解步骤地演示出来,让学生分析每一步的作用和目的,有助于学生对算法的掌握。

(二)利用GeoGebra提高图论教学的实用性

对于开放教育的学生而言,图论的教学在传授理论知识的同时,更应该重视应用能力的培养。GeoGebra除了大量的内置命令外,还提供JavaScript脚本编程功能,能创建更高效、更强大的教学应用程序。JavaScript作为面向Web的编程语言,是互联网时代应用最广泛的编程语言之一,也是网页设计和Web应用必须掌握的开发工具。同时JavaScript程序设计也是开放教育计算机本科的一门重要的专业课。通过JavaScript编程来解决数学问题,不但可以加深学生对数学理论、数学模型的理解和运用,同时对学生的算法分析、程序设计能力也是很好的锻炼。

三、GeoGebra在图论中的教学应用实例

图的着色是图论中的一个重点问题。韦尔奇鲍威尔法是对任意图进行结点着色的经典算法。下面以GeoGebra Classic 5中文版为平台,探讨在GeoGebra中如何利用JavaScript脚本编程辅助算法的教学。

(一)韦尔奇鲍威尔着色算法原理

韦尔奇鲍威尔法:

Step1.将图的结点按照度数降序排列。

Step2.对排序后的第1个结点着第1种色,并按照次序,对与前面已着色点不邻接的每一个点依次着上相同的色。

Step3.对尚未着色的结点用第2种色重复Step2,接着用第3种色继续,直到所有结点全部完成着色。

(二)韦尔奇鲍威尔着色算法实现

Step1:在绘图区中新建一个滑动条“n”,取值为从1到10的整数,标题为“结点数n”。

Step2:在绘图区中新建按钮button1,命名为“生成图”。右击按钮,选择“属性/脚本”,在“单击时”标签中选择“JavaScript脚本”,输入以下命名:

n=ggbApplet.getValue("n");

for (var i=0;i<10; i++){

ggbApplet.deleteObject("V_{"+i+"}");}

for (var i=0;i<10; i++){

for(var j=0; j<10; j++){

ggbApplet.deleteObject("a_{"+i+","+j+"}");}}

ggbApplet.deleteObject("text1");

ggbApplet.deleteObject("text2");

ggbApplet.deleteObject("text3");

ggbApplet.deleteObject("text4");

for(var i=0;i

ggbApplet.evalCommand("V_{"+i+"}=(4;("+i+"*(360/"+n+"))°)");

ggbApplet.evalCommand("SetColor(V_{"+i+"},"LightGray")");

ggbApplet.setPointSize("V_{"+i+"}", 9);}

var A=[];

var row=[];

var degree=[];

var node=[];

for (var i=0; i

degree[i]=0;

鸡新城疫是由副黏病毒引起的高度接触性传染病，有强毒株和弱毒株两类。近年来，由于鸡群正常进行鸡新城疫疫苗接种，因此本病多呈非典型性发生，主要发生于免疫鸡群，尤其是二免前后的鸡。有一定抗体水平的免疫鸡群，病情比较缓和，发病率和死亡率都不高；成鸡产蛋量突然下降5%～12%，严重者在50%以上，并出现畸形蛋、软壳蛋和糙皮蛋。

for(var j=0; j

if(j>i){ggbApplet.evalCommand("a_{"+i+","+j+"}=floor(random()*2)");}

else if(i>j){ggbApplet.evalCommand("a_{"+i+","+j+"}=a_{"+j+","+i+"}");}

else{ggbApplet.evalCommand("a_{"+i+","+j+"}=0");}

a=ggbApplet.getValue("a_{"+i+","+j+"}");

if((j>i)&&(a)){ggbApplet.evalCommand("e_{"+i+","+j+"}=Segment(V_{"+i+"},V_{"+j+"})");

ggbApplet.evalCommand("ShowLabel(e_{"+i+","+j+"},false)");}

degree[i]=degree[i]+a;

A[i]="{"+row+"}";

node[i]="{"+i+","+degree[i]+","+0+"}";}

for(var i=0;i

ggbApplet.evalCommand("SetCaption(V_{"+i+"},"V_{"+i+"}("+degree[i]+")")");}

ggbApplet.evalCommand("degree={"+degree+"}");

ggbApplet.evalCommand("text1=Text("邻接矩阵A=",(7,3.5),false,true)");

ggbApplet.evalCommand("A={"+A+"}");

ggbApplet.evalCommand("text2=Text(FormulaText[{"+A+"}],(7,2.5),false,true)");

ggbApplet.evalCommand("node={"+node+"}");

ggbApplet.evalCommand("node_{ordered}={}");

ggbApplet.evalCommand("SetValue(node_{ordered},Reverse(Sort(node,degree)))");

∥将图的结点按照度数降序排列。

ggbApplet.evalCommand("c1=Element(Transpose(node_{ordered}),3)");

ggbApplet.evalCommand("c2={}");

ggbApplet.evalCommand("SetValue(c2,Sequence("Uncolored",i,1,n))");

ggbApplet.evalCommand("k=0");

ggbApplet.evalCommand("count=0");

Step3:在绘图区中新建按钮button2,命名为“着色”。右击按钮,选择“属性/脚本”,在“单击时”标签中选择“JavaScript脚本”,输入以下命名:

var l_c=["Red","Yellow","Blue","Green","Black","Pink","Brown","Violet",

"Orange","White"];

ggbApplet.evalCommand("list_{color}={}");

for(i=0;i<9;i++){

var j=i+1;

ggbApplet.evalCommand("SetValue(list_{color},"+j+",""+l_c[i]+"")");}

n=ggbApplet.getValue("n");

var vertex=[];

for(var i=0;i

var j=i+1;

vertex[i]={index:ggbApplet.getValue("Element(Element(node_{ordered},"+j+"),1)"),

degree:ggbApplet.getValue("Element(Element(node_{ordered}),"+j+"),2)"),

color:ggbApplet.getValue("Element(c1,"+j+")")};}

var k=ggbApplet.getValue("k");∥k为着色数。

var count=ggbApplet.getValue("count");

k++;

for(var i=0;i

if(vertex[i].color) continue;

var ok=true;

for(var j=0;j

if(!ggbApplet.getValue("a_{"+vertex[i].index+","+vertex[j].index+"}")) continue;

if(vertex[j].color==k){

ok=false;

break;}}

if(!ok) continue;

vertex[i].color=k;

count++;}

ggbApplet.evalCommand("SetValue(k,"+k+")");

ggbApplet.evalCommand("SetValue(count,"+count+")");

for(var i=0;i

var j=i+1;

if(vertex[i].color){

ggbApplet.evalCommand("SetColor(V_{"+vertex[i].index+"},Element(list_{color},"+vertex[i].color+"))");

ggbApplet.evalCommand("SetValue(node_{ordered},"+j+",{Element(Element(node_{ordered},"+j+"),1),Element(Element(node_{ordered},"+j+"),2),"+vertex[i].color+"})");

ggbApplet.evalCommand("SetValue(c2,"+j+",Element(list_{color},"+vertex[i].color+"))");}}

ggbApplet.evalCommand("text3=Text("着第""+k+""种颜色",(15,4),false,true)");

ggbApplet.evalCommand("list1={}");

ggbApplet.evalCommand("SetValue(list1,Transpose(node_{ordered}))");

ggbApplet.evalCommand("SetValue(list1,3,c2)");

ggbApplet.evalCommand("list2=Transpose(list1)");

ggbApplet.evalCommand("list3=Reverse(Sort(list2,Element(Transpose(list2),1)))");

ggbApplet.evalCommand("headline={"结点序号","结点度数","结点颜色"}");

ggbApplet.evalCommand("list=Reverse(Append(list3,headline))");

ggbApplet.evalCommand("text4=Text(TableText(list,"c|_"),(15,3),false,true)");

if(count==n){alert("着色完毕")};

在上面的程序中,拖动滑动条,单击“生成图”按钮,随机生成一个结点数为n的无向图,图中的结点均未着色,同时计算出该图的邻接矩阵,如图1。然后单击“着色”按钮,利用韦尔奇鲍威尔法进行着色,所用颜色数、结点序号、结点度数、结点颜色以表格的形式同步显示在右侧。每单击一次,用一种颜色着色,当所有结点全部上完色,弹出提示框“着色完毕”,如图2。

在教学演示时,教师先让学生观察图,自主判断韦尔奇鲍威尔法当前步骤的执行结果,然后再点击按钮加以显示。每单击一次按钮后预留足够的间歇时间,给学生思考和计算。对于JavaScript代码,可根据学生对JavaScript程序设计课程的掌握情况,作适当地讲解。同时将GeoGebra程序文档发布到网上,供学生自行下载学习。

图1 生成图及邻接矩阵

图2 韦尔奇鲍威尔着色算法

四、结语

利用GeoGebra软件,结合JavaScript脚本编程,可以开发出适合图论的教学程序。通过动态的演示展现算法的执行过程,激发了学生的学习兴趣,加深了学生对复杂、抽象理论的理解。更为重要的是借助编程解决数学问题,培养了学生的算法分析、程序设计等职业技能,促进了开放教育计算机专业应用型人才的培养。