十、求图的所有适当着色.doc

求图的所有适当着色(1) 功能设G是n个顶点的一个图，并设Lam是给定的一个正整数。现在给每个顶点指定一种颜色ai(1=ai=Lam，I=1，2，n)，且G中的每条边e的两个端点都被指为不同的颜色。于是向量（a1，a2，an）就表示图G是用Lam种颜色的一种适当着色。(2) 调用方式先输入顶点个数（39），点“确定”后将出现顶点图示，然后输入颜色数量，再将每条有向边按起始点、终点输入。每输入一条边起、终点后，按“输入”确认，就可在图形中显示该边。当所有边输入完毕后，按“完成”键，将计算所有的适当着色。然后点击下方的“下一个”或“上一个”按钮将在图上用有色点表示出每一组适当着色。(3) 算法说明利用回溯算法一步一步的构造适当着色，并且在每一步都进行测试，看看局部构造的向量是否有可能扩充为一个适当着色，若不能就立即删除它并转到下一步。(4) 程序清单Dim ans As StringDim PI As DoubleDim stack(37), ep(3, 37), st(999, 10), pm(10, 10), om(10, 10), A(11), z1(10), x(10), y(10), d(11) As IntegerDim b, h, nc, i, j, c, e, k, m, n, p, q, s As IntegerDim linei, Lam As IntegerDim index, col(11) As BooleanSub step1() index = True k = 1 stack(1) = 1 stack(2) = 1 m = 2 step2 For i = 1 To n FillColor = QBColor(0) FillStyle = 0 x(i) = Cos(2 * PI * (i - 1) / n) * 500 y(i) = Sin(2 * PI * (i - 1) / n) * 500 Circle (x(i), y(i), 7, QBColor(0) Next i End SubSub step2() nc = stack(m) m = m - 1 If nc 0 Then step3 Else k = k - 1 If k 0 Then step2 Else index = False End If End If End SubSub step3() A(k) = stack(m) stack(m) = nc - 1 If k n Then k = k + 1 step4 End If End SubSub step4() b = 0 For j = 1 To Lam col(j) = True Next j For i = 1 To k - 1 If pm(i, k) = 1 Then col(A(i) = False End If Next i For i = 1 To Lam If col(i) = True Then m = m + 1 stack(m) = i b = b + 1 End If Next i m = m + 1 stack(m) = b step2 End SubPrivate Sub Command1_Click() c = 0 If Not IsNumeric(Text1.Text) Or Not IsNumeric(Text2.Text) Then 输入边的信息 c = MsgBox(顶点必须为数字，请从新输入, 0) Text1.Text = Text2.Text = Exit Sub Else i = Int(Text1.Text) j = Int(Text2.Text) End If If i n Or j n Then 判断顶点合法 c = MsgBox(顶点有误，请从新输入, 0) Text1.Text = Text2.Text = End If For h = 0 To n If (i = ep(1, h) And j = ep(2, h) Or (j = ep(1, h) And i = ep(2, h) Then c = MsgBox(该边已经添加，请输入下一条边：, 0) Text1.Text = Text2.Text = End If Next h If c = 0 Then 画边 s = s + 1 ep(1, s) = i ep(2, s) = j pm(i, j) = 1 pm(j, i) = 1 Line (x(i), y(i)-(x(j), y(j), QBColor(0) Text1.Text = Text2.Text = End IfEnd SubPrivate Sub Command2_Click() q = 0 index = True k = 1 A(1) = 1 stack(1) = 1 stack(2) = 1 m = 2 While index step2 If index = True Then q = q + 1 For i = 1 To n st(q, i) = A(i) Next i End If Wend Command1.Enabled = False Command3.Enabled = False Label3.Caption = 共有 & q & 个适当着色 Command4.Visible = True Command5.Visible = True If n - 1 0 Then Command4.Enabled = True End If h = 0End SubPrivate Sub Command3_Click() Cls c = 0 If Not IsNumeric(Text3.Text) Then 输入顶点个数 c = MsgBox(请输入3-9的整数, 0) Text1.Text = Else n = Int(Text3.Text) If n 9 Then c = MsgBox(顶点个数有误，请从新输入, 0) Text3.Text = End If End If If c = 0 Then 依据顶点个数画图 Dim ra As Integer ScaleTop = -1100 ScaleLeft = -700 ScaleHeight = 2000 ScaleWidth = 2500 For i = 1 To n FillColor = QBColor(0) FillStyle = 0 x(i) = Cos(2 * PI * (i - 1) / n) * 500 y(i) = Sin(2 * PI * (i - 1) / n) * 500 Circle (x(i), y(i), 7, QBColor(0) CurrentX = x(i) * 1.2 CurrentY = y(i) * 1.2 Print i Next i Command7.Enabled = True End If End SubPrivate Sub Command4_Click() h = h + 1 Timer1.Enabled = False If h 1 Then Command5.Enabled = True End If For i = 1 To n FillColor = QBColor(st(h, i) FillStyle = 0 x(i) = Cos(2 * PI * (i - 1) / n) * 500 y(i) = Sin(2 * PI * (i - 1) / n) * 500 Circle (x(i), y(i), 20, QBColor(st(h, i) Next i Timer1.Enabled = True Label3.Caption = 现在是第 & h & / & q & 个适当着色 If h = q Then Command4.Enabled = False End IfEnd SubPrivate Sub Command5_Click() h = h - 1 Timer1.Enabled = False If h q Then Command4.Enabled = True End If For i = 1 To n FillColor = QBColor(st(h, i) FillStyle = 0 x(i) = Cos(2 * PI * (i - 1) / n) * 500 y(i) = Sin(2 * PI * (i - 1) / n) * 500 Circle (x(i), y(i), 20, QBColor(st(h, i) Next i Timer1.Enabled = True Label3.Caption = 现在是第 & h & / & q & 个适当着色 If h = 1 Then Command5.Enabled = False End IfEnd SubPrivate Sub Command7_Click() If Not IsNumeric(Text4.Text) Then 输入顶点个数 c = MsgBox(请输入1-9的整数, 0) Text4.Text = Else b = Int(Text4.Text) If b 9 Then c = MsgBox(颜色数量有误，请从新输入, 0) Text4.Text = End If End If If c = 0 Then Lam = b End If Command1.Enabled = True Command2.Enabled = True Command3.Enabled = False End SubPrivate Sub F