问答题

【说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1～4分别表示4种颜色。要着色的N个区域用0～-1编号，区域相邻关系用adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域了相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color[i]的值为区域i，所着颜色。 【C程序】 #include ＜stdio.h＞ #define N 10 void output(int color[]) { /*输出一种着色方案*/ int i ; for ( i = 0 ; i ＜ N ; i++ ) printf( "%4d" , color[i] ) ; printf ("\n") ; } int back(int *ip ,int color[] ) { /*回溯*/ intc = 4 ; while ( c == 4 ) { if ( *ip ＜= 0 ) return 0 ; -- (*ip) ; c = (1) ; color[*ip] =-1 ; } return c ; } /*检查区域i，对c种颜色的可用性*/ int colorOk(int i , intc , int [] [N] ,int color[ ] ) { int j ; for (j = 0 ; j ＜ i ; j++ ) if ( (2) ) return 0 ; return 1 ; } /*为区域i选一种可着色的颜色*/ int select (int i ,int c ,int adj [] [N] ,int color[ ] ){ int k ; for(k = c ; k ＜= 4 ; k++ ) if( colorOK( (3) )) return k ; return 0 ; } int coloring(int adj [] [N]) { /*寻找各种着色方案*/ int color[N] , i , c , cnt ; for(i = 0 ; i ＜ N ; i++) color[i] =-1 ; i = c = 0 ; cnt = 0 ; while(1) { if((c = (4) ) == 0 { c = back( &i , color); if( c == 0 ) return cnt; } else { (5) ; i++ ; if i == N) { output(color); ++cnt ; c = back( &i , color ) ; } else c = 0 ; } } } void main()( int adj[N] [N] = { {0,1,0,1,1,1,1,1,1,1}, {1,0,1,1,0,1,1,1,1,0}, {0,1,0,1,0,1,1,0,1,1}, {1,1,1,0,1,1,0,0,1,1}, {1,0,0,1,0,1,0,0,0,0}, {1,1,1,1,1,0,1,0,0,1}, {1,1,1,0,0,1,0,0,1,0}, {1,1,0,0,0,0,0,0,1,1}, {1,1,1,1,0,0,1,1,0,1}, {1,0,1,1,0,1,0,1,1,0}, } ; printf("共有%d组解.\n",coloring(adj)); }