Xem mã nguồn của Bài toán người đưa thư Trung Hoa

'''Bài toán người đưa thư Trung Hoa''' ([[tiếng Anh]]: ''Chinese postman problem'') phát biểu rằng: 
:''Một người đưa thư xuất phát từ bưu điện phải đến một số con đường để phát thư rồi quay trở về điểm xuất phát, hỏi người đó phải đi như thế nào để số đường đi là ít nhất''.

Trong phần [[đồ thị]], '''bài toán người đưa thư Trung Hoa''' tương đương với bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của một đồ thị cho trước.

Tên gọi "bài toán người đưa thư Trung Hoa" được Alan Goldman của [[Cục Tiêu chuẩn quốc gia Hoa Kỳ]] (''U.S. National Bureau of Standards'') đặt, vì nó được nhà [[toán học]] Trung Hoa [[Guan Meigu|Quản Mai Cốc]] nêu ra đầu tiên vào năm 1962<ref>{{chú thích web | url=http://www.nist.gov/dads/HTML/chinesePostman.html | title="Chinese Postman Problem"}}</ref>.

== Cách giải ==

Bài toán giải bằng phương pháp đồ thị. Dựng một đồ thị có các cạnh tương ứng với các con đường mà người đưa thư phải đi qua. Một chu trình đi qua tất cả các cạnh gọi là một hành trình. Đỉnh xuất phát của chu trình này tương ứng với vị trí của bưu điện.

Nếu đồ thị là [[đồ thị Euler]] (có hai đỉnh bậc lẻ hoặc không có đỉnh bậc lẻ) thì sẽ tồn tại hành trình khép kín và chỉ đi qua mỗi cạnh một lần.

Ta xét trường hợp đồ thị có hơn hai đỉnh bậc lẻ. Như thế hành trình của người đưa thư sẽ đi qua một số cạnh hai lần. Trường hợp này được giải quyết bằng cách sử dụng định lý Goodman-Hedetniemi (1973) <ref>{{chú thích web | url = http://www.scribd.com/doc/16616577/Giao-Trinh-Toan-Roi-Rac-Chuong-4 | tiêu đề = Giao Trinh Toan Roi Rac | author = | ngày = | ngày truy cập = 9 tháng 2 năm 2015 | nơi xuất bản = | ngôn ngữ = }}</ref>{{Verify credibility|date=February 2014}}.

'''Định lý Goodman-Hedetniemi (1973)''': 
:''Nếu ''G'' là một đồ thị liên thông có ''q'' cạnh thì hành trình ngắn nhất trong ''G'' có chiều dài:''
:::<math>q+m(G)</math>,
:''trong đó m(G) là số cạnh mà hành trình đi qua 2 lần''.

''G'' có một số chẵn các đỉnh bậc lẻ, gọi số lượng này là 2''k''.

Gọi <math>V_0(G)</math> là tập hợp các đỉnh bậc lẻ (2''k'' đỉnh) của G. Ta phân 2''k'' đỉnh này thành ''k'' cặp, mỗi tập hợp ''k'' cặp này được gọi là một phân hoạch <math>P_i</math> của <math>V_0(G)</math>.

Với mỗi cặp đỉnh ''u'', ''v'' trong một phân hoạch <math>P_i</math> của <math>V_0(G)</math>, ta xét khoảng cách giữa 2 đỉnh đó (chính bằng độ dài [[đường đi]] ngắn nhất nhận ''u,v'' làm 2 đầu mút), ký hiệu là ''d(u,v)''. Tính khoảng cách của k cặp đỉnh, rồi cộng lại ta được tổng <math>d(P_i)</math>.

Số ''m(G)'' chính là số nhỏ nhất trong các tổng <math>d(P_i)</math>.

'''Ví dụ''':

[[Hình:Định lý Gooodman-Hedetniemi ví dụ minh họa.PNG|vừa|430px|phải|Đồ thị ''G'' gồm 6 đỉnh: ''a'', ''b'', ''c'', ''d'', ''e'', ''f'' với bậc tương ứng là 3,3,2,3,3,2 như trong hình vẽ.]]

[[Hình:Định lý Gooodman-Hedetniemi ví dụ minh họa bước 2a.PNG|vừa|430px|phải|Vẽ thêm hai cạnh phụ (''a'',''b'') và (''e'',''d'')]]

[[Hình:Định lý Gooodman-Hedetniemi ví dụ minh họa bước 2b.PNG|vừa|430px|phải|Vẽ thêm hai cạnh phụ (''a'',''e'') và (''b'',''d'')]]

:Cho đồ thị ''G'' gồm 6 đỉnh: ''a'', ''b'', ''c'', ''d'', ''e'', ''f'', với bậc tương ứng là 3,3,2,3,3,2 như trong hình vẽ.

:Ta sử dụng định lý Goodman-Hedetniemi để tìm hành trình ngắn nhất trong ''G''.

:Số cạnh của ''G'': <math>q=8</math>.

:Tập các đỉnh có bậc lẻ <math>V_0(G)</math>={''a'',''b'',''e'',''d''}. Có 3 cách phân hoạch tập <math>V_0(G)</math> thành 2 cặp:
:*<math>P_1</math>={(''a'',''b'')(''e'',''d'')}, với d(<math>P_1</math>)= d(''a'',''b'') + d(''e'',''d'')= 1+1 = 2;
:*<math>P_2</math>={(''a'',''d'')(''b'',''e'')}, với d(<math>P_2</math>)= d(''a'',''d'')+ d(''b'',''e'')= 2+2 = 4;
:*<math>P_3</math>={(a,e'')(''b'',''d'')}, với d(<math>P_3</math>)= d(''a'',''e'')+ d(''b'',''d'')= 1+1= 2.

:Như vậy, <math>m(G)=min</math>{2,4,2}=2, suy ra hành trình ngắn nhất trong ''G'' có độ dài:
::<math>q+m(G) = 8+2 = 10</math>.

:Có 2 hành trình như thế:
:* Ta vẽ thêm 2 cạnh phụ (''a'',''b'') và (''e'',''d'') vào đồ thị ''G''. Chu trình Euler trong đồ thị mới sẽ đồng thời là hành trình ngắn nhất trong đồ thị ''G'':
:::''f''→''a''→''b''→''c''→''d''→''e''→''a''→''b''→''d''→''e''→''f''.
:* Ta vẽ thêm 2 cạnh phụ (''a'',''e'') và (''b'',''d'') vào đồ thị ''G''. Chu trình Euler trong đồ thị mới sẽ đồng thời là hành trình ngắn nhất trong đồ thị ''G'':
:::''f''→''a''→''b''→''c''→''d''→''b''→''d''→''e''→''a''→''e''→''f''.

== Các phiên bản khác của bài toán ==
* Bài toán có thể được đặt ra với một đồ thị có hướng (thay vì vô hướng), các dữ kiện và yêu cầu khác không đổi. Khi đó bài toán được gọi là '''Bài toán người quét rác New York''' (tiếng Anh: ''New York Street Sweeper problem'').

==Xem thêm==

==Chú thích==
{{Tham khảo}}

==Thư mục==

==Liên kết ngoài==

[[Thể loại:Lý thuyết đồ thị]]
[[Thể loại:Lý thuyết đồ thị trong các bài toán tính toán]]
[[Thể loại:Bài toán NP-đủ]]