Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Cấu trúc cây trong đồ thị vô hướng

    D
    dream dream Đang Ngoại tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Cấu trúc cây trong đồ thị vô hướng

    Luận văn thạc sĩ năm 2011
    Đề tài: Cấu trúc cây trong đồ thị vô hướng

    Mục lục
    Lời cảm ơn 3
    Mở đầu 4
    1 Một số khái niệm cơ bản về đồ thị 6
    1.1 Các định nghĩa . 6
    1.2 Một số đơn đồ thị đặc biệt . 7
    1.2.1 Đồ thị đầy đủ . 7
    1.2.2 Đồ thị vòng . 8
    1.2.3 Đồ thị bánh xe . 8
    1.2.4 Đồ thị hai phần 9
    1.2.5 Đồ thị phân đôi đầy đủ 9
    1.3 Các đồ thị mới từ đồ thị cũ 10
    1.4 Tính liên thông trong đồ thị vô hướng . 10
    2 Cấu trúc cây 12
    2.1 Định nghĩa cây . 12
    2.2 Các tính chất của cây . 12
    3 Cây bao trùm của đồ thị đầy đủ 15
    3.1 Cây bao trùm . 15
    3.2 Cây bao trùm của đồ thị đầy đủ 16
    4 Một số thuật toán xây dựng cây bao trùm của đồ thị vô
    hướng liên thông 22
    4.1 Thuật toán tìm kiếm ưu tiên chiều sâu . '22
    Thuật toán tìm kiếm ưu tiên chiều rộng 25
    Kết luận
    Tài liệu tham khảo

    Mở đầu
    Lí thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỉ XVIII bởi nhà toán học Thụy sĩ tên là Leonhard Euler. Ỏng đã dùng đồ thị để giải quyết bài toán cầu Kônigsberg nổi tiếng.
    Lí thuyết đồ thị được ứng dụng rất nhiều trong thực tế. Rất nhiều bài toán thuộc nhiều ứng dụng khác nhau được giải bằng mô hình đồ thị.
    Một loại đồ thị đặc biệt được gọi là cây. Khái niệm cây đã được dùng từ năm 1857. khi nhà toán học Anh, Arthur Cayley dùng cây để xác định những dạng khác nhau của hợp chất hóa học. Từ đó cây đã được dùng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau.
    Luận văn trình bày một số khái niệm cơ bản về đồ thị, cây và một số tính chất của cây. trình bày công thức tính số cây bao trùm của đồ thị đầy đủ n đỉnh được đánh nhãn và một số thuật toán tìm cây bao trùm của đồ thị.
    Ngoài phần mở đầu, phần kết luận, luận văn gồm 4 chương.
    Chương 1 Một số khái niệm cơ bản về đồ thị
    Chương này trình bày một số khái niệm cơ bản về đồ thị và các ví dụ minh họa.
    Chương 2 cấu trúc cây
    Chương này trình bày định nghĩa cây và các tính chất của cây.
    Chương 3 Cây bao trùm của đồ thị đầy đủ
    Chương này trình bày về cây bao trùm của đồ thị, cây bao trùm của đồ thị đầy đủ, công thức tính số cây bao trùm của đồ thị đầy đủ, thuật toán mã hóa Priifer và thuật toán giải mã Priifer.
    Chương 4 Một số thuật toán xây dựng cây bao trùm của đồ thị vô hướng liên thông
    Chương này trình bày về hai thuật toán tìm cây bao trùm của đồ thị: Thuật toán tìm kiếm ưu tiên chiều sâu và thuật toán tìm kiếm ưu tiên chiều rộng.

    Chương 1
    Một số khái niệm cơ bản về đồ thị
    Ta hiểu Dồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Người ta phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. Trong chương này chúng tôi chỉ đưa ra các khái niệm về đồ thị vô hướng và các ví dụ minh họa.
    Chương này gồm bốn mục: Trong mục 1.1. chúng tôi trình bày một số định nghĩa về đồ thị vô hướng. Mục 1.2 trình bày một số đơn đồ thị đặc biệt. Mục 1.3 trình bày về các đồ thị mới từ đồ thị cũ. Mục 1.4 trình bày về tính liên thông trong đồ thị vô hướng. Các kiến thức trong chương này được tham khảo từ chương 8 trong sách [1],
    1.1 Các định nghĩa
    Định nghĩa 1.1. Một đơn đồ thị G = (V. E) gồm một tập không rỗng V là tập các đỉnh và một tập E là tập các cạnh, đó là các cặp không sắp thứ tự của các đỉnh phân biệt.

    Tài liệu tham khảo
    [1] Bang Ye Wu, Kun-Mao Chao, Spanning Trees and Optimization Problems, (2004), Chapman k Hall/CRC Press, USA
    [2] Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937.
    [3] Kenneth H. Rosen, Discrete mathematics and its applications, Fifth edition, dịch bởi Phạm Văn Thiều và Đặng Hữu Thịnh "Toán học rời rạc ứng dụng trong Tin học", NXB Giáo dục, 1997

    Xem Thêm: Cấu trúc cây trong đồ thị vô hướng
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Cấu trúc cây trong đồ thị vô hướng sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status