![](images/graphics/blank.gif)
BÀI 07: Sắc số của đồ thị
440
lượt xem 52
download
lượt xem 52
download
![](https://tailieu.vn/static/b2013az/templates/version1/default/images/down16x21.png)
Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau: Hãy tô màu các đỉnh của một đồ thị đã cho, sao cho hai đỉnh kề nhau phải được tô bằng hai màu khác nhau. Ta nói rằng, đồ thị G tô được bằng k màu nếu tồn tại hàm: m : V → {0, 1, 2, ... , k-1} sao cho, nếu hai đỉnh x và y kề nhau thì m(x) ≠ m(y). Dễ thấy rằng, đồ thị G tô màu được khi và chỉ khi nó không có đỉnh nút.
Chủ đề:
Bình luận(0) Đăng nhập để gửi bình luận!
![](images/graphics/blank.gif)
CÓ THỂ BẠN MUỐN DOWNLOAD