Thạc Sĩ 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