---
# System prepended metadata

title: Lý thuyết đồ thị

---

# Lý thuyết đồ thị
Các bài từ 0 tới 4: đọc sách thầy LMH
https://csacademy.com/lessons

## Bài 5:
Nhận xét: quân mã đứng ở ô ở giữa không đi được.
Đánh số các vị trí còn lại từ 1 tới 8 như hình sau:
![](https://i.imgur.com/mZdDBjL.png)
Từ ô đánh số $i$, chỉ có thể đi tới 2 ô đánh số $i+1$ và $i-1$ (liền trước và liền sau). Đặc biệt, với ô 1 thì liền trước của nó là ô 8, với ô 8 thì liền sau của nó là ô 1.
Nói cách khác, các ô này tạo thành một chu trình.

Cùng một thời điểm không thể tồn tại 2 quân mã trên cùng một ô.
Như vậy, *vị trí tương đối của các quân mã* bắt buộc phải giữ nguyên.

Ví dụ: 
![](https://i.imgur.com/vQJvZel.png)
Lúc đầu, các quân cờ đứng ở các ô 1,3,4,6 có màu là WBBW. Sau đó, quân ở 6 di chuyển tới 8, quân ở 4 di chuyển tới 7, quân ở 3 di chuyển tới 5,
quân ở 1 di chuyển tới 2 nên có được như hình bên phải.
Vì đi trên vòng tròn nên vẫn có thể ra được hình sau:
![](https://i.imgur.com/p5cIbEX.png)
Các quân đứng ở vị trí 7,8,1,2, màu vẫn là WBBW
Tuy nhiên, sẽ không thể ra được hình sau:
![](https://i.imgur.com/Le6IahV.png)
Vì khi ta đọc theo thứ tự sẽ ra màu của các quân là WBWB, cho dù có đẩy theo vòng tròn bao nhiêu lần đi nữa thì cũng không đọc ra được WBBW như lúc đầu --> không tạo được

### Cài đặt:
- Đánh số các ô
- Kiểm tra ô ở giữa
- Lấy ra các màu theo thứ tự
- Xoay vòng tròn để ra được các cấu hình A' có thể có từ A
- So sánh xem thử bảng B có giống bảng A' không
- 