TAILIEUCHUNG - Đồ thị - Graph

Tài liệu tham khảo cho các bạn sinh viên học chuyên ngành công nghệ thông tin có tư liệu ôn thi tốt đạt kết quả cao trong các kỳ thi giữa kỳ và cuối kỳ | thị - Graph Trình bày những kiến thức căn bản về lý thuyết đồ thị các cách biểu diễn một số thuật toán Chú trọng việc cài đặt tối ưu các thuật toán bằng cách sử dụng các cấu trúc dữ liệu đặc biệt Đánh giá thuật toán Spring 2004 Data Structure Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN 1 Nội dung trình bày Các ví dụ thực tế Các khái niệm và định nghĩa cơ bản Biểu diễn đồ thị Thuật toán sắp xếp Topology Thuật toán tìm đường đi ngắn nhất Spring 2004 Data Structure Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN 2 1 rị ì J1 J Ấ Các ví dụ thực tê Bản đồ đường đi giữa các thành phố Hệ thống đường bay giữa các sân bay Hệ thống lưới điện trong thành phố Hệ thống đường ống nước trong thành phố Sơ đồ đường xe điện xe buýt. Sơ đồ mạng máy tính . Spring 2004 Data Structure Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN 3 Các khái niệm và định nghĩa cơ bản Định nghĩa đồ thị G V E V Vertices tập các đỉnh. Số đỉnh N V E Edges tập các cạnh. Mỗi cạnh là 1 cặp u v với u v eV. Số cạnh M E Ví dụ V A B C D E F E C D C E C F D F E F Spring 2004 Data Structure Algorithm - Nguyen Tri T uan - Khoa CNTT ĐH KHTN T 4 2 Các khái niệm và định nghĩa cơ bản Đồ thị có hướng Directed graph thứ tự các đỉnh trong mỗi cạnh là quan trọng nghĩa là u v v u Đồ thị vô hướng Undirected graph thứ tự các đỉnh trong mỗi cạnh là không quan trọng nghĩa là u v v u Spring 2004 Data Structure Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN 5 Các khái niệm và định nghĩa cơ bản Đồ thị có hướng với V A B C D E F G E A B A E B C B F D E E F F C F G Spring 2004 Data Structure Algorithm - Nguyen Tri T uan - Khoa CNTT ĐH KHTN T 6

• Cơ sở dữ liệu
• biểu diễn đồ thị
• thuật toán sắp xếp
• thuật toán tìm đường đi ngắn nhất
• lý thuyết đồ thị
• tài liệu học đại học
• Bài giảng Lý thuyết đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Euler
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị
• thuật toán
• phương pháp biểu diễn
• cây khung