Trường THPT Trực Ninh B
Chào mừng bạn đã đến với Diễn đàn chính thức trường THPT Trực Ninh B. Nếu chưa có tài khoản, đăng ký ngay! Đã có tài khoản? Vui lòng đăng nhập để tham gia cộng đồng mạng lớn nhất của trường.
Trường THPT Trực Ninh B
Chào mừng bạn đã đến với Diễn đàn chính thức trường THPT Trực Ninh B. Nếu chưa có tài khoản, đăng ký ngay! Đã có tài khoản? Vui lòng đăng nhập để tham gia cộng đồng mạng lớn nhất của trường.
Trường THPT Trực Ninh B
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Trường THPT Trực Ninh B

Trực Thái, Trực Ninh, Nam Định
 
Trang ChínhTrang Chính  GalleryGallery  Tìm kiếmTìm kiếm  Latest imagesLatest images  Đăng kýĐăng ký  Đăng Nhập  
Tìm kiếm
 
 

Display results as :
 
Rechercher Advanced Search
Keywords
2012 2013 tiêu phồng division 2011
Latest topics
» Tìm bạn trong trường trực ninh B HELP
Bài toán người đưa thư EmptyThu Oct 16, 2014 11:38 pm by namanhson

» Hỏi thăm thầy cô giáo
Bài toán người đưa thư EmptySun Jun 29, 2014 10:33 pm by Nguyễn Thùy Liên

» Sống khỏe nhờ nghề công nghệ cao
Bài toán người đưa thư EmptyMon Jan 20, 2014 3:10 pm by ngocdiem

» Bí quyết chọn ngành nghề phù hợp
Bài toán người đưa thư EmptyMon Jan 20, 2014 3:06 pm by ngocdiem

» Sửa chữa Smartphone – nghề thời thượng
Bài toán người đưa thư EmptyWed Jan 08, 2014 3:27 pm by ngocdiem

» Teen thời @ ôn thi đại học như thế nào?
Bài toán người đưa thư EmptyTue Jan 07, 2014 5:03 pm by ngocdiem

» chân lí sống của thế kỉ 21
Bài toán người đưa thư EmptySun Nov 10, 2013 9:53 pm by Bưu chính Viễn thông

» Tuyệt hay - Phần mềm giúp bạn chơi Piano ............ trên máy tính!
Bài toán người đưa thư EmptySun Nov 10, 2013 9:47 pm by Bưu chính Viễn thông

» 4 bí quyết của thủ khoa Đại học
Bài toán người đưa thư EmptySun Nov 10, 2013 9:06 pm by Bưu chính Viễn thông

March 2024
MonTueWedThuFriSatSun
    123
45678910
11121314151617
18192021222324
25262728293031
CalendarCalendar
Thống Kê
Hiện có 1 người đang truy cập Diễn Đàn, gồm: 0 Thành viên, 0 Thành viên ẩn danh và 1 Khách viếng thăm

Không

Số người truy cập cùng lúc nhiều nhất là 12 người, vào ngày Wed Aug 14, 2013 6:51 pm

 

 Bài toán người đưa thư

Go down 
Tác giảThông điệp
Chocolate
Thành viên nhiệt tình
Thành viên nhiệt tình



Tổng số bài gửi : 156
Điểm : 5704
Danh vọng : 4
Ngày sinh : 02/10/1995
Ngày tham gia : 24/12/2011
Tuổi : 28
Đến từ : Tp. Trực Cường

Bài toán người đưa thư Empty
Bài gửiTiêu đề: Bài toán người đưa thư   Bài toán người đưa thư EmptyMon Mar 12, 2012 2:26 pm

Bước tới: menu, tìm kiếm

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 cho, vì nó được nhà toán học Trung Hoa Mei-Ku Guan nêu ra đầu tiên vào năm 1962[1].
Mục lục
[ẩn]

1 Cách giải
2 Các phiên bản khác của bài toán
3 Xem thêm
4 Chú thích
5 Tham khảo
6 Liên kết ngoài

[sửa] 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ác đỉnh đều có bậc chẵn) thì sẽ tồn tại hành trình là chu trình đơn.

Ta xét trường hợp đồ thị có một số đỉ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ý Gooodman-Hedetniemi (1973) [2].

Định lý Gooodman-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:

q+m(G),

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à 2k.

Gọi V_0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k đỉ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 P_i của V_0(G).

Với mỗi cặp đỉnh u, v trong một phân hoạch P_i của V_0(G), 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 d(P_i).

Số m(G) chính là số nhỏ nhất trong các tổng d(P_i).
Về Đầu Trang Go down
https://trucninhb.forumvi.com
 
Bài toán người đưa thư
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Bài toán người bán hàng
» Bài toán bảy cây cầu- Wikipedia
» [hot] bói toán cực sock
» Đề thi thử đại học môn Toán 2013
» Đề thi thử và đáp án đề thi tốt nghiệp môn Toán năm 2013

Permissions in this forum:Bạn không có quyền trả lời bài viết
Trường THPT Trực Ninh B :: Học hỏi :: Tin học-
Chuyển đến