Lý thuyết đồ thị - Tô màu
Tô màu đồ thị không có gì khác ngoài một cách đơn giản để gắn nhãn các thành phần đồ thị như đỉnh, cạnh và vùng theo một số ràng buộc. Trong một đồ thị, không có hai đỉnh liền kề, các cạnh liền kề hoặc các vùng liền kề được tô màu với số lượng màu tối thiểu. Số này được gọi làchromatic number và đồ thị được gọi là properly colored graph.
Trong khi tô màu đồ thị, các ràng buộc được thiết lập trên đồ thị là màu sắc, thứ tự tô màu, cách gán màu, v.v. Màu được đưa ra cho một đỉnh hoặc một vùng cụ thể. Do đó, các đỉnh hoặc vùng có cùng màu tạo thành các tập hợp độc lập.
Màu Vertex
Tô màu đỉnh là phép gán màu cho các đỉnh của đồ thị 'G' sao cho không có hai đỉnh liền kề nào có cùng màu. Nói một cách đơn giản, không có hai đỉnh của một cạnh nào có cùng màu.
Số màu
Số màu tối thiểu cần thiết để tô màu đỉnh của đồ thị 'G' được gọi là số màu của G, ký hiệu là X (G).
χ (G) = 1 nếu và chỉ khi 'G' là một đồ thị rỗng. Nếu 'G' không phải là đồ thị rỗng thì χ (G) ≥ 2.
Example
Note - Một đồ thị 'G' được cho là có thể xác định được n nếu có một màu đỉnh sử dụng nhiều nhất n màu, tức là X (G) ≤ n.
Màu vùng
Màu vùng là phép gán màu cho các vùng của đồ thị phẳng sao cho không có hai vùng liền kề nào có cùng màu. Hai vùng được cho là liền kề nếu chúng có cạnh chung.
Example
Hãy xem biểu đồ sau. Các vùng 'aeb' và 'befc' nằm liền kề nhau, vì có một cạnh chung 'be' giữa hai vùng đó.
Tương tự, các vùng khác cũng được tô màu dựa trên vùng kề cận. Biểu đồ này được tô màu như sau:
Example
Số sắc độ của Kn là
- n
- n–1
- [n/2]
- [n/2]
Hãy xem xét ví dụ này với K 4 .
Trong đồ thị hoàn chỉnh, mỗi đỉnh kề với (n - 1) đỉnh còn lại. Do đó, mỗi đỉnh yêu cầu một màu mới. Do đó số màu của K n = n.
Các ứng dụng của tô màu đồ thị
Tô màu đồ thị là một trong những khái niệm quan trọng nhất trong lý thuyết đồ thị. Nó được sử dụng trong nhiều ứng dụng thời gian thực của khoa học máy tính như -
- Clustering
- Khai thác dữ liệu
- Chụp ảnh
- Phân đoạn hình ảnh
- Networking
- Phân bổ nguồn lực
- Lập lịch xử lý