资源描述:
《十、求图的所有适当着色》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、求图的所有适当着色(1)功能设G是n个顶点的一个图,并设Lam是给定的一个正整数。现在给每个顶点指定一种颜色ai(1<=ai<=Lam,I=1,2,····,n),且G中的每条边e的两个端点都被指为不同的颜色。于是向量(a1,a2,····,an)就表示图G是用Lam种颜色的一种适当着色。(2)调用方式先输入顶点个数(3~9),点“确定”后将出现顶点图示,然后输入颜色数量,再将每条有向边按起始点、终点输入。每输入一条边起、终点后,按“输入”确认,就可在图形中显示该边。当所有边输入完毕后,按“完成”键,将计算所有的适当着色。然后点击下方的“下一个”或“上一个”按钮将在图上用有色点表示出每一
2、组适当着色。(3)算法说明利用回溯算法一步一步的构造适当着色,并且在每一步都进行测试,看看局部构造的向量是否有可能扩充为一个适当着色,若不能就立即删除它并转到下一步。(4)程序清单DimansAsStringDimPIAsDoubleDimstack(37),ep(3,37),st(999,10),pm(10,10),om(10,10),A(11),z1(10),x(10),y(10),d(11)AsIntegerDimb,h,nc,i,j,c,e,k,m,n,p,q,sAsIntegerDimlinei,LamAsIntegerDimindex,col(11)AsBooleanSubs
3、tep1()index=Truek=1stack(1)=1stack(2)=1m=2step2Fori=1TonFillColor=QBColor(0)FillStyle=0x(i)=Cos(2*PI*(i-1)/n)*500y(i)=Sin(2*PI*(i-1)/n)*500Circle(x(i),y(i)),7,QBColor(0)NextiEndSubSubstep2()nc=stack(m)m=m-1Ifnc<>0Thenstep3Elsek=k-1Ifk<>0Thenstep2Elseindex=FalseEndIfEndIfEndSubSubstep3()A(k)=stack
4、(m)stack(m)=nc-1Ifk5、Text)Then'输入边的信息c=MsgBox("顶点必须为数字,请从新输入",0)Text1.Text=""Text2.Text=""ExitSubElsei=Int(Text1.Text)j=Int(Text2.Text)EndIfIfi<1Ori>nOrj<1Orj>nThen'判断顶点合法c=MsgBox("顶点有误,请从新输入",0)Text1.Text=""Text2.Text=""EndIfForh=0TonIf(i=ep(1,h)Andj=ep(2,h))Or(j=ep(1,h)Andi=ep(2,h))Thenc=MsgBox("该边已经添加,请输入下一条边:",0)
6、Text1.Text=""Text2.Text=""EndIfNexthIfc=0Then'画边s=s+1ep(1,s)=iep(2,s)=jpm(i,j)=1pm(j,i)=1Line(x(i),y(i))-(x(j),y(j)),QBColor(0)Text1.Text=""Text2.Text=""EndIfEndSubPrivateSubCommand2_Click()q=0index=Truek=1'A(1)=1stack(1)=1stack(2)=1m=2Whileindexstep2Ifindex=TrueThenq=q+1Fori=1Tonst(q,i)=A(i)Next
7、iEndIfWendCommand1.Enabled=FalseCommand3.Enabled=FalseLabel3.Caption="共有"&q&"个适当着色"Command4.Visible=TrueCommand5.Visible=TrueIfn-1>0ThenCommand4.Enabled=TrueEndIfh=0EndSubPrivateSubCommand3_Click()Clsc=0IfNotIsNumeric(