Tô màu đồ thị

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Đồ thị Petersen có sắc số bằng 3.

Trong Lý thuyết đồ thị, tô màu đồ thị (tiếng Anh: graph coloring) là trường hợp đặc biệt của gán nhãn đồ thị, mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị có thể là:

  • tô màu đỉnh (tiếng Anh: vertex coloring) là gán cho mỗi đỉnh của đồ thị một màu nào đó sao cho không có hai đỉnh nào liền kề lại trùng màu nhau;
  • tô màu cạnh (tiếng Anh: edge coloring) là gán cho mỗi cạnh của đồ thị một màu nào đó sao cho sao cho không có 2 cạnh nào trùng màu;
  • tô màu miền (tiếng Anh: face coloring) là gán cho mỗi miền của đồ thị phẳng một màu sao cho không có 2 miền có chung đường biên lại cùng màu.

Sắc số (tiếng Anh: chromatic number) của một đồ thị là số màu ít nhất để tô các đỉnh. Sắc số của đồ thị G được kí hiệu là χ(G).

Số màu cạnh (tiếng Anh: chromatic index) của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị G được kí hiệu là χ'(G).

Số màu cạnh của đồ thị G bất kì bằng sắc số của đồ thị đường L((G)) của đồ thị đó:

χ'(G) = χ(L(G)),

do đó việc nghiên cứu tô màu cạnh của G tương đương với nghiên cứu tô màu đỉnh của L(G).

Mục lục

Các định lí và tính chất [sửa]

Các giá trị giới hạn của sắc số [sửa]

Rõ ràng sắc số của một đồ thị sẽ không vượt quá số đỉnh của nó (bậc của đồ thị):

1 \le \chi(G) \le n.\,.

Nếu G có clique kích thước k thì cần ít nhất k màu để tô màu đỉnh cho clique này (xem thêm bài về đồ thị đầy đủ), như vậy sắc số của một đồ thị sẽ không nhỏ hơn chỉ số clique của đồ thị đó:

\chi(G) \ge \omega(G).\,

Nếu đồ thị đơn G có bậc cực đại bằng Δ(G) thì sắc số của nó không vượt quá Δ(G)+1[1].

Chứng minh 

Tổng quát hơn là định lý Brook, định lý khẳng định rằng:

Tất cả mọi đồ thị đơn và liên thông G, ngoại trừ đồ thị đầy đủ K_n và đồ thị chu trình bậc lẻ W_n, đều có sắc số nhỏ hơn hoặc bằng bậc cực đại:
\chi (G) \le Δ(G).

Nếu đồ thị G có m cạnh thì sắc số của nó thỏa mãn:

\chi(G)(\chi(G)-1) \le 2m.\,
Chứng minh 

Một số định lý liên quan của sắc số [sửa]

Định lý 1 [sửa]

Bất cứ chu trình độ dài lẻ nào cũng đều có sắc số bằng 3

Chứng minh: Giả sử chu trình có độ dài là 2n +1 ta chứng minh theo số n

  • n=1 chu trình gồm 3 đỉnh mà 2 đỉnh bất kì đều kề nhau \Rightarrow dùng đúng 3 màu để tô
  • (n) \Rightarrow (n+1) Giả sử \alpha là một chu trình có độ dài 2(n+1)+1=2n+3 với các dãy đỉnh là x_1, x_2,...,x_{2n+1},x_{2n+2},x_{2n+3}.

Nối x_1 với x_{2n+1} ta được một chu trình \alpha'có độ dài 2n+1.

Theo giả thuyết quy nạp chu trình \alpha' có sắc số bằng 3.

Lấy màu của x_1 tô cho x_{2n+2} còn màu của x_{2n+1} tô cho x_{2n+3}.

Chu trình \alpha được tô màu mà không thêm màu mới vào.

Vậy chu trình \alpha có sắc số bằng 3

Định lý 2 [sửa]

Đồ thị đầy đủ n đỉnh Kn có sắc số bằng n

Một số tiêu chuẩn đơn giản để kiểm tra xem 1 đồ thị có hai sắc số hay không:

  • Ta có định lý: Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G có hai sắc số khi và chỉ khi G không có chu trình đơn vô hướng độ dài lẻ.

Chứng minh:

  • Giả sử G là đồ thị có hai sắc số. Theo Định lý 1 thì G không thể có chu trình đơn vô hướng độ dài lẻ.
  • Ngược lại giả sử G không có chu trình đơn vô hướng độ dài lẻ. Không mất tính tổng quát có thể xem G liên thông.

Chọn 1 đỉnh a nào đó bất kì trong đồ thị

Đặt m(a)= 0 (m: số màu)

Với x \ne a Ta ký hiệu d(x)là độ dài đường đi vô hướng ngắn nhất nối a vớix

Đặt m(x)= d(x) mod 2

Ta sẽ chứng minh m là hàm màu của G

Giả sử x, y kề nhau

Lấy d(x) là đường đi vô hướng ngắn nhất nối a với x có độ dài d(x)
d(y) là đường đi vô hướng ngắn nhất nối a với y có độ dài d(y)

Chu trình đơn [d(x),(x,y),d(y)] có độ dài d(x)+d(y)+1 phải là một số chẵn

Vậy thì d(x)+d(y) là một số lẻ \Rightarrow d(x), d(y) khác nhau tính chẵn lẻ

\Rightarrow m(x) \ne m(y)

Hàm tô màu m có hai giá trị, vậy sắc số ≤ 2. G có ít nhất một cạnh nên sắc số của nó bằng 2

Từ định lý trên ta có hệ quả sau: Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.

Các giá trị giới hạn của số màu cạnh [sửa]

Định lí 1 [sửa]

Số màu cạnh của đồ thị đơn G bất kì không vượt quá số đỉnh của nó.
Chứng minh 

Định lý König khẳng định rằng đối với đồ thị hai phía G, số màu cạnh của nó bằng bậc cực đại của nó: \chi'(G) = \Delta(G).

Định lý Vizing khẳng định rằng, nếu đồ thị đơn G có bậc cực đại bằng \Delta(G) thì số màu cạnh của nó bằng \Delta(G) hoặc \Delta(G)+1.

Đa thức màu [sửa]

Xem bài đa thức màu.

Sắc số và số màu cạnh của một số đồ thị cơ bản [sửa]

Khái niệm sắc số liên quan đến bài toán tô màu như sau: Hãy tô màu các đỉnh của đồ thị đã cho, sao cho 2 đỉnh kề phải được tô bằng hai màu khác nhau


Đồ thị hai phía [sửa]

  • Các đỉnh của đồ thị K_{3,3} được tô bằng hai màu xanh và đỏ.

Đồ thị hai phía đầy đủ K_{m,n} có sắc số bằng 2: χ(K_{3,3})=2. Mở rộng: một đồ thị hai phía bất kì có sắc số không vượt quá 2.

Ví dụ minh họa là các đỉnh của đồ thị K_{3,3} có thể được tô bởi hai màu xanh và đỏ.

Đồ thị chu trình [sửa]

  • Các đỉnh của đồ thị C_5 tô được bởi ít nhất 3 màu.

  • Các đỉnh của đồ thị C_6 tô được bởi ít nhất 2 màu.

  • Các cạnh của đồ thị C_5 tô được bởi ít nhất 3 màu.

  • Các cạnh của đồ thị C_6 tô được bởi ít nhất 2 màu.

Đồ thị chu trình C_n có sắc số bằng:

  • χ(C_n)= 3, nếu n lẻ.
  • χ(C_n)= 2, nếu n chẵn.

Số màu cạnh:

  • χ'(C_n)= 3, nếu n lẻ.
  • χ'(C_n)= 2, nếu n chẵn.

Đồ thị bánh xe [sửa]

  • Các đỉnh của đồ thị W_6 tô được bởi ít nhất 4 màu.

  • Các đỉnh của đồ thị W_7 tô được bởi ít nhất 3 màu.

  • Các cạnh của đồ thị W_7 tô được bởi ít nhất 6 màu.

Đồ thị bánh xe W_n (n≥4) có sắc số bằng:

  • χ(W_n)= 4, nếu n chẵn;
  • χ(W_n)= 3, nếu n lẻ.

Số màu cạnh (n≥3):

  • χ'(W_n)= n-1.

Đồ thị đầy đủ [sửa]

  • Đồ thị đầy đủ 7 đỉnh có sắc số bằng 7.

  • K_5 có số màu cạnh bằng 5.

  • K_4 có số màu cạnh bằng 3.

Đồ thị đầy đủ K_n có sắc số bằng:

  • χ(K_n) = n.

Số màu cạnh:

  • χ'(K_n) = n, nếu n lẻ.
  • χ'(K_n) = n-1, nếu n chẵn.
Chứng minh 

Đồ thị siêu khối [sửa]

  • Sắc số của Q_2 bằng 2.

  • Sắc số của Q_3 bằng 2.

Đồ thị siêu khối Q_n có sắc số bằng 2, vì bản thân nó là đồ thị phân đôi.

Ứng dụng [sửa]

Tô màu bản đồ [sửa]

Trên các bản đồ, các miền khác nhau (miền ở đây được hiểu là các quốc gia trên bản đồ thế giới hay các tỉnh trong một bản đồ hành chính quốc gia) được tô màu sao cho 2 miền có chung biên giới không trùng màu nhau. Đối với bản đồ có nhiều miền, nếu ta dùng một số lượng lớn màu thì sẽ rất khó phân biệt các miền có màu gần giống nhau, vì thế người ta chỉ dùng một số lượng màu nhất định để tô màu bản đồ. Một bài toán được đặt ra là: có thể dùng ít nhất bao nhiêu màu để tô màu một bản đồ sao cho các miền kề nhau không cùng một màu[2] (tr.593).

Bài toán này dẫn đến định lý bốn màu nổi tiếng và định lý năm màu[3] .

Bài toán áp dụng vào thực tế: Tô màu bản đồ nước Mỹ [sửa]
bản đồ 14 tiểu bang (tiêu biểu) nước Mỹ

Đề bài:

Tô màu bản đồ nước mỹ gồm 14 tiểu bang (tiêu biểu) sao cho hai tiểu bang giáp ranh không cùng chung một màu và sao cho số màu sử dụng là ít nhất. Xem hình

ma trận kề bản đồ 14 tiểu bang (tiêu biểu) nước Mỹ

Bài làm:

Bước 1: Lập ma trận kề

Quy ước:

  • Đỉnh: là các tiểu bang

Đỉnh 1 - California

Đỉnh 2 - Nevada

Đỉnh 3 - Alizona

Đỉnh 4 - Utah

Đỉnh 5 - Colorado

Đỉnh 6 - Nebraska

Đỉnh 7 - Kasas

Đỉnh 8 - Oklahoma

Đỉnh 9 - Texas

Đỉnh 10 - Arkansas

Đỉnh 11 - Louisiana

Đỉnh 12 - Mississippi

Đỉnh 13 - Alaboma

Đỉnh 14 - Florida

  • Cạnh: thể hiện mối quan hệ giữa hai tiểu bang

Giá trị 0: hai đỉnh không có đường nối trực tiếp

Giá trị 1: hai đỉnh có đường nối trực tiếp

  • Màu: màu
  • Ma trận kề (xem hình)
bảng tính bậc từng đỉnh dựa theo ma trận kề bản đồ nước Mỹ

Bước 2: Tính bậc của từng đỉnh

(xem hình)

bảng tô màu theo nguyên lý greedy dựa vào ma trận kề bản đồ nước Mỹ

Bước 3: Tô màu theo nguyên lý Greedy

(xem hình)

Bước 4: Kết luận

14 tiểu bang nước Mỹ tô ít nhất 3 màu

  • Màu 1: California, Utah, Nebraka, Olklahoma, Louisiana, Florida
  • Màu 2: Nevada, Colorado, Texas, Alabama
  • Màu 3: Aiona, Kansas, Arkansas

Một số thuật toán tô màu và code mẫu [sửa]

Thuật toán tô màu FF [sửa]

Thuật toán FF (First Fit) là thuật toán tô màu các đỉnh theo thứ tự đơn giản nhất.

Tư tưởng của thuật toán [sửa]

Lần lượt tô màu cho các đỉnh theo thứ tự của đỉnh, với mỗi đỉnh x, ta tô cho màu x có số thứ tự nhỏ nhất còn hợp lý (chưa tô màu x cho bất kỳ đỉnh nào kề x).

Code mẫu [sửa]

Ngôn ngữ lập trình C
#include <stdio.h>
 #include <stdio.h>
 #include <conio.h>
 #include <stdlib.h>
 int *doc_tep(int *a,int *n);
 void in_matran(int *a,int n);
 int ktra_mau(int *a,int *b,int *c,int n,int x);
 void ToMau(int *a,int n);
 void main()
{

  int n,*a;
  a=doc_tep(a,&n);
  in_matran(a,n);
  ToMau(a,n);
  getch();

}
int *doc_tep(int *a,int *n)
{

  FILE *f;
  f=fopen("Graph2.INP","r");
  if(f==NULL)
  {
    printf("nLoi Mo Tep.");
    getch();
    exit(1);
  }
  fscanf(f,"%d",n);
  a=(int *) malloc(*n**n*sizeof(int));
  for(int i=0;i<*n;i++)
     for(int j=0;j<*n;j++)
        fscanf(f,"%d",(a+i**n+j));
  fclose(f);
  return a;

}
void in_matran(int *a,int n) {

  for(int i=0;i<n;i++)
  {
     for(int j=0;j<n;j++)
        printf("%5d",*(a+i*n+j));
     printf("nn");
  }

}
int ktra_mau(int *a,int *b,int *c,int n,int d,int x) //Dinh d,mau x {

  for(int j=0;j<n;j++)
  if(*(a+d*n+j)!=0 && j!=d && *(b+j)==x)
     return 0;
  return 1;

}
void ToMau(int *a,int n) {

  int *b,*c;
  b=(int *) calloc (n,sizeof(int));
  c=(int *) calloc (n,sizeof(int));
  *b=0;            //To mau 0 cho dinh 1.
  *c=1;            //Danh dau dinh 1 da to mau.
  for(int i=1; i<n;i++)
     for(int j=0; j<n;j++)
        if(ktra_mau(a,b,c,n,i,j)==1)
        {
           *(b+i)=j;
           *(c+i)=1;
           break;
        }
  printf("nTo Mau Cho Do Thi: n");
  for(int i=0; i<n;i++)
     printf("ntDinh %d ---> Mau %d",i+1,*(b+i));

}

Thuật toán tô màu Greedy [sửa]

Tư tưởng thuật toán [sửa]

Dùng màu thứ nhất tô cho một đỉnh tùy ý và các đỉnh khác có thể tô còn lại (không có cạnh nối nhau).
Sau đó dùng màu thứ hai tô tiếp cho các đỉnh có thể tô còn lại.
Và cứ như vậy…cho đến khi nào tô tất cả các đỉnh được tô màu hết.

Code mẫu [sửa]

Ngôn ngữ lập trình C
#include <stdio.h>
 #include <conio.h>
 #include <iostream.h>
 #include <stdlib.h>
 #include <dos.h>
 #define MAX 10
 //khai bao bien
char *path = "D:\\dothi1.txt";
 int n;
 int matrix[MAX][MAX];
 int level[MAX];
 int nocolor[MAX][MAX];
 int color[MAX];
 void ReadFile(char *path)
{

    FILE *f;f=fopen(path,"r");
    if(f==NULL){
       cout<<"Unsucsess!";
       exit(0);
    }
    else{
       cout<<"Loading file is success!";
       delay(800);
       clrscr();
    }
    fscanf(f,"%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
           fscanf(f,"%d",&matrix[i][j]);
    //** Set 0 cho nocolor.
    for(int x=0;x<n;x++)
        for(int y=0;y<n;y++)
            nocolor[x][y]=0;

}
void OutMat(int a[MAX][MAX])
{

   for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           cout<<a[i][j]<<" ";
       }
       cout<<"\n";
   }

}
void SetLevel(int a[MAX][MAX])
{

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]==1)
               level[i]++;
        }
    }

}
int EleMax(int l[MAX])
{

    int eMax = 0,max=l[0];
    for(int i=1;i<n;i++){
        if(l[i]>max){
          max=l[i];
          eMax=i;
       }
   }
   return eMax;

}
void ToMau(int a[MAX][MAX],int l[MAX],int nc[MAX][MAX])
{

   int col; 
   int index,tmp ;
   for(int x=0;x<10;x++){
       //* Xet khi level deu =0;
       tmp=0;
       for(int y=0;y<n;y++)
       tmp+=l[y];
      if(tmp!=0){
          index = EleMax(l);
         //* Kiem tra mau.
         col=1;
         for(int i=0; i<n;i++){
            if(nc[index][i]==col)
               col++;
         }
         //* SET mau
         color[index]=col;
         l[index]=0;
         //* Ha bac lien quan.
         for(int j=0;j<n;j++)
            if(a[index][j]==1 & l[j]!=0){
                l[j]--;
            }
         //* Cam cac mau ko dc xai.
        for(int h=0;h<n;h++)
            if(a[index][h]==1)
                nc[h][x]=col;
      }
       else{
           for(int z=0;z<n;z++)if(color[z]==0){
             col=1;
             for(int i=0; i<n;i++){
                 if(nc[z][i]==col)
                    col++;
             }
             color[z]=col;
          }
          break;
     }
  }

}
void main()
{

  ReadFile(path);
  SetLevel(matrix);
  OutMat(matrix);
  ToMau(matrix,level,nocolor) ;
  cout<<"\n";
  cout<<"Dinh:\t";
  for(int j=0;j<n;j++)
    cout<<j+1<<" ";
  cout<<"\n";
  cout<<"Mau:\t";
  for(int i=0;i<n;i++)
     cout<<color[i]<<" ";
  getch();

}

Xem thêm [sửa]

Chú thích [sửa]

  1. ^ Vũ Đình Hòa, Đồ thị, NXB Giáo dục
  2. ^ Kenneth H.Rosen, Toán học rời rạc, NXB Khoa Học và Kỹ thuật Hà Nội, 2003
  3. ^ Trần Đan Thư - Dương Anh Đức (2008). Lý Thuyết Đồ Thị. Nhà xuất bản Đại học Quốc Gia TP Hồ Chí Minh. 

Tham khảo [sửa]

  • Panconesi, A.; Srinivasan, A. (1996), “On the complexity of distributed network decomposition”, Journal of Algorithms 20 

Liên kết ngoài [sửa]

Lấy từ “http://vi.wikipedia.org/w/index.php?title=Tô_màu_đồ_thị&oldid=11460797”