Giảng viên: ThS. Trần Quang Khải
TOÁN RỜI RẠC
Chương 06:
Đồ thị
Toán rời rạc: 2011-2012
Nội dung
1. Giới thiệu về lý thuyết đồ thị.
2. Đồ thị vô hướng – Đồ thị có hướng.
3. Bậc của đỉnh.
4. Một số dạng đồ thị đặc biệt.
5. Biểu diễn đồ thị trên máy tính.
Chương 6: Đồ thị 2
Toán rời rạc: 2011-2012
Giới thiệu
Những câu hỏi cũ:
Đường nào nhanh nhất tới nhà người yêu?
Đường nào gần nhất tới café Gió và Nước?
Chương 6: Đồ thị 3
Toán rời rạc: 2011-2012
Giới thiệu
Câu hỏi khác:
Thế kế mạng LAN cho tòa nhà 20 tầng thế nào đây?
Sắp đặt các links trong website sao cho hợp lý?
Sắp xếp cả núi công việc để hoàn thành sớm nhất?
Chương 6: Đồ thị 4
Toán rời rạc: 2011-2012
Giới thiệu
Định nghĩa đồ thị (graph): cấu trúc rời rạc gồm
Các đỉnh (vertices or nodes).
Các cạnh (edges) nối các đỉnh.
Biểu diễn:
Đỉnh: các điểm.
Cạnh: đường thẳng/cong.
Hai loại:
Đồ thị vô hướng (undirected graph).
Đồ thị có hướng (directed graph).
Chương 6: Đồ thị 5