Chu trình Hamilton

Xem 1-20 trên 47 kết quả Chu trình Hamilton
  • Chu trình Hamilton Năm 1857 W. R. Hamilton, nhà toán học người Ailen đã đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số 20 đỉnh của một khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các thành phố, mỗi thành phố đúng một lần. Bài toán này đã dẫn tới những khái niệm sau đây.

    pdf6p yeuthuong 01-12-2010 279 79   Download

  • Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị, mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế, chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở. Chu trình Euler Khái niệm chu trình Euler được ra đời từ bài toán nổi tiếng sau đây. Ví dụ 7.1 (Bài toán 7 cây cầu ở Konigsberg): Thành phố Konigsberg thuộc nước Cộng hoà Litva có con sông Pregel chảy qua,...

    pdf5p yeuthuong 01-12-2010 394 75   Download

  • Chương 2 trình bày nội dung đường đi và chu trình Euler, đường đi và chu trình Hamilton. Chương này giúp người học dùng lý thuyết đồ thị để chứng minh 2 chu trình trên. Mời các bạn tham khảo tài liệu để nắm bắt nội dung chi tiết.

    pdf10p xaydungk23 19-04-2016 18 4   Download

  • Luận án nghiên cứu bài toán xác định sự tồn tại của chu trình Hamilton trong đồ thị trên các lớp đồ thị, đánh giá độ phức tạp thời gian đa thức để xác định chu trình Hamilton trong một lớp đồ thị đã khảo sát, đánh giá tính hiệu quả và khả thi của các thuật toán bằng chương trình thực nghiệm trên các đồ thị lớn, đánh giá độ dài của chu trình dài nhất trong lớp đồ thị. Mời các bạn cùng tham khảo.

    pdf27p lovivivi000 21-12-2016 9 2   Download

  • Giáo trình Lý thuyết đồ thị: Phần 1 giới thiệu định nghĩa và các tính chất cơ bản của đồ thị vô hướng và đồ thị có hướng; bài toán về chu trình Euler và chu trình Hamilton; khảo sát sơ lược về đồ thị phẳng; khảo sát tổng quan về cây S các vấn đề liên quan đặc biệt là cây nhị phân; bài toán con đường ngắn nhất và giải thuật Dijstra và giải thuật Floyd.

    pdf98p thuytrang_4 06-05-2015 103 48   Download

  • Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị, mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế, chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở. 7.1. Chu trình Euler Khái niệm chu trình Euler được ra đời từ bài toán nổi tiếng sau đây.

    pdf5p yeuthuong 26-03-2011 136 29   Download

  • Chu trình euler và chu trình hamilton Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị, mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế, chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở.

    pdf0p meogiay 15-11-2011 63 13   Download

  • Cây và một số ứng dụng Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồ thị vô hướng. Đó là khái niệm cây. 11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa 11.1: Giả sử T = (V, E) là đồ thị vô hướng. Ta nói rằng đồ thị T là một cây nếu nó liên thông và không có chu trình. Ví dụ 11.2: Đồ thị dưới đây là một cây.

    pdf0p meogiay 15-11-2011 43 6   Download

  • Trong bài báo này, ta chứng tỏ rằng bao đóng của một đồ thị G cho trước được xác định duy nhất, không phụ thuộc vào quá trình nối các cặp đỉnh có tổng bậc không nhỏ hơn n. Ta cũng đưa ra thuật toán xác định chu trình Hamilton trong đồ thị ban đầu nếu biết trước một chu trình Hamilton trong đồ thị cl(G).

    pdf14p uocvong07 14-10-2015 11 2   Download

  • Chương 5 trình bày những kiến thức liên quan đến đường đi trên đồ thị. Các nội dung chính trong chương gồm có: Đường đi và chu trình Euler, đường đi và chu trình Hamilton, bài toán đường đi tốt nhất.

    pdf11p youcanletgo_02 04-01-2016 8 2   Download

  • Given a undirected and simple graph with n vertices, we denote by σ2 the minimum of degree sum of the pair of nonadjacent vertices in G and by σ∗2 the minimum of degree sum of the pair of nonadjacent vertices with distance 2.

    pdf8p binhminhmuatrenngondoithonggio 09-06-2017 1 1   Download

  • Giáo trình Lý thuyết đồ thị được biên soạn nhằm đáp ứng nhu cầu tham khảo sách bằng tiếng Việt của các bạn về lý thuyết đồ thị. Đây là giáo trình Toán dành cho sinh viên chuyên ngành Tin học, do đó hầu hết các vấn đề được trình bày bằng ngôn ngữ giải thuật, mặc dù vậy phần chứng minh vẫn chặt chẽ và rõ ràng. Mời các bạn tham khảo phần 2 sau đây để nắm bắt nội dung chi tiết.

     

    pdf66p thuytrang_4 06-05-2015 62 28   Download

  • Năm 1857 W. R. Hamilton, nhà toán học người Ailen đã đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số 20 đỉnh của một khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các thành phố, mỗi thành phố đúng một lần. Bài toán này đã dẫn tới những khái niệm sau đây. Định nghĩa 7.5: Đường Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần. ...

    pdf6p yeuthuong 26-03-2011 100 11   Download

  • Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 16', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

    pdf0p meogiay 15-11-2011 66 10   Download

  • Bài toán đường đi ngắn nhất Trước mỗi chuyến xuất hành, chúng ta thường phải suy nghĩ và chọn ra cho mình một hành trình “tiết kiệm” nhất theo nghĩa tốn ít thời gian, tốn ít nhiên liệu hoặc tốn ít tiền nhất … Lý thuyết Đồ thị sẽ giúp chúng ta tìm ra giải pháp đó. 8.1. Bài toán Đường đi ngắn nhất

    pdf0p meogiay 15-11-2011 50 8   Download

  • Chu số và sắc số của đồ thị 4.1. Chu số của đồ thị Cho đồ thị G = (V, E) có n đỉnh, m cạnh, p thành phần liên thông. Định nghĩa 4.1: Đại lượng: c = m - n + p được gọi là chu số của đồ thị G. Trước hết, ta xét các tính chất của đại lượng này. Ví dụ

    pdf0p meogiay 15-11-2011 49 6   Download

  • Cặp ghép và đồ thị hai phần 5.1. Tập đỉnh tựa và cặp ghép Để đưa vào các khái niệm mới này, chúng ta xét bài toán phân công nhiệm vụ như sau: Một cơ quan có n nhân viên x1, x2, …, xn và m nhiệm vụ y1, y2, …, ym. Do quá trình đào tạo, mỗi nhân viên có thể đảm nhiệm một hay nhiều nhiệm vụ và mỗi nhiệm vụ có một số nhân viên có thể đảm nhiệm được.

    pdf0p meogiay 15-11-2011 47 6   Download

  • Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 13', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

    pdf0p meogiay 15-11-2011 42 6   Download

  • Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 2', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

    pdf0p meogiay 15-11-2011 37 5   Download

  • Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 19', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

    pdf0p meogiay 15-11-2011 47 5   Download

Đồng bộ tài khoản