tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 3 - Tôn Quang Toại

Bài giảng Lý thuyết đồ thị: Chương 3 Tìm kiếm trên đồ thị, cung cấp cho người đọc những kiến thức như: Một số khái niệm; Thuật toán tìm kiếm theo chiều rộng; Thuật toán tìm kiếm theo chiều sâu. Mời các bạn cùng tham khảo! | CHƯƠNG 3 TÌM KIẾM TRÊN ĐỒ THỊ Tôn Quang Toại Khoa CNTT Đại học Ngoại ngữ Tin học Nội dung Một số khái niệm Thuật toán tìm kiếm theo chiều rộng Thuật toán tìm kiếm theo chiều sâu Ứng dụng Một số khái niệm Đường đi chu trình Tính liên thông 2 đỉnh liên thông Đồ thị vô hướng liên thông Đồ thị có hướng Liên thông mạnh Miền liên thông Đỉnh khớp cạnh cầu Một số khái niệm Đường đi Path Đường đi từ đỉnh x đến đỉnh y trong đồ thị G V E là một dãy các đỉnh liên tiếp nối đỉnh x đến đỉnh y trong đó Độ dài đường đi Là số cạnh của đường đi Đường đi đơn simple Là đường đi qua mỗi cạnh tối đa 1 lần. Một số khái niệm Chu trình Cycle Là đường đi có đỉnh đầu trùng với đỉnh cuối Chu trình đơn Mỗi cạnh xuất hiện tối đa 1 lần trong chu trình Một số khái niệm Hai đỉnh liên thông Hai đỉnh x y được gọi là liên thông với nhau nếu có đường đi từ x đến y. Đồ thị liên thông Đồ thị vô hướng G V E được gọi là đồ thị liên thông nếu thì x liên thông với y. Một số khái niệm Đồ thị liên thông mạnh Đồ thị có hướng G V A được gọi là đồ thị liên thông mạnh nếu thì x liên thông với y. Thành phần liên thông Là tập đỉnh liên thông với nhau và nếu bổ sung thêm 1 đỉnh khác thì không liên thông Một số khái niệm Cạnh cầu Cho đồ thị G V E . Cạnh gọi là cầu nếu xóa cạnh e thì số thành phần liên thông tăng lên Đỉnh khớp Cho đồ thị G V E . Đỉnh gọi là khớp nếu xóa các cạnh liên thuộc với v thì số thành phần liên thông tăng lên ít nhất là 2. Tìm kiếm trên đồ thị Tìm kiếm trên đồ thị Cho đồ thị G V E và 1 đỉnh . Tìm kiếm trên đồ thị là phương pháp xuất phát từ đỉnh s và theo các cạnh liên thuộc để viếng thăm duyệt các đỉnh của đồ thị sao cho mỗi đỉnh được viếng thăm 1 lần nhằm tìm nghiệm của bài toán Ví dụ Kiểm tra xem có đường đi từ đỉnh u đến đỉnh v không Kiểm tra đồ thị có liên thông hay không Tìm kiếm trên đồ thị Trong chương này chúng ta sẽ tìm hiểu hai thuật toán tìm kiếm cơ bản trên đồ thị Thuật toán tìm kiếm theo chiều rộng Breadth First Search BFS Thuật toán tìm kiếm theo chiều sâu Depth First .

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Thuật toán tìm kiếm theo chiều sâu
• Tìm kiếm trên đồ thị
• Thuật toán tìm kiếm
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• 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ề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng