Bài giảng Chương 7: Đồ thị và các thuật toán đồ thị

CHƯƠNG 7<br /> <br /> Đồ thị và các thuật toán đồ thị<br /> HCM<br /> <br /> HAN<br /> <br /> HP<br /> <br /> DAN<br /> <br /> NỘI DUNG<br /> 1. Đồ thị<br /> Đồ thị vô hướng, Đồ thị có hướng,Tính liên thông của đồ thị<br /> 2. Biểu diễn đồ thị<br /> Biểu diễn đồ thị bởi ma trận, Danh sách kề, Danh sách cạnh<br /> 3. Các thuật toán duyệt đồ thị<br /> 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<br /> 4. Một số ứng dụng của tìm kiếm trên đồ thị<br /> Bài toán đường đi, Bài toán liên thông,<br /> Đồ thị không chứa chu trình và bài toán sắp xếp tôpô, Bài toán tô màu đỉnh đồ thị<br /> 5. Bài toán cây khung nhỏ nhất<br /> Thuật toán Kruscal, Cấu trúc dữ liệu biểu diễn phân hoạch,<br /> 6. Bài toán đường đi ngắn nhất<br /> Thuật toán Dijkstra, Cài đặt thuật toán với các cấu trúc dữ liệu<br /> <br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> 2<br /> <br /> 1. Đồ thị<br /> Đồ thị là cặp (V, E), trong đó<br /> <br /> <br /> <br /> V là tập đỉnh<br /> E là họ các cặp đỉnh gọi là các cạnh<br /> <br /> Ví dụ:<br /> <br /> <br /> <br /> <br /> Các đỉnh là các sân bay<br /> Các cạnh thể hiện đường bay nối hai sân bay<br /> Các số trên cạnh có thể là chi phí (thời gian, khoảng cách)<br /> <br /> HAP<br /> <br /> DBP<br /> <br /> DAN<br /> HCM<br /> <br /> HAN<br /> <br /> BKK<br /> <br /> NHT<br /> <br /> VIN<br /> <br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> 3<br /> <br /> Các kiểu cạnh<br /> Cạnh có hướng (Directed edge)<br />  Cặp có thứ tự gồm hai đỉnh (u,v)<br />  Đỉnh u là đỉnh đầu<br />  Đỉnh v là đỉnh cuối<br />  Ví dụ, chuyến bay<br /> Cạnh vô hướng (Undirected edge)<br />  Cặp không có thứ tự gồm 2 đỉnh (u,v)<br />  Ví dụ, tuyến bay<br /> Đồ thị có hướng (digraph)<br />  Các cạnh có hướng<br />  Ví dụ, mạng truyền tin<br /> Đồ thị vô hướng (Undirected graph/graph)<br />  Các cạnh không có hướng<br />  Ví dụ, mạng tuyến bay<br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> HAN<br /> <br /> flight<br /> VN 426<br /> <br /> HCM<br /> <br /> HAN<br /> <br /> 1135<br /> km<br /> <br /> HCM<br /> <br /> 4<br /> <br /> Ứng dụng<br /> Mạch lôgic (Electronic circuits)<br /> <br /> <br /> <br /> Phòng máy 1<br /> <br /> Mạch in<br /> Mạch tích hợp<br /> <br /> Phòng hành chính<br /> <br /> Mạng giao thông (Transportation<br /> networks)<br /> <br /> <br /> <br /> Phòng máy 2<br /> <br /> Phòng Giáo vụ<br /> <br /> Mạng xa lộ<br /> Mạng tuyến bay<br /> <br /> Mạng máy tính (Computer<br /> networks)<br /> <br /> <br /> <br /> <br /> Mạng cục bộ<br /> Internet<br /> Web<br /> <br /> Trường ĐHQG<br /> Ban Giám đốc<br /> Phòng Tuyên huấn<br /> <br /> Cơ sở dữ liệu (Databases)<br /> <br /> <br /> Tổ Tin<br /> <br /> Sơ đồ quan hệ thực thể<br /> (Entity-relationship diagram)<br /> <br /> Bờm<br /> Cuội<br /> <br /> Chị Hằng<br /> <br /> 5<br /> <br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> Thuật ngữ<br /> Đầu mút của cạnh<br /> <br /> <br /> U và V là các đầu mút của cạnh a<br /> <br /> Cạnh kề với đỉnh<br /> <br /> <br /> a, d, và b kề với đỉnh V<br /> <br /> Đỉnh kề<br /> <br /> <br /> U và V là kề nhau<br /> <br /> Bậc của đỉnh<br /> <br /> <br /> a<br /> <br /> X có bậc 5<br /> <br /> U<br /> <br /> V<br /> d<br /> <br /> e<br /> W<br /> <br /> h và i là các cạnh lặp<br /> <br /> Khuyên<br /> <br /> <br /> h<br /> X<br /> <br /> c<br /> <br /> Cạnh lặp<br /> <br /> <br /> b<br /> <br /> j<br /> Z<br /> <br /> i<br /> g<br /> <br /> f<br /> <br /> Y<br /> <br /> j là khuyên<br /> <br /> Đơn đồ thị: Không chứa cạnh lặp và khuyên<br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> 6<br /> <br /> Thuật ngữ (tiếp tục)<br /> Đường đi<br />  Dãy các đỉnh (hoặc dãy các cạnh), trong đó hai đỉnh<br /> liên tiếp là có cạnh nối:<br /> P: s = v0, v1, ..., vk-1, vk = t,<br /> (vi-1, vi) là cạnh của đồ thị, i=1, 2, ..., k.<br />  Độ dài của đường đi là số cạnh trên đường đi (k).<br />  s - đỉnh đầu và t - đỉnh cuối của đường đi P<br /> Đường đi đơn<br />  Các đỉnh trên đường đi là phân biệt<br /> <br /> 7<br /> <br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> Thuật ngữ (tiếp tục)<br /> V<br /> <br /> a<br /> U<br /> c<br /> <br /> b<br /> <br /> d<br /> P2<br /> <br /> P1<br /> X<br /> <br /> h<br /> <br /> Z<br /> <br /> e<br /> <br /> W<br /> <br /> g<br /> f<br /> <br /> Y<br /> <br /> Ví dụ<br />  P1= V,X,Z (dãy cạnh: b, h) là đường đi đơn<br />  P2= U,W,X,Y,W,V) (P2=c,e,g,f,d) là đường đi nhưng<br /> không là đơn<br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> 8<br /> <br /> Thuật ngữ (tiếp)<br /> Chu trình<br /> <br /> <br /> Đường đi gồm các cạnh<br /> phân biệt có đỉnh đầu trùng<br /> đỉnh cuối<br /> <br /> Chu trình đơn<br /> <br /> <br /> Ngoại trừ đầu trùng cuối,<br /> không còn hai đỉnh nào<br /> giống nhau<br /> <br /> Ví dụ<br /> <br /> <br /> <br /> a<br /> U<br /> c<br /> <br /> V<br /> <br /> b<br /> <br /> d<br /> C2<br /> <br /> X<br /> <br /> h<br /> <br /> e<br /> <br /> C1<br /> g<br /> <br /> W<br /> <br /> C1= V,X,Y,W,U là CT đơn<br /> C2=U,W,X,Y,W,V là chu trinh<br /> không là đơn<br /> <br /> f<br /> <br /> Z<br /> <br /> Y<br /> <br /> 9<br /> <br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> Tính chất<br /> Tính chất 1<br /> <br /> Sv deg(v) = 2m<br /> CM: mỗi cạnh được đếm 2 lần<br /> <br /> Tính chất 2<br /> Trong đơn đồ thị vô hướng (đồ<br /> thị không có cạnh lặp và<br /> khuyên)<br /> m  n (n - 1)/2<br /> CM: mỗi đỉnh có bậc không<br /> quá (n - 1)<br /> <br /> Ký hiệu<br /> n<br /> m<br /> deg(v)<br /> <br /> số đỉnh<br /> số cạnh<br /> bậc của đỉnh v<br /> <br /> Ví dụ<br /> <br /> <br /> <br /> <br /> n=4<br /> m=6<br /> deg(v) = 3<br /> <br /> Tương tự có những cận cho<br /> đồ thị có hướng<br /> Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN<br /> <br /> 10<br /> <br />