十、求图的所有适当着色

《十、求图的所有适当着色》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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-1Ifk

5、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(