Đồ thị

LÝ THUYẾT ĐỒ THỊ


TS. NGUYỄN THANH HÙNG
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
MỤC TIÊU CỦA CHUYÊN ĐỀ
GIỚI THIỆU CÁC NỘI DUNG CƠ BẢN
TRAO ĐỔI VỀ NHỮNG KHÓ KHĂN KHI DẠY CHUYÊN ĐỀ LÝ THUYẾT ĐỒ THỊ
TRAO ĐỔI KINH NGHIỆM, PHƯƠNG PHÁP GIẢNG DẠY CÁC NỘI DUNG CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
CÁC NỘI DUNG CƠ BẢN
CÁC KHÁI NIỆM CƠ BẢN
BÀI TOÁN TÌM KIẾM TRÊN ĐỒ THỊ
CẦU, ĐIỂM KHỚP, THÀNH PHẦN SONG LIÊN THÔNG, LIÊN THÔNG MẠNH
BÀI TOÁN EULER, HAMINTON
BÀI TOÁN CÂY KHUNG
BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
BÀI TOÁN LUỒNG TRÊN MẠNG, CẶP GHÉP

NHỮNG KHÓ KHĂN – THUẬN LỢI
HỌC SINH CHƯA ĐƯỢC CHUẨN BỊ ĐẦY ĐỦ CÁC KIẾN THỨC TOÁN HỌC CẦN THIẾT
QUỸ THỜI GIAN CÓ HẠN
NỘI DUNG CẦN GIẢNG DẠY CHƯA ĐƯỢC CHUẨN BỊ CHO GIÁO VIÊN
THỜI ĐIỂM THI QUỐC GIA DỜI LÊN SỚM HƠN
TÀI LIỆU ĐẦY ĐỦ:
TOÁN RỜI RẠC (NGUYỄN ĐỨC NGHĨA, NGUYỄN TÔ THÀNH)
GIẢI THUẬT&LẬP TRÌNH(LÊ MINH HOÀNG)
Một số vấn đề cần lưu ý khi xây dựng nội dung giảng dạy

Trang bị vừa đủ kiến thức
Bỏ qua các phần chứng minh về toán không cần thiết
Tập trinh giới thiệu về các bài toán và thuật toán giải các bài toán
Phân bố chương trình cần giảng dạy và phần học sinh tự học
Tìm nguồn bài tập ứng dụng phong phú cho học sinh
Kiểm tra đánh giá
NHỮNG KHÁI NIỆM CƠ BẢN
Khái niệm đồ thị: Đồ thị vô hướng
Đồ thị, đỉnh, cung
Bậc của một đỉnh + định lý về quan hệ của bậc các đỉnh và số cung
Đường đi, liên thông, miền liên thông
Biểu diễn đồ thị
Ma trận kề, biểu diễn đồ thị thưa
Thuật toán tìm kiếm
Tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu
Bài tập
Thuật toán tìm kiếm theo chiều rộng
Ý tưởng xây dựng thuật toán
Gần đến trước, xa đến sau
Mỗi đỉnh thăm đúng một lần
Áp dụng để tìm đường đi ngắn nhất
Cài đặt
Bài tập ứng dụng
Các bài toán trên mảng 2 chiều
Các bài toán trò chơi, biến đổi trạng thái
…
Chu trình Euler
Các khái niệm
Định lý về điều kiện cần và đủ để có chu trình Euler
Cài đặt
Cài đặt bàng hàng đợi
Cài đặt bằng đệ quy
Đường đi Euler
Bài toán K-nét
Cây Khung
Cây
Cây khung và bài toán tìm cây khung nhỏ nhất
Thuật toán Prim
Thuật toán Kruskal
Đường đi ngắn nhất
Bài toán đường đi ngắn nhất
Thuật toán Ford-Bellman
Thuật toán Dijkstra
Thuật toán Floyd
Luồng trên mạng
Mạng
Luồng trong mạng
Bài toán tìm luồng cực đại
Thuật toán Ford-Fulkerson