Trong bài viết hôm nay chúng ta đi tìm hiểu cách tô màu đồ thị và trước khi vào bài học ngày hôm nay thì mình sẽ tổng kết lại một số kiến thức nền tảng về đồ thị cho bạn.
- Độ thị phân loại là 2 loại: Đồ thị có hướng G = [V, E], đồ thị vô hướng G = (V, E).
- Đồ thị kí hiệu là G = (V,E)
- Trong đó G là đồ thì G, V là đỉnh (Vertex) và E là cạnh hay cung (Edge).
- Về đồ thị có hướng thì sẽ có các mũi tên đánh hướng đi trên đô thị và chỉ đi một chiều. Vô hướng thì không có đánh mũi tên và đi hai chiều.
- Đồ thị vô hướng hay có hướng đều có đỉnh và cạnh (cung). Người ta gọi đồ thị có hướng là cung và vô hướng là cạnh.
- Hai đỉnh của cạnh E được gọi là hai đầu mút.
- Nếu cạch hai đầu mà cùng một đỉnh là gọi là khuyên.
- Bậc của đỉnh được bằng số đỉnh kề với đỉnh đó. Ký hiệu là deg(V)
- deg(V) = deg–(V) + deg+(V), trong đó deg–(V) là số bậc vào, deg+(V) là số bậc ra.
- Đỉnh một bậc gọi là đỉnh treo
- Đỉnh 0 bậc gọi là đỉnh cô lập
Cách làm bài tập tô màu đồ thị có code
Các bạn làm theo các bước dưới đây:
Trước hết chúng ta phải hiểu bài toán tô màu đồ thị là gì? => Bài toán tô màu đồ thị là bài toán mà các đỉnh sẽ được tô màu mà sao cho hai đỉnh kề nhau không cùng một màu và số màu sử dụng là ít nhất.
Số màu ít nhất được sử dụng được gọi là sắc số.
Ta áp dụng bài toán này cho việc sắp xếp lịch thi – phòng thi, tô màu bản đồ,…
Bước 1: Là tạo một ma trận quan hệ với các đỉnh và cạnh. Ma trận quan hệ là ma trận có đường chéo từ trái qua phải là 0 hay ∞. Mặt trên và mặt dưới là giống nhau.
Trong đó các đỉnh là đối tượng được cho, cạch là đường nói giữa hai đỉnh mà 2 đỉnh này không tô màu giống nhau.
Ví dụ: Đỉnh là 8 đài phát thanh A, B, C, D, E, F, G, H. Cạnh là đường dây nối giữa 2 đài khoảng cách >= 100km (hai đài kề nhau không được tô màu giống nhau)
Có quan hệ ta đánh số là 1 và không quan hệ là 0.
| A | B | C | D | E | F | G | H | BẬC | |
| A | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
| B | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | |
| C | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
| D | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |
| E | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | |
| F | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | |
| G | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
| H | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
Bước 2: Tính bậc của các đỉnh.
| A | B | C | D | E | F | G | H | BẬC | |
| A | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 4 |
| B | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 4 |
| C | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 2 |
| D | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 3 |
| E | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 6 |
| F | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 5 |
| G | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 4 |
| H | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 4 |
Bước 3: Viết ra các đỉnh và số bậc của định (bậc của đỉnh nằm bên dưới).
Ví dụ:
| A | B | C | D | E | F | G | H | |
| 4 | 4 | 2 | 3 | 6 | 5 | 4 | 4 |
Bước 4: Hạ bậc của đỉnh có bậc cao nhất về 0 và đánh số màu là (1) ở trên đỉnh đó (lưu ý số 1 ta khoanh tròn để biết đỉnh này đã tô màu gì). Số màu là 1 rồi tăng dần.
Bước 5: Kiểm tra và điền các đỉnh quan hệ với đỉnh có bậc cao nhất và đánh dấu là 1. Những đỉnh này nhận số 1 nghĩa là ta cấm dùng màu số 1 cho các đỉnh quan hệ với định có bậc cao nhất.
Bước 6: Hệ bậc xuống 1 đơn vị của các đỉnh quan hệ với đỉnh bậc cao nhất.
Bước 7: Ghi lại số bậc của các đỉnh còn lại.
Bước 8: Lặp lại bước 4 đến khi tất cả các đỉnh được tô màu. Các đỉnh đã tô màu thì ta cũng không cần đụng chạm tới nó nữa.
Bước 9: Ta lập kết quả ra được số màu được sử dụng là bao nhiêu và mỗi màu đó thì có thể tô bao nhiêu đỉnh. Ví dụ: Số màu sử dụng cho đồ thị này là 4, màu 1 = D,E, màu 2 = B, C, F, màu 3 = A, G, màu 4 = H.
Trên đây là các mà bạn tìm ra được số màu cần tô ít nhất trong đồ thị. Ngoài phương pháp hạ bậc và chọn bậc lớn nhất như cách trên thì chung ta còn phương pháp khác như thuật giải tham lam, tô màu nguyên lý Greedy.
Code thuật giải tô màu đồ thị – theo giải thuật tham lam.
| #include <stdio.h> #include <stdlib.h> #define input “G:/code-c/dothi.txt” #define SIZE 50 void docDoThi(int A[][SIZE], int &n); void toMau(int A[][SIZE],int n,int Mau[]); void xuat(int A[], int n); int main(){ int A[SIZE][SIZE], n; int Mau[SIZE]; docDoThi(A,n); for(int i =0; i<n; i++){ for(int j=0; j<n;j++){printf(“%d “, A[i][j]); } printf(“\n”); } printf(“\nGiai thuat tham lam:”); printf(“\nA B C D E F G H I\n”); toMau(A,n,Mau); xuat(Mau,n); return 1; } |
| void docDoThi(int A[][SIZE], int &n){ FILE *fi = fopen(input,”rt”); if(fi == NULL){ printf(“Khong mo duoc file!”); exit(0); } fscanf(fi,”%d”,&n); for(int i =0; i<n; i++){ for(int j=0; j<n;j++){fscanf(fi,”%d”, &A[i][j]); } }fclose(fi); } |
| void toMau(int A[][SIZE],int n,int Mau[]){ int BangMau[SIZE][SIZE] = {0}; int mauvuato; for(int i=0; i<n; i++){ for(int k = 0; k <n; k++) if(BangMau[i][k] == 0){ Mau[i] = k; mauvuato = k; break; } for(int j=i+1; j<n; j++){ if(A[i][j] > 0) BangMau[j][mauvuato] = 1; } } } void xuat(int A[], int n){ for(int i=0;i<n;i++){ printf(“%d “,A[i] + 1); } } |
Chúng các bạn thành công!