Đồ_thị liên_thông Tính liên_thông connectivity là một trong những tính_chất quan_trọng nhất của đồ_thị nói_riêng và lý_thuyết đồ_thị nói_chung Định_nghĩa Một đồ_thị được gọi là liên_thông connected nếu có đường đi giữa mọi cặp đỉnh phân_biệt của đồ_thị Ngược_lại đồ_thị này được gọi là không liên_thông disconnected Cho đồ_thị G X U vô hướng hay có hướng Ta định_nghĩa một quan_hệ như hệ sau trên tập đỉnh X Với mọi i j thuộc X i xấp_xỉ j i j hay có dây_chuyền đỉnh đầu là i và đỉnh cuối là j Quan_hệ này có 3 tính_chất phản_xạ đối_xứng và bắc_cầu nên nó là một quan_hệ tương_đương Do_đó tập X được phân hoạch thành các lớp tương_đương Ta định_nghĩa BULLET Một thành_phần liên_thông của đồ_thị là một lớp tương_đương được xác_định bởi quan_hệ xấp_xỉ nói trên BULLET Số_thành phần liên_thông của đồ_thị là số_lượng các lớp tương_đương BULLET Một đồ_thị liên_thông là 1 đồ_thị chỉ có 1 thành_phần liên_thông Thành_phần liên_thông Một đồ_thị không liên_thông sẽ bao_gồm nhiều đồ_thị con liên_thông các đồ_thị con này được gọi là các thành_phần liên_thông connected component Đồ_thị liên_thông khi và chỉ khi có một thành_phần liên_thông Trong hình trên có 4 thành_phần liên_thông Đỉnh k đứng riêng_lẻ theo quy_ước cũng tính là 1 thành_phần liên_thông Các định_lý BULLET Định_lý về đường đi giữa 2 đỉnh bậc lẻ Nếu một đồ_thị G không quan_tâm liên_thông hay không có đúng 2 đỉnh bậc lẻ chắc_chắn sẽ có một đường đi nối 2 đỉnh này BULLET Định_lý về số cạnh của đồ_thị Định_lý bắt_tay Số cạnh tối_đa của một đơn đồ_thị không liên_thông G gồm n đỉnh và k thành_phần là formula _ 1 Tính_chất BULLET Đồ_thị liên_thông có hướng BULLET Liên_thông mạnh strongly connected Đồ_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ị Xem thêm thành_phần liên_thông mạnh BULLET Liên_thông yếu weakly connected Đồ_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 tương_ứng với đồ_thị đã cho Tức_là huỷ_bỏ các hướng của các cạnh trong đồ_thị BULLET Liên_thông một phần unilaterally connected Đồ_thị có hướng gọi là liên_thông một phần nếu với mọi cặp đỉnh a b bất_kỳ có ít_nhất một đỉnh đến được đỉnh còn lại BULLET Đỉnh khớp cut vertex articulation point của một đồ_thị vô hướng là đỉnh mà nếu xoá đỉnh này khỏi đồ_thị và các cạnh nối đến nó thì số_thành phần liên_thông của đồ_thị sẽ tăng thêm BULLET Cạnh cầu bridge của một đồ_thị vô hướng là cạnh mà nếu xoá đi khỏi đồ_thị thì số_thành phần liên_thông của đồ_thị sẽ tăng thêm BULLET Đồ_thị song liên_thông biconnectivity là đồ_thị không chứa đỉnh khớp
Đồ_thị liên_thông