tailieunhanh - Bài giảng Thuật toán ứng dụng: Đồ thị - Trương Xuân Nam

Bài giảng Thuật toán ứng dụng: Đồ thị cung cấp cho người học những kiến thức như: Khái niệm đồ thị; Biểu diễn đồ thị trong máy tính; Duyệt đồ thị; Đường đi ngắn nhất; Bài tập. Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Đồ thị Nội dung 1. Khái niệm đồ thị 2. Biểu diễn đồ thị trong máy tính 3. Duyệt đồ thị 4. Đường đi ngắn nhất 5. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Khái niệm đồ thị TRƯƠNG XUÂN NAM 3 Khái niệm đồ thị Đồ thị Sự trừu tượng hóa các đối tượng và các mối liên hệ giữa chúng trong thực tế Đường đi giữa các thành phố Đường nối mạng giữa các thiết bị kết nối Đường điện trong khu vực Mối quan hệ giữa các cá nhân trên mạng xã hội Các đối tượng các đỉnh Các mối quan hệ kết nối các cạnh cung TRƯƠNG XUÂN NAM 4 Khái niệm đồ thị Đồ thị các đỉnh các cung nối giữa chúng G V E G Graph đồ thị V Vertices đỉnh E Edges cung Tập V tập các đỉnh thường đánh số từ 1 đến n hoặc từ 0 đến n-1 Tập E tập các cung nối giữa hai đỉnh một cung là một cặp u v có thể u v Đồ thị có hướng cung u v và cung v u không có mối liên hệ gì đặc biệt thường nói gọi tắt là đồ thị TRƯƠNG XUÂN NAM 5 Khái niệm đồ thị Đa đồ thị giữa các cặp u v có thể có nhiều hơn 1 cung nối chúng Đơn đồ thị giữa các cặp u v chỉ có tối đa 1 cung Đồ thị vô hướng cung u v và cung v u là một không phân biệt Trường hợp này người ta dùng từ cạnh u v để chỉ ý nghĩa u v và v u là tương đương TRƯƠNG XUÂN NAM 6 Độ đo về đỉnh cung cạnh Nếu có cạnh u v thì hai đỉnh u và v được gọi là kề nhau đỉnh liền kề Cạnh e u v gọi là liên thuộc hay phụ thuộc đỉnh u và cả đỉnh v đương nhiên Bậc của đỉnh v deg v số cạnh phụ thuộc vào v số đỉnh liền kề với v Trong đồ thị vô hướng số đỉnh bậc lẻ luôn chẵn Cung e u v e gọi là cung ra khỏi u và là cung đi vào v Số cung ra của v là deg v số cung vào v là deg- v Tổng các deg và def- luôn bằng nhau và bằng số cung Cung u v có thể có trọng số khi đó G là đồ thị trọng số TRƯƠNG XUÂN NAM 7 Đường đi và chu trình Đường đi từ u đến v bắt đầu từ u liên tiếp di chuyển qua các đỉnh kề để đến v Đường đi không tự cắt từ u đến v quá trình di chuyển từ u đến v không thăm lại một đỉnh đã đi qua thường nói về đường đi ta nói về đường đi không tự cắt Chu trình đường đi từ u trở về chính nó Một đường đi chu trình .

• Cơ sở dữ liệu
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Biểu diễn đồ thị trong máy tính
• Thuật toán Floyd Warshall
• Đồ thị phẳng
• Phân tích Thuật toán
• Quy hoạch động
• Cài đặt thuật toán
• Thuật toán Tham lam
• Ý tưởng tham lam
• Bài toán lập lịch
• Tiếp cận tham lam
• Toán ứng dụng
• Bài giảng Toán ứng dụng
• Biểu diễn đồ thị
• Thuật toán tìm kiếm
• Bài toán đường đi ngắn nhất
• Thuật toán Floyd
• Tiếp cận chia để trị
• Bài toán tháp Hà Nội
• Bài toán tính giá trị đa thức
• Bài toán đếm số dãy con
• Bài giảng Ma trận
• Khái niệm thuật toán
• Thuật toán trong tin học
• Phương pháp biểu diễn thuật toán
• Cấu trúc dữ liệu
• Chương trình nhân hai số nguyên
• Kỹ năng phân loại bài toán
• Kỹ năng phân tích thuật toán
• Quay lui đệ qui
• Bài toán quy hoạch động
• Thuật toán quay lui
• Liệt kê nhị phân
• Đệ quy quay lui
• Bài toán liệt kê xâu nhị phân
• Phương trình tuyến tính
• Thuật toán nhánh và cận
• Chu trình Euler
• Thuật toán Dijkstra
• Thuật toán Kruskal
• Disjoint set structure
• Bài toán xếp ba lô
• Bài toán dãy con chung dài nhất
• Phân tích về quy hoạch động
• Thư viện cấu trúc dữ liệu
• Cấu trúc dữ liệu mở
• Thuật toán Dequeue
• Chia để trị
• Thuật toán chia để trị
• Công thức truy hồi
• Tìm kiếm nhị phân
• Thuật toán Tarjan DFS
• Duyệt theo chiều sâu
• Cấu trúc dữ liệu duy trì
• Cấu trúc dữ liệu trừu tượng
• Giải thuật tìm kiếm
• Cài đặt tìm kiếm ở thư viện
• Hàm đệ quy
• Quy tắc xây dựng phần tử
• Nhánh cận
• Chiến lược tìm kiếm tối ưu tổ hợp
• Danh sách tuyến tính
• Quan hệ tuyến tính
• Ngăn xếp dữ liệu
• Dãy con cực đại
• Dãy con tăng dần dài nhất
• Dãy con chung dài nhất
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Thuật toán quay lui tổng quát
• Ứng dụng của thuật toán quay lui
• Chuỗi nhị phân
• Bài giảng Lý thuyết tài chính ứng dụng
• Lý thuyết tài chính ứng dụng
• Kế toán doanh nghiệp
• Bản chất cuả tài chính
• Chức năng của tài chính
• Vai trò của tín dụng
• Tài chính doanh nghiệp
• Bài giảng Tin học 10 bài 8
• Bài giảng điện tử Tin học 10
• Bài giảng lớp 10 Tin học
• Bài giảng điện tử lớp 10
• Quy trình quản lý tin học
• Giải các bài toán khoa học kĩ thuật
• Những ứng dụng của tin học
• Bài giảng Kỹ thuật điện tử
• Kỹ thuật điện tử
• Vi mạch khuếch đại thuật toán
• Vi mạch thuật toán
• Thông số kỹ thuật vi mạch thuật toán
• Ứng dụng vi mạch thuật toán
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Cấu trúc dữ liệu và thuật toán
• Ứng dụng cây gia phả
• Ứng dụng cây thư mục
• Thiết kế thuật toán
• Bài giảng Phân tích thuật toán
• Thuật toán hoán vị
• Số nghịch thế
• Bảng nghịch thế
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều sâu
• Thuật toán tìm kiếm theo chiều rộng
• Ứng dụng thuật toán tìm kiếm đồ thị