Thuật_toán tìm thành_phần liên_thông BULLET Một đồ_thị G được gọi là liên_thông nếu có dây_chuyền giữa mọi cặp đỉnh phân_biệt đồ_thị G BULLET Thành_phần liên_thông của đồ_thị G là các đồ_thị con liên_thông tối đại của G BULLET Đồ_thị G được gọi là đồ_thị liên_thông nếu G chỉ có một thành_phần liên_thông BULLET Đồ_thị có hướng gọi là liên_thông mạnh nếu có đường đi từ a tới b và từ b tới a với mọi cặp đỉnh a và b của đồ_thị BULLET Đồ_thị có hướng gọi là liên_thông yếu nếu có đường đi giữa 2 đỉnh bất_kỳ của đồ_thị vô hướng nền Thuật_toán BULLET Giả_sử đồ_thị G gồm n đỉnh Có_thể tìm các thành_phần liên_thông của đồ_thị bằng cách duyệt theo chiều sâu BULLET Sử_dụng tìm_kiếm theo chiều sâu được đưa ra trong thế_kỷ 19 bởi nhà toán_học người Pháp Charles_Pierre_Trémaux_Mã giả codice _ 1 BULLET Ghi_chú khi thuật_toán kết_thúc thì các đỉnh nằm trong cùng 1 thành_phần liên_thông sẽ được gắn cùng 1 nhãn đỉnh Ví_dụ BULLET Cho đồ_thị G vô hướng 4 đỉnh BULLET Xét tính liên_thông đồ_thị G bằng thuật_toán DFS BULLET Bước 1 Gán nhãn các đỉnh là 0 BULLET Bước 2 BULLET Với I 1 gán nhãn đỉnh I 1 và xét từ đỉnh I có đường đi đến các đỉnh còn lại không BULLET Ta sẽ thấy từ đỉnh 1 có đường đi đến đỉnh 2 nên sẽ gán nhãn 2 là 1 BULLET Tại đỉnh 2 ta xem có đường đi từ 2 đến các đỉnh còn lại không từ đỉnh 2 ta đi được đến đỉnh 3 nên ta sẽ gán nhãn của đỉnh 3 là nhãn của đỉnh 2 BULLET Tại đỉnh 3 ta xem có đường đi từ 3 đến các đỉnh còn lại không từ đỉnh 3 ta đi được đến đỉnh 4 nên ta sẽ gán nhãn của đỉnh 4 là nhãn của đỉnh 3 BULLET Từ đỉnh 1 ta đã đi được đến các đỉnh còn lại trong đồ_thị nên G là 1 đồ_thị lien thông vì G chỉ có 1 chu_trình duy_nhất Kết_thúc thuật_toán Tài_liệu BULLET Giáo_trình lý_thuyết đồ_thị Trần_Đan_Thư_Dương Anh Đức Đại_Học Khoa_Học_Tự_Nhiên Thành_phố Hồ_Chí_Minh Nhà_xuất_bản ĐHQG Thành_phố Hồ_Chí_Minh Liên_kết ngoài BULLET http en wikipedia org wiki K edge connected _ graph BULLET http en wikipedia org wiki K vertex connected _ graph
Thuật_toán tìm thành_phần liên_thông