¶ Đường đi - Chu trình Euler
Nguồn: Eulerian path - Wikipedia và một số nguồn khác
Biên soạn:
- Bùi Nguyễn Ngọc Thắng - Carnegie Mellon University in Qatar
Reviewer:
- Trần Quang Lộc - ITMO University
- Hoàng Xuân Nhật - VNUHCM-University of Science
- Nguyễn Nhật Minh Khôi - VNUHCM-University of Science
- Nguyễn Châu Khanh - VNU University of Engineering and Technology (VNU-UET)
- Hồ Ngọc Vĩnh Phát - VNUHCM-University of Science
Chuẩn bị bài tập và bộ test
- Nguyễn Hoàng Vũ - THPT chuyên Phan Bội Châu - Nghệ An
Bài viết sẽ giới thiệu cho độc giả về đường đi và chu trình Euler, một khái niệm cơ bản có ứng dụng rộng rãi trong lý thuyết đồ thị và lập trình thi đấu. Phạm vi bài viết bao gồm các định lý liên quan đến sự tồn tại của đường đi và chu trình Euler trong đồ thị và chứng minh, thuật toán tìm chu trình Euler và ứng dụng trong một số bài tập.
Khái niệm về đường đi và chu trình Euler lần đầu tiên được đề cập bởi Leonhard Euler năm 1736 khi nghiên cứu bài toán bảy cây cầu ở Konigsberg.
Thành phố Konigsberg thuộc Phổ (nay là Kaliningrad thuộc Nga), được chia làm 4 vùng bằng các nhánh sông Pregel. Các vùng này gồm 2 vùng bên bờ sông (B, C), đảo Kneiphof (A) và một miền nằm giữa hai nhánh sông Pregel (D). Vào thế kỷ XVIII, người ta đã xây 7 chiếc cầu nối những vùng này với nhau. Người dân ở đây tự hỏi: Liệu có cách nào xuất phát tại một địa điểm trong thành phố, đi qua 7 chiếc cầu, mỗi chiếc đúng 1 lần rồi quay trở về nơi xuất phát không?
Minh hoạ 7 cây cầu ở Konigsberg - Nguồn: Wikipedia
Một cách tổng quát hơn:
Cho một đồ thị với tập các đỉnh và cạnh. Liệu có thể chỉ ra một đường đi hay chu trình đi qua tất cả các cạnh mỗi cạnh đúng một lần?
¶ Kí hiệu
Những kí hiệu sau sẽ được dùng xuyên suốt bài viết:
- Với đỉnh thuộc một đồ thị vô hướng thì là bậc của .
- Với đỉnh thuộc một đồ thị có hướng thì là bán bậc ra của và là bán bậc vào của .
¶ Định nghĩa
- Đường đi Euler (Eulerian path/trail) trên một đồ thị (bất kể là vô hướng hay có hướng, đơn hay đa đồ thị) là đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần.
- Chu trình Euler (Eulerian cycle/circuit/tour) trên một đồ thị là đường đi Euler trên đồ thị đó thoả mãn điều kiện đường đi bắt đầu và kết thúc tại cùng một đỉnh. Hiển nhiên rằng chu trình Euler cũng là một đường đi Euler.
- Đồ thị có chu trình Euler gọi là đồ thị Euler (Eulerian graph). Đồ thị chỉ có đường đi nhưng không có chu trình Euler được gọi là đồ thị nửa Euler (semi-Eulerian graph).
¶ Chu trình Euler trên đồ thị có hướng
¶ Định lý 1
Một đồ thị có hướng là đồ thị Euler nếu và chỉ nếu:
- Với mọi đỉnh thuộc đồ thị,
- Tất cả đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông
¶ Ví dụ
Đồ thị 1 (hình dưới) là một đồ thị Euler.
Ta thấy rằng mọi đỉnh thuộc đồ thị đều có bán bậc ra bằng bán bậc vào: , .
Đồng thời, các đỉnh có bậc lớn hơn 0 là , , , và đều nằm cùng một thành phần liên thông.
Do đó ta kết luận đồ thị 1 là đồ thị Euler. Thật vậy, là một chu trình Euler trên đồ thị.
 |
|---|
| Đồ thị 1 |
Đồ thị 2 dưới có những đỉnh mà bán bậc vào khác bán bậc ra. Chẳng hạn, đỉnh có cạnh vào và cạnh ra, tức . Do đó ta kết luận đồ thị 2 không phải là đồ thị Euler.
 |
|---|
| Đồ thị 2 |
¶ Chứng minh
¶ Chiều thuận
Giả sử đồ thị có hướng tồn tại chu trình Euler.
- Vì chu trình Euler đi qua tất cả các cạnh nên cũng đi qua tất cả các đỉnh có bậc lớn hơn . Vì thế tất cả các đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông.
- Dễ thấy trong chu trình số lần ta đi vào một đỉnh bất kì bằng đúng số lần ta đi ra khỏi đỉnh đó nên với mỗi đỉnh , .
¶ Chiều đảo
Ta sẽ sử dụng phương pháp quy nạp để chứng minh.
Vì các đỉnh có bậc bằng không ảnh hưởng đến việc tồn tại chu trình Euler nên ta chỉ xét trường hợp đồ thị có hướng không tồn tại đỉnh có bậc là .
Nếu đồ thị có nhiều hơn một thành phần liên thông thì hiển nhiên đồ thị không tồn tại chu trình Euler.
Xét đồ thị có hướng chỉ có một thành phần liên thông và tất cả các đỉnh trong đồ thị có bậc lớn hơn .
Ta cần chứng minh nếu với mỗi đỉnh , thì tồn tại chu trình Euler.
Dễ thấy nếu chỉ có đỉnh thì định lý đúng.
¶ Bổ đề 1
Với mọi đỉnh , tồn tại một chu trình chứa .
¶ Chứng minh
Ta dựng một chu trình bắt đầu từ .
Bắt đầu từ ta chọn một cạnh ra từ đến chưa thăm bất kì để đi. Lặp lại thao tác này cho đến khi ta đến một đỉnh mà ta đã thăm hết tất cả cạnh ra của . Nếu thì luôn tìm được một cạnh ra chưa thăm để đi tiếp vì khi đi vào thì ta giảm đi , tức ban đầu . Do điều kiện mọi đỉnh thuộc đều có bán bậc vào bằng bán bậc ra nên , tức tồn tại cạnh ra chưa thăm. Suy ra . Như vậy ta đã chỉ ra được một chu trình chứa trong đồ thị.
Giả sử điều phải chứng minh đúng với mọi đồ thị con thoả điều kiện. Tức là ta tìm được một chu trình Euler trên mọi sao cho với mọi , .
Ta chọn một đỉnh bất kì . Áp dụng bổ đề 1, giả sử ta tìm được một chu trình chứa . Xoá tất cả các cạnh trên thuộc .
Nếu sau khi xoá không còn cạnh thì là một chu trình Euler.
Ngược lại, ta thu được một số thành phần liên thông . Do khi ta đi theo chu trình , mỗi khi ta đi vào một đỉnh, ta đi ra khỏi đỉnh ấy ngay bước tiếp theo nên với mọi (), .
Theo giả sử thì với mọi ta tìm được một chu trình Euler đi qua tất cả các cạnh thuộc . Nhận xét rằng mọi có ít nhất một đỉnh chung với do nếu và không có đỉnh chung nghĩa là không đi qua bất kì đỉnh nào trong , tức và không liên thông, trái với điều kiện đặt ra là mọi đỉnh thuộc liên thông (lưu ý điều kiện đúng là mọi đỉnh có bậc lớn hơn trong thuộc cùng một thành phần liên thông, nhưng do ở đây ta đang xét trường hợp liên thông yếu). Lần lượt nối các chu trình con vào , ta thu được một chu trình kết quả đi qua tất cả các cạnh trên .
Đồ thị ban đầu, dễ thấy tồn tại chu trình
Xoá các cạnh thuộc , ta nhận thấy có chu trình con là và
Nhận thấy giữa và có đỉnh chung . Nối chu trình lại ta thu được một chu trình mới lớn hơn: .
Tiếp tục, giữa và có đỉnh chung . Nối chu trình lại ta thu được một chu trình mới: . Ta đã đi qua tất cả các cạnh và tìm được chu trình Euler trong đồ thị.
¶ Đường đi Euler trên đồ thị có hướng
¶ Định lý 2
Đồ thị có hướng là đồ thị nửa Euler nếu và chỉ nếu đồ thị thoả một trong hai điều kiện sau:
- Tồn tại chu trình Euler
- Thoả tất cả các điều kiện sau:
- Tồn tại trong đồ thị đúng đỉnh và sao cho và
- Với mọi đỉnh khác và ,
- Tất cả các đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông
Đỉnh và đỉnh cũng chính là đỉnh xuất phát và kết thúc của đường đi Euler trong đồ thị.
¶ Ví dụ
Đồ thị 3 dưới đây là một đồ thị nửa Euler.
Đồ thị 3 có đỉnh có và và đỉnh có và .
Các đỉnh khác ngoài và đều có bán bậc ra bằng bán bậc vào: , , \ldots
Đồng thời các đỉnh có bậc lớn hơn là , , , , thuộc cùng một thành phần liên thông.
Do đó, ta kết luận tồn tại đường đi Euler trên đồ thị 3. Thật vậy, là một đường đi Euler trên đồ thị.
 |
|---|
| Đồ thị 3 |
Đồ thị 4 có hướng không tồn tại đường đi Euler do có các đỉnh có bậc ra khác bậc vào là , , , .
 |
|---|
| Đồ thị 4 |
¶ Chứng minh
¶ Chiều thuận
Giả sử tồn tại đường đi Euler bắt đầu từ và kết thúc tại trên đồ thị có hướng.
- Nếu , đồ thị có chu trình Euler. Dựa vào định lý 1, ta chứng minh được định lý đúng trong trường hợp này.
- Nếu , do đường đi Euler đi qua tất cả các cạnh nên nhận thấy:
- do đường đi xuất phát nhưng không kết thúc tại nên phải ít hơn cạnh
- do đường đi kết thúc nhưng không xuất phát tại nên phải nhiều hơn cạnh
- với mọi khác và
- Tất cả các đỉnh có bậc lớn hơn trong đồ thị thuộc cùng một thành phần liên thông
¶ Chiều đảo
Trong trường hợp đồ thị có hướng tồn tại chu trình Euler, hiển nhiên đồ thị tồn tại đường đi Euler.
Giả sử đồ thị có hướng thoả các điều kiện trong định lý 2. Thêm một cạnh nối từ đến vào đồ thị ( và là đỉnh duy nhất trong đồ thị không thoả điều kiện bán bậc vào bằng bán bậc ra). Khi này mọi đỉnh trong đồ thị đều có bán bậc vào bằng bán bậc ra nên đồ thị tồn tại chu trình Euler đi qua và :
Ta nhận thấy trên đồ thị lúc sau tồn tại một đường đi qua tất cả các cạnh khác bắt đầu từ và kết thúc ở .
Do đó đồ thị ban đầu tồn tại một đường đi Euler.
¶ Chu trình Euler trên đồ thị vô hướng
¶ Định lý 3
Đồ thị vô hướng là đồ thị Euler nếu và chỉ nếu:
- Bậc của mọi đỉnh là chẵn
- Tất cả các đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông
¶ Chứng minh
Cách chứng minh định lý cho đồ thị vô hướng khá tương tự như cho đồ thị có hướng.
¶ Chiều thuận
Giả sử đồ thị vô hướng tồn tại chu trình Euler.
- Vì chu trình Euler đi qua tất cả các cạnh nên dễ thấy tất cả các đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông.
- Vì chu trình Euler đi qua mỗi cạnh đúng một lần và với mỗi đỉnh, số lần ta đi vào bằng đúng số lần ta đi ra khỏi đỉnh ấy nên bậc của mỗi đỉnh là chẵn.
¶ Chiều đảo
Ta cũng sử dụng phương pháp quy nạp để chứng minh.
Dễ thấy định lý đúng khi đồ thị có một đỉnh.
Xét một đồ thị vô hướng có đỉnh thoả , . Tương tự như trên đồ thị có hướng, ta chứng minh được:
- Chọn một đỉnh bất kì thì luôn tìm được một chu trình chứa .
- Xoá các cạnh trên thuộc :
- Nếu sau khi xoá không còn cạnh thì chính là một chu trình Euler.
- Ngược lại, ta thu được một số thành phần liên thông .
- Do trên chu trình , mỗi khi ta đi vào một đỉnh ta lập tức đi ra khỏi đỉnh ấy nên sau khi xoá cạnh, bậc của mọi đỉnh vẫn chẵn.
- Với mỗi , do bậc của mọi đỉnh vẫn chẵn, tìm được chu trình Euler đi qua tất cả các cạnh (giả thiết quy nạp).
- Do tất cả các đỉnh có bậc lớn hơn trong thuộc cùng một thành phần liên thông nên mọi có đỉnh chung với . Lần lượt nối các chu trình nhỏ vào , ta thu được chu trình Euler của .
Đồ thị ban đầu, dễ thấy chu trình
Xoá các cạnh thuộc , ta dễ thấy một chu trình .
Nhận thấy và có đỉnh chung , nối và để tạo ra chu trình mới lớn hơn: . Ta đã đi qua tất cả các cạnh và tìm được chu trình Euler trong đồ thị.
¶ Đường đi Euler trên đồ thị vô hướng
¶ Định lý 4
Tồn tại đường đi Euler trên một đồ thị vô hướng nếu và chỉ nếu:
- Đồ thị có đúng hoặc đỉnh bậc lẻ
- Tất cả các đỉnh có bậc lớn hơn thuộc cũng một thành phần liên thông
¶ Chứng minh
¶ Chiều thuận
Giả sử đồ thị vô hướng tồn tại đường đi Euler xuất phát tại và kết thúc tại .
- Nếu , dựa vào định lý 3, đồ thị có chu trình Euler nên tất cả đỉnh trong đồ thị có bậc chẵn và mọi đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông.
- Nếu , do đường đi Euler đi qua tất cả các cạnh nên dễ thấy đồ thị có đúng 2 đỉnh bậc lẻ là và và các đỉnh có bậc lớn hơn thuộc cùng một thành phần liên thông.
¶ Chiều đảo
- Nếu tất cả các đỉnh trong đồ thị có bậc lớn hơn thuộc cùng một thành phần liên thông và không có đỉnh bậc lẻ thì tồn tại chu trình Euler.
- Nếu tất cả các đỉnh trong đồ thị có bậc lớn hơn thuộc cũng một thành phần liên thông và có đúng đỉnh lẻ, ta thêm một cạnh ảo giữa đỉnh lẻ. Khi này đồ thị tồn tại chu trình Euler. Xoá cạnh ảo khỏi chu trình Euler, ta thu được đường đi Euler của đồ thị.
¶ Thuật toán tìm chu trình - đường đi Euler
Qua phần chứng minh trên, ta có thể thấy nếu có thuật toán tìm chu trình Euler thì hoàn toàn có thể dễ dàng sử dụng để tìm đường đi Euler nên trong phần này chúng ta sẽ tập trung vào thuật toán tìm chu trình Euler.
Hai thuật toán tìm chu trình Euler được biết đến rộng rãi là thuật toán Fluery và thuật toán Hierholzer. Bài viết sẽ tập trung vào thuật toán Hierholzer do tính phổ biến và độ hiệu quả của thuật toán này so với thuật toán Fluery.
¶ Thuật toán Hierholzer cho đồ thị có hướng
Thuật toán Hierholzer tìm chu trình Euler dựa trên các bước đã nêu trong phần chứng minh định lý cho đồ thị có hướng.
Giả sử đồ thị thoả định lý 1. Các bước trong thuật toán cụ thể như sau:
- Trước khi bắt đầu thuật toán ta chọn một đỉnh bất kì có bậc lớn hơn trong đồ thị để bắt đầu. Ta xem là tham số cho thuật toán. Nếu đồ thị không có cạnh, hiển nhiên ta trả về chu trình rỗng.
- Từ đỉnh tham số, ta tìm một chu trình chứa . Các bước cụ thể để tìm như sau:
- Khởi tạo mảng kết quả là rỗng và xuất phát từ đỉnh .
- Từ đỉnh đang đứng, chọn một cạnh ra chưa thăm để đi. Đánh dấu cạnh vừa đi qua và cập nhật vào .
- Lặp lại bước (ii). Nếu không thể đi tiếp thì ta tìm được một chu trình và sang bước 2.
- Nếu ta đã đi qua tất cả cạnh, trả là kết quả. Nếu chưa đi qua tất cả các cạnh, các cạnh chưa thăm trong đồ thị tạo thành những thành phần liên thông yếu. Tìm một đỉnh trên đồ thị thuộc mà có cạnh ra chưa đi qua.
- Gọi đệ quy thủ tục tìm chu trình Euler với tham số là đỉnh . Sau khi hoàn thành ta thu được một chu trình Euler đi qua tất cả các cạnh trong đồ thị con chứa .
- Nối hai chu trình và tại đỉnh chung . Lặp lại bước 2.
¶ Cài đặt mẫu
Trong phần cài đặt mẫu, đồ thị có hướng được biểu diễn dưới dạng danh sách kề. Trong trường hợp đồ thị vô hướng, cài đặt tương tự nhưng khi đánh dấu cạnh đã thăm lưu ý đánh dấu cả hai chiều.
Ngoài ra cài đặt mẫu sử dụng cấu trúc danh sách liên kết đôi thông qua cấu trúc list trong thư viện chuẩn của C++ để biểu diễn chu trình . Việc sử dụng danh sách liên kết đôi giúp bước nối hai chu trình trở nên đơn giản hơn do ta chỉ cần thay đồi liên kết giữa các phần tử trong danh sách. Ngoài cách sử dụng danh sách liên kết đôi, một số cài đặt khác sử dụng hai ngăn xếp để nối hai chu trình. Độc giả có thể tham khảo cách cài đặt này ở các tài liệu khác.
// N - số đỉnh nhiều nhất
// M - số cạnh nhiều nhất
struct Edge {
int target, id;
Edge(int _target, int _id): target(_target), id(_id) {}
};
vector<Edge> adj[N]; // Danh sách kề lưu cạnh và chỉ số
bool used_edge[M]; // Mảng đánh dấu cạnh đã thăm
list<int> euler_walk(int u) {
// Sử dụng cấu trúc danh sách liên kết để lưu kết quả
list<int> ans;
// Xuất phát từ đỉnh u
ans.push_back(u);
while (!adj[u].empty()) {
// Chọn một cạnh bất kì chưa thăm
int v = adj[u].back().target;
int eid = adj[u].back().id;
// Xoá cạnh vừa đi qua khỏi đồ thị
// Lưu ý việc xoá cạnh có thể **ảnh hưởng** tới các
// thao tác trên đồ thị về sau do việc xoá cạnh sẽ
// **phá huỷ** hoàn toàn danh sách cạnh
// Nên sao lưu danh sách cạnh ra biến khác nếu cần dùng lại
adj[u].pop_back();
// Bỏ qua nếu cạnh đã thăm
if (used_edge[eid]) continue;
// Đánh dấu cạnh đã đi qua
used_edge[eid] = true;
// Di chuyển sang đỉnh mới
u = v;
// Thêm cạnh vào đường đi hiện tại
// Có nhiều cách lưu chu trình như lưu đỉnh, cạnh,
// chỉ số cạnh, ...
ans.push_back(u);
}
// Tìm cạnh chưa thăm từ một đỉnh trên chu trình hiện tại
// Bắt đầu từ đỉnh thứ hai trong chu trình do ta biết
// rằng đỉnh đầu tiên trong chu trình (u) đã không còn
// cạnh ra
for (auto it = ++ans.begin(); it != ans.end(); ++it) {
// Gọi đệ quy tiếp tục tìm chu trình mới
auto t = euler_walk(*it);
// Nối chu trình tìm được vào chu trình hiện tại
t.pop_back();
ans.splice(it, t);
}
return ans;
}
Độ phức tạp thời gian của cách cài đặt trên là do việc nối hai chu trình được thực hiện trong thời gian nếu chu trình được biểu diễn bằng danh sách liên kết. Nếu chúng ta biểu diễn chu trình bằng một số cấu trúc phổ biến khác như (chẳng hạn vector) thì độ phức tạp thời gian sẽ tăng lên do việc nối chu trình kém hiệu quả.
Độ phức tạp bộ nhớ là tuyến tính dựa vào số đỉnh và số cạnh.
¶ Ứng dụng
¶ CSES - Teleporters Path
¶ Tóm tắt đề
Tìm một đường đi Euler trên đồ thị có hướng đỉnh, cạnh. In IMPOSSIBLE nếu không thể tìm được.
¶ Lời giải
Như đã đề cập, để tìm đường đi Euler, ta thêm một cạnh ảo từ giữa đỉnh lẻ, tìm chu trình Euler, rồi xoá cạnh ảo đã thêm.
Một cách khác để tìm đường đi Euler là ta chỉ cần gọi thủ tục tìm chu trình Euler như trên với tham số là đỉnh . Kết quả nhận được là đường đi Euler trên đồ thị. Lý giải là khi gọi thủ tục tìm chu trình Euler trong trường hợp này, ở lần lặp đầu tiên, chúng ta sẽ tìm được một đường đi từ tới . Những cạnh chưa thăm còn lại trong đồ thị tạo thành những thành phần liên thông thoả điều kiện tồn tại chu trình Euler. Khi này thuật toán sẽ gọi đệ quy tìm chu trình Euler trên từng đồ thị con và nối các chu trình con lại để dựng đường đi cần tìm.
¶ Cài đặt
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2, M = 2e5 + 2;
struct Edge {
int target, id;
Edge(int _target, int _id): target(_target), id(_id) {}
};
int n, m, in_deg[N];
vector<Edge> adj[N];
bool used_edge[M];
list<int> euler_walk(int u); // Hàm euler_walk như cài đặt mẫu
bool check() {
if (adj[1].size() != in_deg[1] + 1 ||
adj[n].size() != in_deg[n] - 1)
return false;
for (int i = 2; i < n; ++i)
if (adj[i].size() != in_deg[i])
return false;
return true;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v, i);
++in_deg[v];
}
// Kiểm tra tồn tại đường đi Euler
if (!check()) {
cout << "IMPOSSIBLE";
return 0;
}
// Thêm cạnh ảo vào đồ thị
adj[n].emplace_back(1, m);
// Tìm chu trình Euler
list<int> ans = euler_walk(1);
// Kiểm tra xem đã đi qua hết tất cả cạnh chưa vì trong trường hợp đồ
// thị không liên thông ta không thể đi qua tất cả cạnh
if (ans.size() < m + 1)
cout << "IMPOSSIBLE";
else {
// Tìm cạnh ảo đã thêm
for (auto u1 = ans.begin(), u2 = ++ans.begin(); u2 != ans.end(); ++u1, ++u2)
if (*u1 == n && *u2 == 1) {
// In các cạnh trên chu trình nhưng bỏ qua cạnh ảo
for (auto i = u2; i != ans.end(); ++i)
cout << (*i) << " ";
for (auto i = ++ans.begin(); i != u2; ++i)
cout << (*i) << " ";
break;
}
}
return 0;
}
¶ VNOI Marathon 08 - Mê cung
¶ Tóm tắt đề
Cho đơn đồ thị vô hướng đỉnh, cạnh. Mỗi cạnh có trọng số là . Tìm một chu trình đi qua tất cả các cạnh của đồ thị, sao cho tại mỗi thời điểm, tổng trọng số các cạnh đi qua không âm.
¶ Lời giải
Nếu đồ thị không liên thông, có đỉnh bậc lẻ, hay tổng trọng số tất cả các cạnh âm thì hiển nhiên không thể tìm được chu trình thoả yêu cầu.
Tìm một chu trình Euler bất kì trên đồ thị . Lưu ý do là một chu trình nên đỉnh liền sau là .
Gọi là mảng tổng tiền tố của trọng số các cạnh trên . Như vậy,
Lưu ý chỉ đỉnh liền sau trong .
Ta biết rằng do như đã đề cập, nếu tổng trọng số các cạnh âm thì không tìm được chu trình thoả yêu cầu.
Gọi là đỉnh thuộc chu trình sao cho nhỏ nhất.
Nếu thì thoả yêu cầu.
Nếu thì do .
Như vậy với mọi thì hay tổng trọng số các cạnh giữa vị trí và trong không âm. Tương tự với mọi thì .
Nhận thấy khi này nếu ta dịch chu trình ban đầu sao cho là đỉnh xuất phát thì sẽ tìm được một chu trình thoả yêu cầu do:
- Với mọi , .
- Với mọi ,
¶ Cài đặt
#include <bits/stdc++.h>
using namespace std;
const int N = 202;
const int M = 40002;
struct Edge {
int target, id;
Edge(int _target, int _id): target(_target), id(_id) {}
};
int n, m, w[M], deg[N], edge_id[N][N], S[M];
vector<Edge> adj[N];
bool used_edge[M];
list<int> euler_walk(int u); // Hàm euler_walk như cài đặt mẫu
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v >> w[i];
// Thêm cạnh vào đồ thị
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
edge_id[u][v] = i;
edge_id[v][u] = i;
// Cập nhật bậc của đỉnh
++deg[u];
++deg[v];
}
// Nếu đồ thị có đỉnh bậc lẻ hiển nhiên không tồn tại đáp án
for (int i = 1; i <= n; ++i)
if (deg[i] % 2 != 0) {
cout << -1;
return 0;
}
// Tìm chu trình Euler
list<int> cycle = euler_walk(1);
int cycle_size = cycle.size();
// Nếu các đỉnh có bậc lớn hơn 0 trong đồ thị không nằm cùng một TPLT
// thì không tồn tại đáp án
if (cycle_size < m + 1) {
cout << -1;
return 0;
}
// Tạo mảng S như đã đề cập
fill(S, S + M, 0);
int u = *cycle.begin();
auto it = ++cycle.begin();
for (int i = 1; it != cycle.end(); ++i, ++it) {
int v = *it;
S[i] = S[i - 1] + w[edge_id[u][v]];
u = v;
}
// Tìm k sao cho S[k] -> min
int k = 0;
for (int i = 1; i < cycle_size; ++i)
if (S[i] < S[k]) k = i;
// Dịch chu trình sao cho bắt đầu ở u[k]
list<int> ans;
ans.clear();
it = cycle.begin();
for (int i = 0; i < k; ++i, ++it)
ans.push_back(*it);
ans.push_back(*it);
ans.insert(ans.begin(), it, (--cycle.end()));
for (int i : ans) cout << i << " ";
return 0;
}
¶ 10040 - Ouroboros Snake
¶ Tóm tắt đề
Số Ouroboros "bậc" là số nhị phân được định nghĩa như sau:
- Đặt bit nhị phân thành một vòng tròn. Nếu ta có thể thu được dãy nhị phân độ dài khác nhau thì số đó là số Ouroboros.
Hãy trả lời các truy vấn với hai tham số và . Với mỗi truy vấn, cho biết bit thứ (đánh số bắt đầu từ ) trong số Ouroboros độ dài nhỏ nhất theo thứ tự từ điển (, ).
¶ Lời giải
Bài toán này đề cập đến khái niệm về dãy de Bruijn. Độc giả có thể tìm hiểu kĩ hơn tại đây de Bruijn sequence - Wikipedia. Bài viết chỉ đề cập đến những ý cần biết để giải quyết bài toán.
Dãy de Bruijn bậc của một tập gồm phần tử là một dãy vòng tròn sao cho với mỗi dãy độ dài chỉ gồm các phần tử thuộc , xuất hiện đúng một lần trong dưới dạng một dãy con liên tiếp. Hiển nhiên có phần tử.
Đồ thị de Bruijn là một khái niệm liên quan mật thiết đến dãy de Bruijn. Đồ thị de Bruijn chiều của một tập có phần tử là đồ thị có đỉnh, mỗi đỉnh đại diện cho một dãy độ dài chỉ gồm các phần từ trong . Giữa hai đỉnh và có cạnh một chiều từ đến nếu hậu tố độ dài của trùng với tiền tố độ dài của .
Một tính chất quan trọng cần lưu ý là với cùng một tập , đồ thị de Bruijn chiều là đồ thị đường (line graph) của đồ thị de Bruijn chiều.
Đồ thị đường của một đồ thị vô hướng là đồ thị được xây dựng như sau:
- Với mỗi cạnh trong , tạo một đỉnh tương ứng trên
- Hai đỉnh bất kì trên được nối bởi một cạnh vô hướng nếu hai cạnh tương ứng với hai đỉnh đó có đỉnh chung trên
Nhận thấy rằng dãy de Bruijn chính là một chu trình Hamilton của đồ thị de Bruijn chiều và phần tử. Một hệ quả đáng lưu ý của các tính chất trên là do chu trình Hamilton của một đồ thị là chu trình Euler của đồ thị đường của , nên cũng chính là chu trình Euler của đồ thị de Bruijn chiều và phần tử.
Trong bài toán này, với mỗi giá trị , ta có thể tìm trước dãy de Bruijn thứ tự từ điển nhỏ nhất để có thể truy cứu lại với mỗi truy vấn. Ta tận dụng hệ quả nêu trên để tìm số Ouroboros bậc thứ tự từ điển nhỏ nhất. Trước tiên, ta dựng đồ thị de Bruijn chiều với phần tử và : biểu diễn các số nhị phân từ đến dưới dạng một đồ thị có đỉnh, đỉnh thể hiện số dưới dạng nhị phân. Giữa 2 đỉnh và của đồ thị có cạnh một chiều từ đến nếu và . Ta đặt trọng số của cạnh bằng với .
Như vậy ban đầu mỗi đỉnh trong đồ thị có cạnh ra - cạnh có trọng số là và cạnh có trọng số là - và cạnh vào cũng có trọng số là và . Do mỗi đỉnh trong đồ thị có bán bậc ra bằng bán bậc vào nên đồ thị vừa dựng là một đồ thị Euler. Khi này bài toán quy về tìm chu trình Euler có thứ tự từ điển nhỏ nhất trên đồ thị.
Ta dùng phương pháp tham lam để giải quyết yêu cầu tìm thứ tự từ điển nhỏ nhất:
- Khi tìm chu trình xuất phát từ một đỉnh, ta sẽ ưu tiên đi qua cạnh có trọng số là trước.
- Sau khi có một chu trình bắt đầu từ một đỉnh, các cạnh còn lại trong đồ thị tạo thành các thành phần liên thông. Theo thuật toán, khi này ta tìm một đỉnh trên chu trình hiện tại có cạnh chưa thăm và gọi đệ quy tiếp tục tìm chu trình bắt đầu từ đỉnh đó. Do mỗi đỉnh chỉ có cạnh nên khi này nếu đỉnh còn cạnh chưa thăm, cạnh đó chắc chắn có trọng số . Do ta cần thứ tự từ điển nhỏ nhất nên ta muốn đặt các cạnh trọng số càng về cuối chu trình càng tốt. Vì thế ta sẽ duyệt chu trình hiện tại từ cuối về đầu, và gọi đệ quy thủ tục nếu có đỉnh có cạnh chưa thăm.
Với mỗi bậc , độ phức tạp thời gian sẽ là . Như vậy độ phức tạp thời gian để tiền xử lí cho toàn bộ bậc sẽ là khoảng phép tính, đủ trong giới hạn cho phép.
¶ Cài đặt
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int target, weight;
Edge(int _target, int _weight): target(_target), weight(_weight) {}
};
vector<vector<Edge>> build_graph(int n) {
vector<vector<Edge>> g(1 << n);
for (int u = 0; u < (1 << n); ++u) {
// Lưu ý thêm cạnh có trọng số 1 trước để ưu tiên sử dụng cạnh
// có trọng số 0 khi tìm chu trình
g[u].emplace_back(((u << 1) + 1) & ((1 << n) - 1), 1);
g[u].emplace_back((u << 1) & ((1 << n) - 1), 0);
}
return g;
}
list<Edge> euler_walk(int u, vector<vector<Edge>> &g) {
list<Edge> ans;
while (!g[u].empty()) {
int v = g[u].back().target;
ans.push_back(g[u].back());
g[u].pop_back();
u = v;
}
// Duyệt chu trình hiện tại từ cuối về đầu và
// gọi đệ quy nếu cần thiết
auto it = --ans.end();
while (it != ans.begin())
{
auto tit = it;
--tit;
ans.splice(it, euler_walk(tit->target, g));
it = tit;
}
return ans;
}
const int N = 23;
vector<int> ans[N];
int main() {
int test;
cin >> test;
while (test--) {
int n, k;
cin >> n >> k;
if (ans[n].empty()) {
// Dựng đồ thị de Bruijn n - 1 chiều
vector<vector<Edge>> g = build_graph(n - 1);
// Tìm chu trình Euler trên đồ thị vừa dựng
list<Edge> seq = euler_walk(0, g);
// Sinh dãy de Bruijn n chiều từ chu trình Euler tìm được
int cur = 0;
ans[n].clear();
for (auto it = seq.begin(); it != seq.end(); ++it) {
cur = ((cur << 1) + it->weight) & max((1 << n) - 1, 1);
ans[n].push_back(cur);
}
}
cout << ans[n][k] << "\n";
}
return 0;
}
¶ Vietnam TST 2017 - Problem 2 - Day 2
¶ Tóm tắt đề
Có đoạn thẳng song song với trục tọa độ trên mặt phẳng. Mỗi đoạn được biểu diễn bởi hai điểm (, ). In ra cách vẽ sao cho có thể tô màu tất cả các đoạn thẳng và số lần phải nhấc bút là ít nhất.
¶ Lời giải
Ta xem mỗi điểm trên mặt phẳng như một cạnh trên đồ thị vô hướng. Thêm đỉnh ảo vào đồ thị. Với mỗi đỉnh bậc lẻ trong đồ thị ban đầu, nối đỉnh đó với đỉnh ảo vừa thêm. Khi này đồ thị ta đang có gồm nhiều thành phần liên thông, mỗi thành phân liên thông là một đồ thị Euler. Tìm chu trình Euler trên tửng thành phần liên thông rồi xoá đỉnh ảo và các cạnh ảo đã thêm khỏi chu trình tìm được, ta thu được cách vẽ sao cho số lần nhấc bút là ít nhất.
¶ Cài đặt mẫu
#include <bits/stdc++.h>
using namespace std;
const int N = 1002;
struct Point {
int x, y;
Point(int _x, int _y): x(_x), y(_y) {}
};
struct Edge {
Point source, target;
int id;
bool fake;
Edge(int x, int y, int u, int v, int _id, bool _fake = false):
source(x, y),
target(u, v),
id(_id),
fake(_fake) {}
};
struct Graph {
int edges;
vector<vector<vector<Edge>>> graph;
Graph() {
edges = 0;
graph.clear();
graph.resize(N * 2);
for (int i = 0; i < N * 2; ++i)
graph[i].resize(N * 2);
}
vector<vector<Edge>>& operator[](int i) {
return graph[i];
}
void addEdge(int x, int y, int u, int v, bool fake = false) {
graph[x][y].emplace_back(x, y, u, v, edges, fake);
graph[u][v].emplace_back(u, v, x, y, edges, fake);
++edges;
}
void addFakeEdges() {
for (int i = 0; i < N * 2; ++i)
for (int j = 0; j < N * 2; ++j) {
if (graph[i][j].size() % 2 != 0) {
// Nối đỉnh bậc lẻ với đỉnh ảo
addEdge(i, j, 0, 0, true);
}
}
}
void addLine(int x1, int y1, int x2, int y2) {
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
if (x1 == x2) { // nếu đoạn thẳng song song với trục Oy
for (int i = y1; i < y2; ++i) {
addEdge(N + x1, N + i, N + x2, N + i + 1);
}
} else { // nếu đoạn thẳng song song với trục Ox
for (int i = x1; i < x2; ++i) {
addEdge(N + i, N + y1, N + i + 1, N + y2);
}
}
}
};
int n; // Số đoạn thẳng trong đề
vector<bool> avail;
Graph g = Graph();
vector<vector<Point>> ans;
ostream& operator<<(ostream& out, Point p) {
out << (p.x - N) << " " << (p.y - N);
return out;
}
// Hàm euler_walk như trên
list<Edge> euler_walk(Point u, Graph &g) {
list<Edge> ans;
while (!g[u.x][u.y].empty()) {
Edge e = g[u.x][u.y].back();
g[u.x][u.y].pop_back();
if (!avail[e.id]) continue;
avail[e.id] = false;
ans.emplace_back(e);
u = e.target;
}
auto it = --ans.end();
while (it != ans.begin())
{
list<Edge>::iterator tit = it;
--tit;
ans.splice(it, euler_walk(it->source, g));
it = tit;
}
return ans;
}
int main() {
// Khởi tạo mảng đánh dấu cạnh đã đi qua hay chưa
avail.clear();
// Đọc đầu vào
cin >> n;
for (int i = 0; i < n; ++i) {
int x, y, u, v;
cin >> x >> y >> u >> v;
g.addLine(x, y, u, v);
}
// Thêm cạnh ảo vào đồ thị
g.addFakeEdges();
avail.assign(g.edges, true);
ans.clear();
// Duyệt qua tất cả các TPLT trong đồ thị
for (int i = 0; i < N * 2; ++i) {
for (int j = 0; j < N * 2; ++j) {
if (!g[i][j].empty()) {
// Tìm chu trình Euler trên TPLT đang xét
list<Edge> cycle = euler_walk(Point(i, j), g);
// Chia chu trình tìm được thành các nét vẽ
// riêng biệt dựa vào các cạnh ảo
vector<Point> stroke;
stroke.clear();
for (list<Edge>::iterator it = cycle.begin(); it != cycle.end(); ++it) {
if (it->fake) {
if (!stroke.empty()) {
ans.push_back(stroke);
stroke.clear();
}
} else {
if (stroke.empty()) {
stroke.push_back(it->source);
}
stroke.push_back(it->target);
}
}
if (!stroke.empty()) ans.push_back(stroke);
}
}
}
cout << ans.size() << "\n";
for (vector<Point> v : ans) {
cout << v.size() << "\n";
for (Point i : v) cout << i << "\n";
}
return 0;
}