Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản - Nguyễn Đức Nghĩa
Phần 2
LÝ THUYẾT ĐỒ THỊ
Graph Theory
1
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Nội dung
Chương 1. Các khái niệm cơ bản
– Đồ thị vô hướng và có hướng
– Các thuật ngữ cơ bản
– Một số dạng đồ thị vô hướng đặc biệt
Chương 2. Biểu diễn đồ thị
– Ma trận kề, ma trận trọng số, Ma trận liên thuộc đỉnh
cạnh
– Danh sách cạnh, Danh sách kề
Chương 3. Duyệt đồ thị
– Tìm kiếm theo chiều sâu; Tìm kiếm theo chiều rộng
– Tìm đường đi và kiểm tra tính liên thông
2
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Nội dung
Chương 4. Cây và cây khung của đồ thị
– Cây và các tính chất của cây
– Cây khung của đồ thị
– Bài toán cây khung nhỏ nhất
Chương 5. Bài toán đường đi ngắn nhất
– Phát biểu bài toán
– Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Dijkstra,
Ford-Bellman)
– Đường đi ngắn nhất trên đồ thị không có chu trình
– Đường đi ngắn nhất giữa mọi cặp đỉnh (Thuật toán Floyd)
Chương 6. Bài toán luồng cực đại trong mạng
– Mạng, luồng và bài toán luồng cực đại
– Định lý Ford-Fulkerson
– Thuật toán Ford-Fulkerson
– Một số ứng dụng
3
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Chương 1
CÁC KHÁI NIỆM CƠ BẢN
4
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Chương 1
CÁC KHÁI NIỆM CƠ BẢN
1.1. Đồ thị trong thực tế
1.2. Các loại đồ thị
1.3. Bậc của đỉnh
1.4. Đồ thị con
1.5. Đồ thị đẳng cấu
1.6. Đường đi và chu trình
1.7. Tính liên thông
1.8. Một số loại đồ thị đặc biệt
1.9. Tô màu đồ thị
5
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Không phải
Đồ thị là gì?
cái này
• Trong toán học đời thường hiểu là:
Bản vẽ hay Sdiễn dữ liệu nhờ sử
dụ
• Trong toán rời rạc:
Đây là cấu trúc rời rạc có tính trực quan cao,
rất tiện ích để biểu diễn các quan hệ.
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Các ứng dụng thực tế của đồ thị
• Có tiềm năng ứng dụng trong nhiều lĩnh vực (Đồ
thị có thể dùng để biểu diễn các quan hệ. Nghiên
cứu quan hệ giữa các đối tượng là mục tiêu của
nhiều lĩnh vực khác nhau).
• Ứng dụng trong mạng máy tính, mạng giao thông,
mạng cung cấp nước, mạng điện,…) lập lịch, tối
ưu hoá luồng, thiết kế mạch, quy hoạch phát
triển...
• Các ứng dụng khác: Phân tích gen, trò chơi máy
tính, chương trình dịch, thiết kế hướng đối tượng,
…
7
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Mối liên hệ giữa các môn học
461
322
143
373
321
326
142
370
415
410
341
413
417
378
421
Đỉnh = môn học
Cạnh có hướng = đk tiên quyết
401
8
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Biểu diễn mê cung
S
S
B
E
E
Đỉnh = phòng
Cạnh = cửa thông phòng hoặc hành lang
9
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Biểu diễn mạch điện
(Electrical Circuits)
Nguồn
Công tắc
Đỉnh = nguồn, công tắc, điện trở, …
Cạnh = đoạn dây nối
Điện trở
10
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Các câu lệnh của chương trình
Program statements
x1
x2
-
x1=q+y*z
x2=y*z-q
+
Thoạt nghĩ:
*
*
q
q
q
y
z
y*z tính hai lần
x1
+
x2
-
Loại
Biểu thức con
chung:
*
q
Đỉnh = ký hiệu/phép toán
Cạnh = mối quan hệ
y
z
11
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Yêu cầu trình tự (Precedence)
S1
S2
S3
S4
S5
S6
a=0;
6
b=1;
c=a+1
d=b+a;
e=d+1;
e=c+d;
5
4
Các câu lệnh nào phải thực hiện trước S6?
3
S1, S2, S3, S4
Đỉnh = câu lệnh
Cạnh = yêu cầu trình tự
2
1
12
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Truyền thông trong mạng máy tính
(Information Transmission in a Computer Network)
56
Tokyo
Hà nội
Seoul
128
New York
16
181
30
140
Bắc kinh
Sydney
Đỉnh = máy tính
Cạnh = tốc độ truyền thông
13
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Luồng giao thông trên xa lộ
(Traffic Flow on Highways)
UW
Đỉnh = thành phố
Cạnh = lượng xe cộ trên
tuyến đường cao tốc kết
nối giữa các thành phố
14
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Mạng xe buýt
15
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Mạng tàu điện ngầm
16
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Sơ đồ đường phố
17
Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà
Tải về để xem bản đầy đủ
275 trang
27200
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_phan_2_ly_thuyet_do_thi_chuong_1_cac.pptx
